NDLI: Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents

Content Provider	IEEE Xplore Digital Library
Author	Devanur, N.R. Kannan, R.
Copyright Year	2008
Description	Author affiliation: Microsoft Res. (Kannan, R.)
Abstract	We consider markets in the classical Arrow-Debreu model. There are n agents and m goods. Each buyer has a concave utility function (of the bundle of goods he/she buys) and an initial bundle. At an ldquoequilibriumrdquo set of prices for goods, if each individual buyer separately ex-changes the initial bundle for an optimal bundle at the set prices, the market clears, i.e., all goods are exactly consumed. Classical theorems guarantee the existence of equilibria, but computing them has been the subject of much recent research. In the related area of Multi-Agent Games,much attention has been paid to the complexity as well as algorithms. While most general problems are hard, polynomial time algorithms have been developed for restricted classes of games, when one assumes the number of strategies is constant.For the Market Equilibrium problem, several important special cases of utility functions have been tackled. Here we begin a program for this problem similar to that for multi-agent games, where general utilities are considered. We begin by showing that if the utilities are separable piece-wise linear concave (PLC) functions, and the number of goods(or alternatively the number of buyers) is constant, then we can compute an exact equilibrium in polynomial time.Our technique for the constant number of goods is to de-compose the space of price vectors into cells using certain hyperplanes, so that in each cell, each buyerpsilas threshold marginal utility is known. Still, one needs to solve a linear optimization problem in each cell. We then show the main result - that for general (non-separable) PLC utilities, an exact equilibrium can be found in polynomial time provided the number of goods is constant. The starting point of the algorithm is a ldquocell-decompositionrdquo of the space of price vectors using polynomial surfaces (instead of hyperplanes).We use results from computational algebraic geometry to bound the number of such cells. For solving the problem inside each cell, we introduce and use a novel LP-duality based method. We note that if the number of buyers and agents both can vary, the problem is PPAD hard even for the very special case of PLC utilities - namely Leontief utilities.
Starting Page	45
Ending Page	53
File Size	327350
Page Count	9
File Format	PDF
ISBN	9780769534367
ISSN	02725428
DOI	10.1109/FOCS.2008.30
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-10-25
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Programmable control Mathematical model Computer science Piecewise linear techniques Vectors Computational geometry Computational complexity Game theory economics market equilibrium exact algorithm
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Market equilibria in polynomial time for fixed number of goods or agents (2008)

Algebraic approach to Nash equilibria for finite normal form games

Electronic Colloquium on Computational Complexity, Report No. 31 (2006) On the Approximation and Smoothed Complexity of Leontief Market Equilibria

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Algebraic approach to Nash equilibria for finite normal form games

Computing pure strategy Nash equilibria in compact symmetric games (2010)

Computing Equilibria in Multi-Player Games (2004)

Games of fixed rank: a hierarchy of bimatrix games (2005).

EQUILIBRIA, FIXED POINTS, AND COMPLEXITY CLASSES (1998)

Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents

Similar Documents

Market equilibria in polynomial time for fixed number of goods or agents (2008)

Algebraic approach to Nash equilibria for finite normal form games

Electronic Colloquium on Computational Complexity, Report No. 31 (2006) On the Approximation and Smoothed Complexity of Leontief Market Equilibria

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Algebraic approach to Nash equilibria for finite normal form games

Computing pure strategy Nash equilibria in compact symmetric games (2010)

Computing Equilibria in Multi-Player Games (2004)

Games of fixed rank: a hierarchy of bimatrix games (2005).

EQUILIBRIA, FIXED POINTS, AND COMPLEXITY CLASSES (1998)

Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents