Universität Paderborn - Home Universität Paderborn
Die Universitä der Informationsgesellschaft

Algorithmic Game Theory



Framework

Apparently, it is in human's nature to act selfishly. Game Theory, founded by von Neumann and Morgenstern, provides us with strategic games, an important mathematical model to describe and analyze such a selfish behavior and its resulting conflicts. In such a game, a finite set of players is considered. Each player is allowed to choose a strategy from its strategy set. This choice is done once and for all, and all players' choices are made non-cooperatively and simultaneously (that is, when choosing a strategy each player is not informed of the strategies chosen by any other player). Each player aims for an optimal value of its private objective function which depends not only on its choice but also on the choices of the other players. One of the basic assumption in strategic games is that the players act rational, that is, consistently in pursuit of their private objective function.

One of the most widely used solution concepts for strategic games is the concept of Nash equilibrium. It represents a stable state in which no player has an incentive to unilaterally change its strategy in order to improve the value of its private objective function. A Nash equilibrium is pure if each player employs a pure strategy, that is, one single strategy from its strategy set. A Nash equilibrium is mixed if each player employs a mixed strategy, that is, a probabilty distribution over pure strategies. Many algorithms have been developed to compute a Nash equilibrium. Though the celebrated results of Nash ensure the existence of a mixed Nash equilibrium, the complexity to compute such a Nash equilibrium is widely unknown. Papadimitriou advocates it to be "the most important concrete open question on the boundary of P today."

Not only the computational complexity of Nash equilibria is of interest, but also the degradation of the social welfare of the system due to the selfish behavior of the players. In order to measure this social welfare, a global objective function, usually coined as social cost, is considered. The price of anarchy, also called coordination ratio, measures the extent to which non-cooperation approximates cooperation. It is defined as the worst-case ratio between the value of social cost in a Nash equilibrium and that of some social optimum.

Another challenge of algorithmic game theory is to design games with desirable properties. This topic is termed mechanism design. The main focus of mechanism design is to construct games for which revealing private information is a dominant strategy for each agent, i.e., maximizes his objective function regardless of the other agents' actions.

Example: The Prisoner's Dilemma:

Consider the following situation: two thieves are arrested by the police under the suspicion of having burgled a jewelry store. However, the police does not have sufficient proof in order to have them convicted. Thus, the two thieves are interrogated separately, and the police offers them a deal (see Table below): Clearly, each of the thieves (as his private objective function) tries to minimize the number of years to be spent in prison. Moreover, a natural definition of social cost is the sum of years to be spent in prison by the thieves.

Thief A
Cooperate
Deflect
Thief B
Cooperate
5 years
5 years
acquittal
6 years
Deflect
6 years
acquittal
1 years
1 years

It is easy to see that social cost is minimum if both thieves deflect the deal. In this case, both of them would spend only 1 year in prison, and the social cost is 2 years. However, this state is not a Nash equilibrium since each of the thieves can decrease the number of years to be spent in prison from 1 to 0 (that is, he will be acquitted) by unilaterally changing his strategy. In the only pure Nash equilibrium both thieves cooperate, and the social cost of this Nash equilbrium is 10 years.

Applications



Contact

Rainer Feldmann (obelix@upb.de)
Martin Gairing (gairing@upb.de).

Index A – Z | Impressum | Webmaster | Modified: 10.05.2007