Essays on the Computation of Economic Equilibria and Its Applications.

Abstract

The computation of economic equilibria is a central problem in algorithmic game theory. In this dissertation, we investigate the existence of economic equilibria in several markets and games, the complexity of computing economic equilibria, and its application to rankings.

It is well known that a competitive economy always has an equilibrium under mild conditions. In this dissertation, we study the complexity of computing competitive equilibria. We show that given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, it is PPAD-hard to compute an approximate competitive equilibrium. Furthermore, it is still PPAD-Complete to compute an approximate equilibrium for economies with additively separable piecewise linear concave utility functions.

Degeneracy is an important concept in game theory. We study the complexity of deciding degeneracy in games. We show that it is NP-Complete to decide whether a bimatrix game is degenerate.

With the advent of the Internet, an agent can easily have access to multiple accounts. In this dissertation we study the path auction game, which is a model for QoS routing, supply chain management, and so on, with multiple edge ownership. We show that the condition of multiple edge ownership eliminates the possibility of reasonable solution concepts, such as a strategyproof or false-name-proof mechanism or Pareto efficient Nash equilibria.

The stationary distribution (an equilibrium point) of a Markov chain is widely used for ranking purposes. One of the most important applications is PageRank, part of the ranking algorithm of Google. By making use of perturbation theories of Markov chains, we show the optimal manipulation strategies of a Web spammer against PageRank under a few natural constraints. Finally, we make a connection between the ranking vector of PageRank or the Invariant method and the equilibrium of a Cobb-Douglas market. Furthermore, we propose the CES ranking method based on the Constant Elasticity of Substitution (CES) utility functions.