The nonlinear Bernstein-Schrodinger equation in Economics

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14298
DOI : http://dx.doi.org/10.1007/978-3-319-25040-3_6You do not have permission to access embedded form.

Résumé

In this paper we relate the Equilibrium Assignment Problem (EAP), which is underlying in several economics models, to a system of nonlinear equations that we call the “nonlinear Bernstein-Schrödinger system”, which is well-known in the linear case, but whose nonlinear extension does not seem to have been studied. We apply this connection to derive an existence result for the EAP, and an efficient computational method.

The nonlinear Bernstein-Schrodinger equation in Economics

Média

Voir la vidéo

Métriques

162
7
202.12 Ko
 application/pdf
bitcache://fffb6bccaaf9b705e5ef832bee648881112f3c20

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14298</identifier><creators><creator><creatorName>Alfred Galichon</creatorName></creator><creator><creatorName>Scott Kominers</creatorName></creator><creator><creatorName>Simon Weber</creatorName></creator></creators><titles>
            <title>The nonlinear Bernstein-Schrodinger equation in Economics</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Sat 17 Feb 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">fffb6bccaaf9b705e5ef832bee648881112f3c20</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24688</version>
        <descriptions>
            <description descriptionType="Abstract">
In this paper we relate the Equilibrium Assignment Problem (EAP), which is underlying in several economics models, to a system of nonlinear equations that we call the “nonlinear Bernstein-Schrödinger system”, which is well-known in the linear case, but whose nonlinear extension does not seem to have been studied. We apply this connection to derive an existence result for the EAP, and an efficient computational method.

</description>
        </descriptions>
    </resource>
.

TOPICS IN EQUILIBRIUM TRANSPORTATION Alfred Galichon (NYU and Sciences Po) GSI, Ecole polytechnique, October 29, 2015 GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 1/ 22 THIS TALK This talk is based on the following two papers: AG, Scott Kominers and Simon Weber (2015a). Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility. AG, Scott Kominers and Simon Weber (2015b). The Nonlinear Bernstein-Schr¨odinger Equation in Economics, GSI proceedings. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 2/ 22 THIS TALK Agenda: 1. Economic motivation 2. The mathematical problem 3. Computation 4. Estimation GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 3/ 22 THIS TALK Agenda: 1. Economic motivation 2. The mathematical problem 3. Computation 4. Estimation GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 3/ 22 THIS TALK Agenda: 1. Economic motivation 2. The mathematical problem 3. Computation 4. Estimation GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 3/ 22 THIS TALK Agenda: 1. Economic motivation 2. The mathematical problem 3. Computation 4. Estimation GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 3/ 22 Section 1 ECONOMIC MOTIVATION GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 4/ 22 MOTIVATION: A MODEL OF LABOUR MARKET Consider a very simple model of labour market. Assume that a population of workers is characterized by their type x ∈ X , where X = Rd for simplicity. There is a distribution P over the workers, which is assumed to sum to one. A population of firms is characterized by their types y ∈ Y (say Y = Rd ), and their distribution Q. It is assumed that there is the same total mass of workers and firms, so Q sums to one. Each worker must work for one firm; each firm must hire one worker. Let π (x, y) be the probability of observing a matched (x, y) pair. π should have marginal P and Q, which is denoted π ∈ M (P, Q) . GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 5/ 22 OPTIMALITY In the simplest case, the utility of a worker x working for a firm y at wage w (x, y) will be α (x, y) + w (x, y) while the corresponding profit of firm y is γ (x, y) − w (x, y) . In this case, the total surplus generated by a pair (x, y) is α (x, y) + w + γ (x, y) − w = α (x, y) + γ (x, y) =: Φ (x, y) which does not depend on w (no transfer frictions). A central planner may thus like to choose assignment π ∈ M (P, Q) so to max π∈M(P,Q) Φ (x, y) dπ (x, y) . But why would this be the equilibrium solution? GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 6/ 22 EQUILIBRIUM The equilibrium assignment is determined by an important quantity: the wages. Let w (x, y) be the wage of employee x working for firm of type y. Let the indirect surpluses of worker x and firm y be respectively u (x) = max y {α (x, y) + w (x, y)} v (y) = max x {γ (x, y) − w (x, y)} so that (π, w) is an equilibrium when u (x) ≥ α (x, y) + w (x, y) with equality if (x, y) ∈ Supp (π) v (y) ≥ γ (x, y) − w (x, y) with equality if (x, y) ∈ Supp (π) By summation, u (x) + v (y) ≥ Φ (x, y) with equality if (x, y) ∈ Supp (π) . GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 7/ 22 THE MONGE-KANTOROVICH THEOREM OF OPTIMAL TRANSPORTATION One can show that the equilibrium outcome (π, u, v) is such that π is solution to the primal Monge-Kantorovich Optimal Transportation problem max π∈M(P,Q) Φ (x, y) dπ (x, y) and (u, v) is solution to the dual OT problem min u,v u (x) dP (x) + v (y) dQ (y) s.t. u (x) + v (y) ≥ Φ (x, y) Feasibility+Complementary slackness yield the desired equilibrium conditions π ∈ M (P, Q) u (x) + v (y) ≥ Φ (x, y) (x, y) ∈ Supp (π) =⇒ u (x) + v (y) = Φ (x, y) “Second welfare theorem”, “invisible hand”, etc. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 8/ 22 EQUILIBRIUM VS. OPTIMALITY Is equilibrium always the solution to an optimization problem? It is not. This is why this talk is about “Equilibrium Transportation,” which contains, but is strictly more general than “Optimal Transportation”. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 9/ 22 EQUILIBRIUM VS. OPTIMALITY Is equilibrium always the solution to an optimization problem? It is not. This is why this talk is about “Equilibrium Transportation,” which contains, but is strictly more general than “Optimal Transportation”. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 9/ 22 IMPERFECTLY TRANSFERABLE UTILITY Consider the same setting as above, but instead of assuming that workers’ and firm’s payoffs are linear in surplus, assume u (x) = max y {Uxy (w (x, y))} v (y) = max x {Vxy (w (x, y))} where Uxy (w) is nondecreasing and continuous, and Vxy (w) is nonincreasing and continuous. Motivation: taxes, decreasing marginal returns, risk aversion, etc. Of course, Optimal Transportation case is recovered when Uxy (w) = αxy + w Vxy (w) = γxy − w. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 10/ 22 IMPERFECTLY TRANSFERABLE UTILITY For (u, v) ∈ R2, let Ψxy (u, v) = min {t ∈ R : ∃w, u − t ≤ Uxy (w) and v − t ≤ Vxy (w)} so that Ψ is nondecreasing in both variables and (u, v) = (Uxy (w) , Vxy (w)) for some w if and only if Ψxy (u, v) = 0. Optimal Transportation case is recovered when Ψxy (u, v) = (u + v − Φxy ) /2. As before, (π, w) is an equilibrium when u (x) ≥ Uxy (w (x, y)) with equality if (x, y) ∈ Supp (π) v (y) ≥ Vxy (w (x, y)) with equality if (x, y) ∈ Supp (π) We have therefore that (π, u, v) is an equilibrium when Ψxy (u (x) , v (y)) ≥ 0 with equality if (x, y) ∈ Supp (π) . GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 11/ 22 Section 2 THE MATHEMATICAL PROBLEM GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 12/ 22 EQUILIBRIUM TRANSPORTATION: DEFINITION We have therefore that (π, u, v) is an equilibrium outcome when    π ∈ M (P, Q) Ψxy (u (x) , v (y)) ≥ 0 (x, y) ∈ Supp (π) =⇒ Ψxy (u (x) , v (y)) = 0 . Problem: existence of an equilibrium outcome? This paper: yes in the discrete case (X and Y finite), via entropic regularization. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 13/ 22 REMARK 1: LINK WITH GALOIS CONNECTIONS As soon as Ψxy is strictly increasing in both variables, Ψxy (u, v) = 0 expresses as u = Gxy (v) and v = G−1 xy (u) where the generating functions Gxy and G−1 xy are decreasing and continuous functions. In this case, relations u (x) = max y∈Y Gxy (v (y)) and v (y) = max x∈X G−1 xy (u (x)) generalize the Legendre-Fenchel conjugacy. This pair of relations form a Galois connection; see Singer (1997) and Noeldeke and Samuelson (2015). GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 14/ 22 REMARK 2: TRUDINGER’S LOCAL THEORY OF PRESCRIBED JACOBIANS Assuming everything is smooth, and letting fP and fQ be the densities of P and Q we have under some conditions that the equilibrium transportation plan is given by y = T (x), where mass balance yields |det DT (x)| = f (x) g (T (x)) and optimality yieds ∂x G−1 xT(x) (u (x)) + ∂uG−1 xT(x) (u (x)) u (x) = 0 which thus inverts into T (x) = e (x, u (x) , u (x)) . Trudinger (2014) studies Monge-Ampere equations of the form |det De (., u, u)| = f g (e (., u, u)) . (more general than Optimal Transport where no dependence on u). GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 15/ 22 DISCRETE CASE Our work (GKW 2015a and b) focuses on the discrete case, when P and Q have finite support. Call px and qy the mass of x ∈ X and y ∈ Y respectively. In the discrete case, problem boils down to looking for (π, u, v) such that    πxy ≥ 0, ∑y πxy = px , ∑x πxy = qy Ψxy (ux , vy ) ≥ 0 πxy > 0 =⇒ Ψxy (ux , vy ) = 0 . GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 16/ 22 Section 3 COMPUTATION GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 17/ 22 ENTROPIC REGULARIZATION Take temperature parameter T > 0 and look for π under the form πxy = exp − Ψxy (ux , vy ) T Note that when T → 0, the limit of Ψxy (ux , vy ) is nonnegative, and the limit of πxy Ψxy (ux , vy ) is zero. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 18/ 22 THE NONLINEAR BERNSTEIN-SCHR ¨ODINGER EQUATION If πxy = exp (−Ψxy (ux , vy ) /T) , condition π ∈ M (P, Q) boils down to set of nonlinear equations in (u, v)    ∑y∈Y exp − Ψxy (ux ,vy ) T = px ∑x∈X exp − Ψxy (ux ,vy ) T = qy which we call the nonlinear Bernstein-Schr¨odinger equation. In the optimal transportation case, this becomes the classical B-S equation    ∑y∈Y exp Φxy −ux −vy 2T = px ∑x∈X exp Φxy −ux −vy 2T = qy GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 19/ 22 ALGORITHM Note that Fx : ux → ∑y∈Y exp − Ψxy (ux ,vy ) T is a decreasing and continuous function. Mild conditions on Ψ therefore ensure the existence of ux so that Fx (ux ) = px . Our algorithm is thus a nonlinear Jacobi algorithm: - Make an initial guess of v0 y - Determine the uk+1 x to fit the px margins, based on the vk y - Update the vk+1 y to fit the qy margins, based on the uk+1 x . - Repeat until vk+1 is close enough to vk. One can proof that if v0 y is high enough, then the vk y decrease to fixed point. Convergence is very fast in practice. GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 20/ 22 Section 4 STATISTICAL ESTIMATION GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 21/ 22 MAXIMUM LIKELIHOOD ESTIMATION In practice, one observes ˆπxy and would like to estimate Ψ. Assume that Ψ belongs to a parametric family Ψθ, so that πθ xy = exp −Ψθ xy uθ x , vθ y ∈ M (P, Q). The log-likelihood l (θ) associated to observation ˆπxy is l (θ) = ∑ xy ˆπxy log πθ xy = − ∑ xy ˆπxy Ψθ xy uθ x , vθ y and thus the maximum likelihood procedure consists in min θ ∑ xy ˆπxy Ψθ xy uθ x , vθ y . GALICHON EQUILIBRIUM TRANSPORTATION SLIDE 22/ 22