Home / research areas / AGT
Algorithmic Game Theory
Game theory studies the behavior of rational agents in scenarios with possible conflict or cooperation. Such agents are known as players and may present different behavior depending on their objective. This objective is usually modeled as a objective function, or utility. While each player tries to maximize their individual objective, this objective can be affected by the behavior of the other players. This scenario where the players must make decisions is called a game, and it models the possible actions and strategies each player can use in order to maximize his objective. A strategy for a game is a (Nash) equilibrium if no player has an incentive to change their individual strategy, i.e. no mater what changes in the behavior of a player, he can’t improve his utility. There are several areas of knowledge where game theory has applications, such as economy, politic science, international relations, biology, ecology and computer science. Examples of these applications include design of voting protocols, trustworthy auctions and fairness in resource allocation. For computer science, game theory has proved to be a important tool to the analysis of problems found on distributed and scalable systems, such as the Internet. By the same token, areas of computer science such as complexity theory have shown to be powerful tools to build, test and analyze typical scenarios found in game theory. Many questions arise when analyzing games from game theory from a algorithmic point of view. For a given game, is there a way to reach a Nash equilibrium in polynomial time? What is the difference between the possible Nash equilibria that a game may have? How good is a equilibrium when compared to a solution where a central entity can control all the players? Furthermore, is it possible to change the game in such a way as to guarantee a certain property or output from the players? This interaction between computer science and game theory is denominated Algorithmic Game Theory. John Forbes Nash Jr., one of the most influential researchers in game theory and winner of the Nobel Prize in economics in 1994, said, during the Brazilian Workshop on Game Theory (from agencia FAPESP, in Portuguese):
“Certamente algo que será pesquisado intensamente de agora em diante é um desenvolvimento cada vez maior da interface entre Computação e Teoria dos Jogos. É algo que está crescendo e se tornando um campo à parte.”
Problems:
- Load balancing (in grid computing, for example);
- Routing in networks (where no single entity selects all paths, i.e. there are multiple entities choosing paths);
- Combinatorial auctions (multiple items or services sale, such as space and processing time in cloud computing);
- Advertising auctions (sale of advertising slots in search mechanisms (Google, Yahoo!) and social networks (Facebook, LinkedIn);
- Development of new network protocols;
- Multi-agent systems.
References:
- Nisan, Rougharden, Tardos e Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. PDF.
- Noan Nisan. Algorithmic Game Theory and Economics Blog. http://agtb.wordpress.com.
- Yoav Shoham. Computer Science and Game Theory. Communications of the ACM archive Volume 51, Issue 8, 2008. Excellent introductory paper.
- Narahari, Garg, Narayanam e Prakash. Game Theoretic Problems in Network Economics and Mechanism Design Solutions. Springer, 2009. Amazon.