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 noncooperatively 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 noncooperation approximates cooperation. It is defined as the worstcase 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): If exactly one of the thieves cooperates with police, then he will be freed and his buddy will be imprisoned for 6 years.
 If both thieves cooperate with the police, then both of them will be imprisoned for 5 years.
 If both thieves deflect the deal, then both of them will get only a small punishment (1 year) because of lack of proof.



  
Thief B      
    
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