In the last decade, there has been much research at the interface of computer science and game theory. One important class of problems at this interface is the computation of solution concepts (such as Nash equilibrium or correlated equilibrium) of a finite game. In order to take advantage of the highly-structured utility functions in games of practical interest, it is important to design compact representations of games as well as efficient algorithms for computing solution concepts on such representations. In this thesis I present several novel contributions in this direction: The design and analysis of Action-Graph Games (AGGs), a fully-expressive modeling language for representing simultaneous-move games. We propose a polynomial-time algorithm for computing expected utilities given arbitrary mixed strategy profiles, and leverage the algorithm to achieve exponential speedups of existing algorithms for computing Nash equilibria. Designing efficient algorithms for computing pure-strategy Nash equilibria in AGGs. For symmetric AGGs with bounded treewidth our algorithm runs in polynomial time. Extending the AGG framework beyond simultaneous-move games. We propose Temporal Action-Graph Games (TAGGs) for representing dynamic games and Bayesian Action-Graph Games (BAGGs) for representing Bayesian games. For certain subclasses of TAGGs and BAGGs we gave efficient algorithms for equilibria that achieve exponential speedups over existing approaches. Efficient computation of correlated equilibria. In a landmark paper, Papadimitriou and Roughgarden described a polynomial-time algorithm ("Ellipsoid Against Hope") for computing sample correlated equilibria of compactly-represented games. Recently, Stein, Parrilo and Ozdaglar showed that this algorithm can fail to find an exact correlated equilibrium. We present a variant of the Ellipsoid Against Hope algorithm that guarantees the polynomial-time identification of exact correlated equilibrium. Efficient computation of optimal correlated equilibria. We show that the polynomial-time solvability of what we call the deviation-adjusted social welfare problem is a sufficient condition for the tractability of the optimal correlated equilibrium problem. ; Science, Faculty of ; Computer Science, Department of ; Graduate


    Access

    Download


    Export, share and cite



    Title :

    Representing and reasoning with large games


    Contributors:
    Jiang, Xin (author)

    Publication date :

    2011-01-01


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629




    Robotic Agents Representing, Reasoning, and Executing Wiping Tasks for Daily Household Chores

    Leidner, Daniel / Bejjani, Wissam / Albu-Schäffer, Alin et al. | German Aerospace Center (DLR) | 2016

    Free access

    Representing Knowledge of large-scale space

    Kuipers, Benjamin Jack | TIBKAT | 1977


    Representing Women

    Brown, Douglas | Emerald Group Publishing | 1999


    Representing Reich

    Online Contents | 2012


    Reflection plate representing ground

    Stalker, E.A. | Engineering Index Backfile | 1934