Computing Market Equilibria
Stub. Combinatorial primal-dual algorithms and convex-programming approaches to Fisher and Arrow-Debreu market equilibria; the Eisenberg-Gale program, tight sets, balanced flows, WGS exchange economies. (AGT ch. 5-6)
Merges Vazirani’s combinatorial primal-dual algorithms for linear Fisher and Arrow-Debreu markets with Codenotti-Varadarajan’s convex-programming view of market equilibria more generally (homogeneous consumers, exchange economies satisfying weak gross substitutability, models with production). Two complementary lenses on the same question: when do market equilibria exist and how fast can they be computed.
Outline (TODO — flesh out each)
- Fisher’s linear case and the Eisenberg-Gale convex program
- Checking whether given prices are equilibrium prices
- The primal-dual schema: tight sets, the invariant, balanced flows
- Main combinatorial algorithm, finding tight sets, running time
- The linear Arrow-Debreu model; an auction-based algorithm
- Resource allocation / single-source multiple-sink markets
- Fisher model with homogeneous consumers (convex-programming view)
- Exchange economies satisfying WGS; specific utility functions
- Limitations of the convex-programming approach; models with production