Vous êtes ici

Accueil » Expert profile — Profil d'expert

Expert profile — Profil d'expert

Portrait de axjiang
Albert Xin Jiang
Champ d'expertise principal
Game Theory
Note biographique
I am broadly interested in computational problems arising in economics (especially game theory and mechanism design). The topic of my PhD thesis is on the theoretical and practical aspects of the computation of game-theoretic solution concepts such as Nash equilibrium, Stackelberg equilibrium and correlated equilibrium. My approach can roughly be divided into two streams:
1. Development of compact representations of game-theoretic models.
This is motivated by the observation that while the standard representation of games as multi-dimensional tables is impractical due to the curse of dimensionality, most real-world games of interest have structured utility functions. I am involved in the development and analysis of Action-Graph Games (AGGs), a fully-expressive modeling language for representing simultaneous-move games. When utility functions exhibit commonly-encountered structure such as context-specific independence, anonymity and additivity, AGGs can represent such games compactly, i.e. using small numbers of bits. For a detailed introduction of AGGs, please see our paper in Games and Economic Behavior (joint work with Kevin Leyton-Brown and Navin Bhat). Recently, we have extended the AGG framework to represent games of incomplete information (joint with Kevin Leyton-Brown) and dynamic games (joint with Kevin Leyton-Brown and Avi Pfeffer). For more information on AGGs and extensions, see the AGG Project website.
2. Design and analysis of efficient algorithms for computing Nash and correlated equilibria given a compactly represented game.
A common subproblem is the computation of expected utility given an arbitrary mixed-strategy profile. For AGGs and their extensions, we provide efficient algorithms for this, and leverage these algorithms to achieve exponential speedups of existing algorithms for finding sample Nash equilibria. Software implementations are available at the AGG Project website. I am also interested in the problem of computing pure-strategy Nash equilibria for graphical game representations including AGGs and graphical games. When the associated graphs have bounded treewidth, techniques based on tree decomposition and dynamic programming are often applicable, while for classes of graphs with unbounded treewidth it is possible to prove hardness results. I am also interested in the computation of correlated equilibria and Stackelberg equilibira. For more details please see my list of publications.