On the complexity of price equilibria

✍ Scribed by Xiaotie Deng; Christos Papadimitriou; Shmuel Safra

• Book ID: 104147671
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 191 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00011-4

✦ Synopsis

We prove complexity, approximability, and inapproximability results for the problem of finding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial algorithm that approximates the market equilibrium arbitrarily close when the number of goods is bounded and the utilities linear. We also show a communication complexity lower bound in a model appropriate for markets. Our result implies that the ideal informational economy of a market with divisible goods and unique optimal allocations is unattainable in general.