IMG_0009.jpeg

# Algorithmic Game Theory ## What is Game Theory? * Study of how people behave in strategic situations * **Strategic situation**: One in which each person's outcome depends on the choices of others * Developed extensively by mathematicians and used by economists, political scientists, etc...

# Algorithmic Game Theory ## What is Game Theory? * Study of how people behave in strategic situations * **Strategic situation**: One in which each person's outcome depends on the choices of others * Developed extensively by mathematicians and used by economists, political scientists, etc. ### Examples * Firms trying to decide how much to produce * Union and management bargaining over contracts * Divorce * Auctions ### What is a game? A **game** is a formal description of a strategic situation * Set of players * Set of possible actions for each player * Specification of payoffs for each combination of strategies ### Types of games * Cooperative vs. Non-cooperative * Symmetric vs. Asymmetric * Perfect vs. Imperfect information * Simultaneous vs. Sequential * Zero-sum vs. Non-zero-sum ## What is Algorithmic Game Theory? * Intersection of Game Theory and Algorithm Design * Uses solution concepts from Game Theory * Addresses questions motivated by Computer Science ### Why is it important? * The Internet has changed the scale of many strategic interactions * Need to worry about computational efficiency * New issues arise because of the distributed ownership and lack of central control on the Internet ### Examples * **Sponsored search auctions**: Google, Yahoo!, and MSN make billions of dollars selling advertisement slots via auctions * **Network routing**: How to avoid congestion when traffic is routed by selfish users * **Peer-to-peer networks**: How to provide incentives so that users share resources ## Example: The Prisoner's Dilemma ### Story Two suspects are arrested for a crime. They are questioned in separate rooms. If they both cooperate (remain silent), then they will each serve a short prison sentence. If one defects (confesses) and the other cooperates, then the defector will be released, and the cooperator will serve a long prison sentence. If they both defect, then they both serve an intermediate sentence. ### Matrix | | Cooperate | Defect | | :-------- | :-------- | :--------- | | Cooperate | -1, -1 | -10, 0 | | Defect | 0, -10 | -5, -5 | *(Row player's payoff, Column player's payoff)* ### Lesson In the Prisoner's Dilemma, defecting is a **dominant strategy**: regardless of what the other player does, it is always better to defect. If both players are rational, then they will both defect. But this outcome is worse for both players than if they had both cooperated! ## Solution Concepts ### What is a Solution Concept? * A rule for predicting how a game will turn out * Specifies a set of outcomes that are considered *reasonable* ### Nash Equilibrium * Most well-known solution concept * An outcome is a Nash Equilibrium if no player has an incentive to deviate, given that the other players do not deviate * Equivalently: Each player's strategy is a best response to the other players' strategies * Every game has at least one Nash Equilibrium (if we allow mixed strategies) ### Examples * In the Prisoner's Dilemma, (Defect, Defect) is the only Nash Equilibrium ### Pareto Optimal An outcome is **Pareto Optimal** if there is no other outcome that makes every player at least as well off and at least one player strictly better off. ### Examples * In the Prisoner's Dilemma, (Cooperate, Cooperate) is Pareto Optimal ### Other Solution Concepts * Dominant Strategy Equilibrium * Minmax Strategy * Correlated Equilibrium * Bayesian-Nash Equilibrium * Social Welfare Maximization * Mechanism Design * Price of Anarchy *** The image presents an introduction to Algorithmic Game Theory. It begins by defining Game Theory as the study of strategic interactions, providing examples such as firms deciding on production levels, union-management bargaining, divorce, and auctions. A game is formally defined, including players, actions, and payoffs. Different game types are mentioned, such as cooperative versus non-cooperative, symmetric versus asymmetric, perfect versus imperfect information, simultaneous versus sequential, and zero-sum versus non-zero-sum. Algorithmic Game Theory is then described as the intersection of Game Theory and Algorithm Design, highlighting its importance due to the scale of Internet-based strategic interactions and the need for computational efficiency The lecture gives the example of the Prisoner's Dilemma, detailing the scenario and presenting a payoff matrix to illustrate the outcomes of cooperation and defection. It shows that defecting is a dominant strategy, leading to a suboptimal outcome for both players. The presentation moves on to Solution Concepts, defining them as rules for predicting game outcomes and specifying reasonable results. The Nash Equilibrium, the well-known solution is defined. It is stated that every game has at least one Nash Equilibrium (with mixed strategies). The concept of Pareto Optimality is introduced, defining it as an outcome where no player can be made better off without making another player worse off. Finally, a list of other solution concepts is provided: Dominant Strategy Equilibrium, Minmax Strategy, Correlated Equilibrium, Bayesian-Nash Equilibrium, Social Welfare Maximization, Mechanism Design, and Price of Anarchy.