Efficient Decentralised Approaches in Algorithmic Game Theory
Lead Research Organisation:
University of Warwick
Department Name: Computer Science
Abstract
Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
Organisations
People |
ORCID iD |
| Artur Czumaj (Principal Investigator) |
Publications
Goldberg P
(2012)
On the approximation performance of fictitious play in finite games
in International Journal of Game Theory
Aziz H
(2011)
Path Coalitional Games
Troels Bjerre Sorensen (Author)
(2012)
Repeated zero-sum games with budget
Fearnley J
(2010)
SOFSEM 2010: Theory and Practice of Computer Science
Karanikolas N
(2011)
Solution to Exchanges 9.1 puzzle borrowing as cheaply as possible
in ACM SIGecom Exchanges
Czumaj A
(2016)
Web and Internet Economics
Czumaj A
(2017)
Zero-Sum Game Techniques for Approximate Nash Equilibria
| Description | Game theory is the mathematical analysis of competitive (more generally, non-cooperative) situations, and is frequently studied in the context of mathematics and economics. A "solution concept" (such as Nash equilibrium, or correlated equilibrium) is a mathematical description of the outcome of a game - the set of choices made by all players, or participants. Many algorithms have been proposed (and implemented as programs) to compute these solutions. The main contribution of the research funded by this grant is a series of research papers advancing our understanding of the computational complexity and structure of solution concepts in multiplayer games. The project, which was run jointly with researchers from the U. Liverpool, led to several significant advances in algorithmic game theory. One of the core topics of modern algorithmic game theory is to understand equilibrium refinements. The EC'2012 paper resolves an important open problem in this area by showing that computing a proper equilibrium of a bimatrix game is in the complexity class PPAD. This is achieved by designing the first pivoting-type algorithm to find an exact proper equilibrium of a bimatrix game. The same technique can be applied to matrix games, thereby computing a parameterised epsilon-proper strategy in polynomial time using linear programming. Perhaps the most known refinement of Nash equilibrium is trembling hand perfection. In the SAGT'2012 paper, we study the complexity of this approach and show that it is NP-hard and Sqrt-Sum-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoff is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, sequential equilibrium, quasi-perfect equilibrium and CURB. Another paper (ESA'2011), which is a joint collaboration with the project's partner U. Liverpool, studies the performance of Fictitious Play, a heuristic for finding an approximate Nash equilibrium of a two-player game. The paper gives a full characterization of the quality of approximation of this heuristic: (i) it exhibits a class of two-player games having payoffs in the range [0,1] for which Fictitious Play fails to find a solution having an additive approximation guarantee significantly better than 1/2, and then (ii) it shows an essentially matching upper bound of 1/2-O(1/n). Another central theme of this project is the study of the quality of repeated games. In the AAMAs'2012 paper, we consider this concept in the framework of repeated zero-sum games. When a zero-sum game is played once, a risk-neutral player will want to maximize his expected outcome in that single play. However, if that single play instead only determines how much one player must pay to the other, and the same game must be played again, until either player runs out of money, optimal play may differ. Optimal play may require using different strategies depending on how much money has been won or lost. Computing these strategies is rarely feasible, as the state space is often large. This can be addressed by playing the same strategy in all situations, though this will in general sacrifice optimality. Purely maximizing expectation for each round in this way can be arbitrarily bad. To address this issue, we propose a new solution concept that has guaranteed performance bounds and provide an efficient algorithm for computing it. In the next paper, published at SODA'2012 by Lachish and his collaborator, we present a new algorithm for the so-called matroid secretary problem, the problem closely related to welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid. The paper makes a major step forward in our understanding of the problem and gives the first algorithm for the problem that achieves sublogarithmic competitive ratio (as a function of the rank of the matroid). Further advances in the area of the project has been made recently (after the expiration of the funding), with publications of Czumaj, Fasoulakis, Jurdzinski. This strand of research focuses on the fundamental question of efficiently finding good Nash equilibrium of the games. |
| Exploitation Route | The project was of fundamental flavor, and there are major research activities in the scientific communities focusing on the topics investigated in the proposal. While fundamental research typically originates in the university environment, a lot of research is later taken over by major high-tech companies and game theory and AI projects, to work on further implementations of related research in practice. |
| Sectors | Digital/Communication/Information Technologies (including Software),Other |