On the complexity of equilibria in games with succinct representation [Elektronische Ressource] / vorgelegt von Alexander Skopalik

On the Complexity of Equilibria inGames with Succinct RepresentationVon der Fakultat fur Mathematik, Informatik und Naturwissenschaften der¨ ¨RWTH Aachen University zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerAlexander Skopalikaus Frankfurt am MainBerichter: Universitatsprofessor Dr. Berthold Vocking¨ ¨Universitatsprofessor Dr. Burkhard Monien¨Tag der mu¨ndlichen Pru¨fung: 31. August 2010Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨gbar.iiAbstractAlgorithmic game theory studies computational and algorithmicquestions arising from the behavior of players in strategic situations.The computational aspects of game theory became subject to closerscrutiny in the last two decades. One reason for this is certainly theadventoflargescalecommunicationnetworks –mostprominently theInternet. Modern technology allows to monitor, evaluate, and influ-ence the behavior of interacting agents in large systems. One maythink of many (future) applications including distribution of goodsand services in auctions, allocationofresources, routing ofdata pack-ages, or regulation of vehicle traffic. One of the main contributions ofgame theory is the ability to predict how these games will be played.The most commonly used solution concepts are equilibrium conceptsthat describe which strategies will be adopted by players.