Computational Aspects of Game Theory and Microeconomics

Abstract

The purpose of this thesis is to study algorithmic questions that arise in the context of game theory and microeconomics. In particular, we investigate the computational complexity of various economic solution concepts by using and advancing methodologies from the fields of combinatorial optimization and approximation algorithms. We first study the problem of allocating a set of indivisible goods to a set of agents, who express preferences over combinations of items through their utility functions. Several objectives have been considered in the economic literature in different contexts. In fair division theory, a desirable outcome is to minimize the envy or the envy-ratio between any pair of players. We use tools from the theory of linear and integer programming as well as combinatorics to derive new approximation algorithms and hardness results for various types of utility functions. A different objective that has been considered in the context of auctions, is to find an allocation that maximizes the social welfare, i.e., the total utility derived by the agents. We construct reductions from multi-prover proof systems to obtain inapproximability results, given standard assumptions for the utility functions of the agents. We then consider equilibrium concepts in games. We derive the first subexponential algorithm for computing approximate Nash equilibria in $2$-player noncooperative games and extend our result to multi-player games. We further propose a second algorithm based on solving polynomial equations over the reals. Both algorithms improve the previously known upper bounds on the complexity of the problem. Finally, we study game theoretic models that have been introduced recently to address incentive issues in Internet routing. A polynomial time algorithm is obtained for computing equilibria in such games, i.e., routing schemes and payoff allocations from which no subset of agents has an incentive to deviate. Our algorithm is based on linear programming duality theory. We also obtain generalizations when the agents have nonlinear utility functions.