Essays on the Computation of Economic Equilibria and Its Applications.

Competitive Equilibrium;PPAD;Path Auction;PageRank;Computer Science;Engineering;Computer Science & Engineering

Du, YeWellman, Michael P. ;

University of Michigan

关键词: Competitive Equilibrium;    PPAD;    Path Auction;    PageRank;    Computer Science;    Engineering;    Computer Science & Engineering;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/64821/duye_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

The computation of economic equilibria is a centralproblem in algorithmic game theory. In this dissertation, weinvestigate the existence of economic equilibria in severalmarkets and games, the complexity of computing economicequilibria, and its application to rankings.It is well known that a competitive economy always has anequilibrium under mild conditions. In this dissertation, we studythe complexity of computing competitive equilibria. We show thatgiven a competitive economy that fully respects all the conditionsof Arrow-Debreu;;s existence theorem, it is PPAD-hard to compute anapproximate competitive equilibrium. Furthermore, it is stillPPAD-Complete to compute an approximate equilibrium for economieswith additively separable piecewise linear concave utilityfunctions.Degeneracy is an important concept in game theory. We study thecomplexity of deciding degeneracy in games. We show that it isNP-Complete to decide whether a bimatrix game is degenerate.With the advent of the Internet, an agent can easily have accessto multiple accounts. In this dissertation we study the pathauction game, which is a model for QoS routing, supply chainmanagement, and so on, with multiple edge ownership. We show thatthe condition of multiple edge ownership eliminates thepossibility of reasonable solution concepts, such as astrategyproof or false-name-proof mechanism or Pareto efficientNash equilibria.The stationary distribution (an equilibrium point) of a Markovchain is widely used for ranking purposes. One of the mostimportant applications is PageRank, part of the ranking algorithmof Google. By making use of perturbation theories of Markovchains, we show the optimal manipulation strategies of a Webspammer against PageRank under a few natural constraints. Finally,we make a connection between the ranking vector of PageRank or theInvariant method and the equilibrium of a Cobb-Douglas market.Furthermore, we propose the CES ranking method based on theConstant Elasticity of Substitution (CES) utility functions.