Name
Abstract | ||
|---|---|---|
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-time algorithm that approximates the market equilibrium arbitrarily closely when the number of goods is bounded and the utilities are linear. We also show a communication complexity lower bound, implying that the ideal informational economy of a market with unique individual optima is unattainable in general. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/509907.509920 | STOC |
Keywords | Field | DocType |
communication complexity,informal economy,treewidth,lower bound | Integer,Discrete mathematics,Combinatorics,Upper and lower bounds,Communication complexity,Treewidth,Mathematics,Bounded function,Information economy | Conference |
ISBN | Citations | PageRank |
1-58113-495-9 | 77 | 12.89 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaotie Deng | 1 | 3887 | 340.99 |
| Christos H. Papadimitriou | 2 | 16671 | 3192.54 |
| Shmuel Safra | 3 | 2885 | 259.32 |