Loading...
Please wait, while we are loading the content...
Similar Documents
Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions.
| Content Provider | CiteSeerX |
|---|---|
| Author | Garg, Jugal Mehta, Ruta Vazirani, Vijay V. |
| Abstract | After more than a decade of work in TCS on the computability of market equilibria, com-plementary pivot algorithms have emerged as the best hope of obtaining practical algorithms. So far they have been used for markets under separable, piecewise-linear concave (SPLC) utility functions [30] and SPLC production sets [31]. Can his approach extend to non-separable utility functions and production sets? A major impediment is rationality, i.e., if all parameters are set to rational numbers, there should be a rational equilibrium. Recently, [42] introduced classes of non-separable utility functions and production sets, called Leontief-free, which are applicable when goods are substitutes. For markets with these utility functions and production sets, and satisfying mild sufficiency conditions, we obtain the following results: ⢠Proof of rationality. ⢠Complementary pivot algorithms based on a suitable adaptation of Lemkeâs classic algo-rithm. ⢠A strongly polynomial bound on the running time of our algorithms if the number of goods is a constant, despite the fact that the set of solutions is disconnected. ⢠Experimental verification, which confirms that our algorithms are practical. ⢠Proof of PPAD-completeness. Next we give a proof of membership in FIXP for markets under piecewise-linear concave (PLC) utility functions and PLC production sets by capturing equilibria as fixed points of a continuous function via a nonlinear complementarity problem (NCP) formulation. Finally we provide, for the first time, dichotomies for equilibrium computation problems, both Nash and market; in particular, the results stated above play a central role in arriving at the dichotomies for exchange markets and for markets with production. We note that in the past, dichotomies have played a key role in bringing clarity to the complexity of decision and counting problems. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Non-separable Utility Function Complementary Pivot Algorithm Utility Function Production Set New Class Equilibrium Computation Piecewise-linear Concave Suitable Adaptation Polynomial Bound Lemke Classic Algo-rithm Major Impediment Following Result Central Role Exchange Market Market Equilibrium Equilibrium Computation Problem Key Role Running Time Nonlinear Complementarity Problem Experimental Verification Splc Production Set Approach Extend Practical Algorithm Plc Production Set Com-plementary Pivot Algorithm Rational Equilibrium Continuous Function Counting Problem First Time Rational Number Mild Sufficiency Condition Fixed Point |
| Content Type | Text |
