Game Theory: Prisoner's Dilemma

• Game theory provides a mathematical framework to analyze strategic interactions between decision-makers (players).
• In game theory, each player seeks to optimize their outcome/payoff based on their actions and the actions of others.
• Game theory has applications in economics, political science, biology, and computer science.

Prisoner's Dilemma

• Two suspects cannot communicate and are offered a deal.
• If one confesses and the other doesn't, the confessor is freed and the other gets 10 years.
• If both confess, they each get 5 years.
• If neither confesses, they each get 1 year.

• The dominant strategy in the Prisoner's Dilemma is to confess, regardless of the other player's action.
• If both confess, they each receive 5 years, while if neither confesses, they each receive 1 year.
• A Nash Equilibrium is when both players confess.
• The socially optimal outcome is when neither confesses.

Algorithmic Game Theory (AGT)

• AGT combines game theory and computer science.
• AGT addresses the computational aspects of game theory.
• AGT explores efficient computation of solutions in games.
• AGT delves into designing computationally tractable games.
• AGT considers how to deal with incomplete information.
• AGT addresses strategic behavior in networks.
• AGT aims to cope with the dynamic nature of games.

Key Concepts in AGT

• Mechanism Design: Designs game rules to achieve desired outcomes with self-interested players.
• Price of Anarchy: Measures social welfare loss due to players' selfishness in a system.
• Computation of Equilibria: Focuses on efficiently computing Nash equilibria.
• Learning in Games: Explores how players learn to play well in repeated games with limited information.
• Game Theory on Networks: Examines how network structure affects strategic interactions.

Applications of AGT

• Designing efficient and incentive-compatible auctions for Internet Advertising.
• Minimizing congestion in Network Routing with selfish users.
• Designing market mechanisms that encourage sellers to offer high-quality products at competitive prices in E-commerce.
• Understanding spread of information and influence in Social Networks, accounting for strategic behavior.
• Allocating resources efficiently and fairly using Cloud Computing.

Course Outline

• Introduction
• Normal Form Games
• Mechanism Design without Money
• Sponsored Search Auctions
• The VCG Mechanism
• Revenue Maximization
• Social Choice
• Coalitional Game Theory
• The Shapley Value
• Fair Division
• Price of Anarchy
• Congestion Games
• The Braess Paradox
• Learning in Games