DOC PREVIEW
MIT 6 896 - Exchange Market Model

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.896: Topics in Algorithmic Game Theory Lecture 15 Constantinos DaskalakisRecapExchange Market Model ntraders kdivisible goods trader i has: - endowment of goods non-negative reals amount of goods trader comes to the marketplace with ui: Xi⊆ Rk+−→ R+consumption set for trader i specifies trader i’s utility for bundles of goods ei∈ Xi- utility functionFisher Market Model can be obtained as a special case of an exchange market, when endowment vectors are parallel: in this case, relative incomes of the traders are independent of the prices. n traders with: ei= mi· e, mi> 0,mi: scalar,e : vectork divisible goods owned by seller; money mi , and utility function ui seller has qj units of good jCompetitive (or Walrasian) Market Equilibrium total demand total supply Def: A price vector is called a competitive market equilibrium iff there exists a collection of optimal bundles of goods, for all traders i = 1,…, n, such that the total supply meets the total demand, i.e. p ∈ Rk+xi(p)n�i=1xi(p) ≤n�i=1ei[ For Fisher Markets: ] n�i=1xi(p) ≤ qArrow-Debreu Theorem 1954 Theorem [Arrow-Debreu 1954]: Suppose Then a competitive market equilibrium exists. (i) is closed and convex Xi(iii a) uiis continuous(iii b) uiis quasi-concaveuiis nonsatiated(iii c) ∀y ∈ Xi, ∃x ∈ Xis.t. ui(x) >ui(y)ui(x) >ui(y)=⇒ ui(λx + (1 − λ)y) >ui(y), ∀λ ∈ (0, 1)(ii) (all coordinates positive) ei>> 0, for all iUtility Functions ui(x)=�juij· xρj1ρ, −∞< ρ ≤ 1CES (Constant Elasticity of Substitution) utility functions: ρ =1linear utility form Leontief utility form ρ → −∞ρ → 0Cobb-Douglas form ui(x)=�jaijxjui(x) = minj{aijxj}ui(x)=�jxaijj, where�jaij=1Eisenberg-Gale’s Convex Program for Fisher Model max um11· um22· ...· umnns.t ui=�juijxρij1ρ�ixij≤ qjxij≥ 0Remarks: - No budgets constraint! - It is not necessary that the utility functions are CES; the program also works if they are concave, and homogeneous - Optimal Solution is a market equilibrium (alternative proof of existence)Complexity of the Exchange ModelComplexity of market equilibria in CES exchange economies. At least as hard as solving Nash Equilibria [CVSY ’05] Poly-time algorithms known [Devanur, Papadimitriou, Saberi, Vazirani ’02], [Jain ’03], [CMK ’03], [GKV ’04],… OPEN!! Back to the Exchange Model !!!!!!!!!! -1 0 1 !!!!!!!!!ρ"−∞Hardness of Leontief Exchange Markets Proof Idea: Theorem [Codenotti, Saberi, Varadarajan, Ye ’05]: Finding a market equilibrium in a Leontief exchange economy is at least as hard as finding a Nash equilibrium in a two-player game. Reduce a 2-player game to a Leontief exchange economy, such that given a market equilibrium of the exchange economy one can obtain a Nash equilibrium of the two-player game. Corollary: Leontief exchange economies are PPAD-hard.Gross-Substitutability ConditionExcess Demand at prices p f(p) :=�ixi(p) −�ieifj(p) :=�ixij(p) −�ieij, ∀jWe already argued that under the Arrow-Debreu Thm conditions: (H) f is homogeneous, i.e. f(a · p)=f(p), ∀a>0(WL) f satisfies Walras’s Law, i.e. pT· f(p)=0, ∀p(we argued that the last property is true using nonsatiation + quasi-concavity, see next slie) suppose there is a unique demand at a given price vector p and its is continuous (see last lecture)Justification of (WL) under Arrow-Debreu Thm conditions Nonsatiation + quasi-concavity  local non-satiation  at equilibrium every trader spends all her budget, i.e. if xi(p) is an optimal solution to Programi(p) then i.e. every good with positive price is fully consumed p · xi(p)=p · ei=⇒ p ·��ixi(p) −�iei�=0Excess Demand at prices p f(p) :=�ixi(p) −�ieifj(p) :=�ixij(p) −�ieij, ∀jWe already argued that under the Arrow-Debreu Thm conditions: (H) f is homogeneous, i.e. f(a · p)=f(p), ∀a>0(WL) f satisfies Walras’s Law, i.e. pT· f(p)=0, ∀psuppose there is a unique demand at a given price vector p and its is continuous (see last lecture)Gross-Substitutability (GS) Def: The excess demand function satisfies Gross Substitutability iff for all pairs of price vectors p and p’: pj<p�j, for some jpi≤ p�i, ∀ifk(p) <fk(p�), ∀k s.t. pk= p�kIn other words, if the prices of some goods are increased while the prices of some other goods are held fixed, this can only cause an increase in the demand of the goods whose price stayed fixed.Differential Form of Gross-Substitutability (GSD) Def: The excess demand function satisfies the Differential Form of Gross Substitutability iff for all r, s the partial derivatives exist and are continuous, and for all p : ∂fr∂ps∂fr∂ps> 0, for all r �= s.Clearly: (GS) !(GSD)!Not all goods are free (Pos) Def: The excess demand function satisfies (Pos) if not all goods are free at equilibrium. I.e. there exists at least one good in which at least one trader is interested.Properties of Equilibrium Lemma 1 [Arrow-Block-Hurwicz 1959]: ¯pSuppose that the excess demand function of an exchange economy satisfies (H), (GSD) and (Pos). Then if is an equilibrium price vector ¯pr> 0, ∀r.Call this property (E+) Lemma 2 [Arrow-Block-Hurwicz 1959]: ¯pSuppose that the excess demand function of an exchange economy satisfies (H), (GS) and (E+). Then if and are equilibrium price vectors, there exists such that ¯p�λ > 0¯p = λ · ¯p�.i.e. we have uniqueness of the equilibrium rayWeak Axiom of Revealed Preferences (WARP) Theorem [Arrow-Hurwicz 1960’s]: Proof on the board ¯ppSuppose that the excess demand function of an exchange economy satisfies (H), (WL), and (GS). If >0 is any equilibrium price vector and >0 is any non-equilibrium vector we have ¯pT· f(p) > 0.Computation of Equilibria Corollary 1 (of WARP): If the excess demand function satisfies (H), (WL), and (GS) and it can be computed efficiently, then a positive equilibrium price vector (if it exists) can be computed efficiently. proof sketch: W. l. o. g. we can restrict our search space to price vectors in [0,1]k, since any equilibrium can be rescaled to lie in this set (by homogeneity of the excess demand function). We can then run ellipsoid, using the separation oracle provided by the weak axiom of revealed


View Full Document

MIT 6 896 - Exchange Market Model

Download Exchange Market Model
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Exchange Market Model and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Exchange Market Model 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?