Efficient Decentralised Approaches in Algorithmic Game Theory

Lead Research Organisation: University of Warwick
Department Name: Computer Science

Abstract

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.Work in Computer Science has attracted considerable interest from the Game Theory community. Computer scientists have developed analytical tools to understand the speed and efficiency of a computational process, and the inherent difficulty of computational problems. This provides new criteria for judging alternative solution concepts in Game Theory, and the algorithms that have been proposed to find them. The field of Distributed Computation has provided useful mathematical models of the interaction amongst the players in a game. This cross-fertilisation is very much a two-way process, since at the same time, computer scientists have applied game-theoretic concepts to model large-scale interactions on the Internet, electronic marketplaces, and interactions amongst computational agents (in the context of AI).So far, many of the algorithms that have been proposed to compute the outcomes of games, have the drawback that the algorithm essentially coordinates the behaviour of the players in a centralised manner. Decentralisation refers to the development of algorithms that are used by multiple players (or agents) in the absence of any central control. The development of these algorithms requires models of precisely how the players interact (and various models have been proposed for this purpose). This research agenda gives rise to a large number of important and interesting problems, which essentially ask: What assumptions have to be made about how players interact, in order for solutions to be found rapidly? This research aims to develop novel algorithms that find solutions efficiently, and in a decentralised manner. We also seek a better understanding of the general limitations on what can be achieved by provably efficient algorithms (characterised mathematically as algorithms that run in polynomial time).Generally, we are interested in solutions that can be found by algorithms that are both efficient and decentralised. Solutions that can be found by such algorithms are arguably more realistic than other solution concepts. The research outlined in this proposal will apply to games that model large-scale interactions amongst many players, as well as standard normal-form games.

Publications

10 25 50
publication icon
Hansen K (2010) Algorithmic Game Theory

publication icon
Aziz H (2011) Path Coalitional Games

publication icon
Goldberg P (2011) Algorithms - ESA 2011

publication icon
Karanikolas N (2011) Solution to Exchanges 9.1 puzzle borrowing as cheaply as possible in ACM SIGecom Exchanges

publication icon
Goldberg P (2012) On the approximation performance of fictitious play in finite games in International Journal of Game Theory

publication icon
Fearnley J (2012) Algorithmic Game Theory

publication icon
Troels Bjerre Sorensen (Author) (2012) Repeated zero-sum games with budget

publication icon
Czumaj A (2014) Algorithmic Game Theory

 
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