Below is a very short summary of

Lecture 1: Introduction to Markets for Indivisible Goods

(by Alexander Teytelboym)

in a special zoom lecture series Towards a General Theory of Markets with Indivisible Goods organized by the University of Tokyo Market Design Center (UTMD). I would like to thank organizers and speakers for providing such wonderful lectures.

• Course Website
• Lecture Movie

1. Divisible good market

Convexity is the key to the existence of competitive equilibria.

• X is convex <=> divisible good
• U is continuous, monotone, and concave (=> convex preferences)
• endowments are positive
  where X: consumption set, U: utility function.

1. Competitive equilibrium exists under weak conditions
2. The number of equilibria is generically finite and odd.
3. Anything goes on aggregate demands and equilibrium prices.
4. The core is larger than the set of equilibrium allocations.
5. Tattonnement works only under stronger conditions on preferences.
6. Computing equilibrium prices is hard.

2: Indivisible good market: TU (transferable utility) case

2-a) Unit-good demand: homogeneous good

• Exchange economy with indivisible good + divisible good (money)
• Ex) horse market by Bohm-Bawek (1890)

Proposition (31min) — Bikhchandani and Mamer (1997) and Ma (1998)
Competitive equilibrium exists in the exchange economy if and only if it exists in the modified two-sided market. exchange economy <=> two-sided market

2-b) Unit-good demand: heterogenous good

• exchange economy <=> two-sided market = assignment market

Theorem (40min) — Koopmans and Beckman (1957)
There exists a competitive equilibrium in the assignment market.

• Proof idea: using duality. (primal => allocation; dual => prices)
  
  

Theorem (41min) — Shapley and Shubik (1971)
Competitive equilibrium outcomes coincide with the core.

• Proof idea: solving the dual problem.
  
  

Theorem (43min) — Shapley and Shubik (1971)
There exist minimum-price and maximum-price competitive equilibria.

2-c) Multi-good demand: heterogenous good

Theorem (53min) — Bikhchandani and Mamer (1997)
Competitive equilibrium exists if and only if the values of the optimal solutions to the IP and LPR coincide.

• IP: Integer Programming
• LPR: Linear Programming Relaxation
  
  

Theorem (58min) — Ma (1998)
Competitive equilibrium exists if and only if a coalitional form game in the corresponding two-sided market is balanced.

• Proof idea
  1. CE in exchange economy <=> Core in two-sided market
  2. applying Bondareva-Shapley Theorem. (balancedness is a Necessary and sufficient condition for the non-emptiness of the core)
     

Any economically interpretable conditions?

• Substitutes valuations: if the price of good k increases, then the demands for all other goods weakly increase.
  
  

Theorem (1h03min) — Kelso and Crawford (1982)
If all agents have substitutes valuations, then competitive equilibria exist.

• Proof idea:
  1. discretize prices => demand is always single-valued (on the grid).
  2. start prices very low: if more than one firm demands good k, increase k’s price.
  3. by substitutability, demand for other goods than k weakly increases.
  4. eventually, the market for each good clears.
  5. take limits, obtain equilibrium in the economy with continuous prices.
     
     

Theorem (1h09min) — Gul and Stachetti (1999)
If an agent j demands at most one unit of each good, and she does not have substitutes valuations, then there exist substitutes valuations for all other agents than j for which no competitive equilibrium exists.

• Remarks:
  1. maximum domain result may not be so useful (no story behind)
  2. if there are multiple units of some goods, then substitutes valuations are insufficient for existence.
  3. the existence of equilibrium is guaranteed by strong substitutability (each unit of a good is treated as a separate good)
     
     

Theorem (1h18min) — Sun and Yang (2006)
If agents have substitutes and complements valuations, then competitive equilibria exist.

• substitutes and complements valuations: all agents regard items in S1 as substitutes, in S2 as substitutes but any item from S1 and an item from S2 as complements. (goods are divided into two groups S1 and S2)
  
  

Theorem (1h25min) — Candogan, Ozdaglar, and Parrilo (2015) If all agents have sign-consistent tree valuations, then competitive equilibria exist.

In Lecture 3, Alex gives very general, economically interpretable conditions for the existence of equilibrium in the presence of income effects while allowing for multi-good demand.

References

1. Bohm-Bawek, E. (1890). Capital and Interest: A Critical History of Economic Theory.
2. Bikhchandani, S., & Mamer, J. W. (1997). Competitive Equilibrium in an Exchange Economy with Indivisibilities. Journal of Economic Theory, 74(2), 385-413.
3. Candogan, O., Ozdaglar, A., & Parrilo, P. A. (2015). Iterative Auction Design for Tree Valuations. Operations Research, 63(4), 751-771.
4. Gul, F., & Stacchetti, E. (1999). Walrasian Equilibrium with Gross Substitutes. Journal of Economic Theory, 87(1), 95-124.
5. Kelso Jr, A. S., & Crawford, V. P. (1982). Job Matching, Coalition Formation, and Gross Substitutes. Econometrica: 1483-1504.
6. Koopmans, T. C., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica: 53-76.
7. Ma, J. (1998). Competitive Equilibrium with Indivisibilities. Journal of Economic Theory, 2(82), 458-468.
8. Shapley, L. S., & Shubik, M. (1971). The Assignment Game I: The Core. International Journal of Game Theory, 1(1), 111-130.
9. Sun, N., & Yang, Z. (2006). Equilibria and Indivisibilities: Gross Substitutes and Complements. Econometrica, 74(5), 1385-1402.