hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT,
Abstract:
We present a combinatorial algorithm for determining the market clearing
prices of a general linear Arrow-Debreu market, where every agent can own
multiple goods. The existing combinatorial algorithms for linear Arrow-Debreu
markets consider the case where each agent can own all of one good only. We
present an $\tilde{\mathcal{O}}((n+m)^7 \log^3(UW))$ algorithm where $n$, $m$,
$U$ and $W$ refer to the number of agents, the number of goods, the maximal
integral utility and the maximum quantity of any good in the market
respectively. The algorithm refines the iterative algorithm of Duan, Garg and
Mehlhorn using several new ideas. We also identify the hard instances for
existing combinatorial algorithms for linear Arrow-Debreu markets. In
particular we find instances where the ratio of the maximum to the minimum
equilibrium price of a good is $U^{\Omega(n)}$ and the number of iterations
required by the existing iterative combinatorial algorithms of Duan, and
Mehlhorn and Duan, Garg, and Mehlhorn are high. Our instances also separate the
two algorithms.
