0f2ba7df071819e9f16ef25833cf9c6d.jpeg

# Algorithmic Game Theory - Lecture 1 Instructor: Yannai Gonczarowski TAs: Gal Yehoshua, Tomer Ezra, Guy Tennenholtz ## What is Game Theory? ### John Nash - Graduate Student at Princeton - PhD Dissertation: Non-cooperative Games (1950) - Nobel Prize in Economics (1994) - Inspiration for "A Beau...

# Algorithmic Game Theory - Lecture 1 Instructor: Yannai Gonczarowski TAs: Gal Yehoshua, Tomer Ezra, Guy Tennenholtz ## What is Game Theory? ### John Nash - Graduate Student at Princeton - PhD Dissertation: Non-cooperative Games (1950) - Nobel Prize in Economics (1994) - Inspiration for "A Beautiful Mind" ### Definition Game theory is the study of mathematical models of strategic interactions among rational agents. ### Strategic Interaction The key aspect is that each agent's utility depends not only on its own action but also on the actions of other agents. ### Rationality Each agent acts to maximize its own utility. ### Selfishness vs. Altruism While game theory often assumes agents are purely self-interested, it can also model altruism and other social preferences. ### Examples - Auctions - Negotiations - Congestion Games - Network Routing - Kidney Exchange - Social Networks - Security Games ### Algorithmic Game Theory (AGT) An interdisciplinary field that lies at the intersection of game theory and computer science. ### Computation - How to compute solution concepts in games? - What is the computational complexity? - Can we design efficient algorithms? ### Design - How can we design games to achieve desirable outcomes? - What are the right incentives to align individual and social goals? ### This Course - Mechanism Design - Social Choice - Fair Division - Price of Anarchy ## Self-Interested Agents ### Example: Routing Game - $n$ agents want to travel from S to T. - Each agent chooses a path. - The cost of a path is the sum of the costs of the edges on the path. - Each agent wants to minimize its own cost. ### Socially Optimal Outcome Minimize the total cost of all agents. ### Selfish Outcome Each agent chooses a path that minimizes its own cost, given the choices of the other agents. ### Terminology - **Players / Agents:** The individuals making decisions. - **Strategies:** The possible choices available to each player. - **Utilities / Payoffs:** The numerical value representing the outcome for each player based on the strategies chosen by all players. - **Strategy Profile:** A set of strategies, one for each player. - **Social Welfare:** The sum of the utilities of all players. - **Cost:** Negative utility. ## Example: Prisoner's Dilemma Two suspects are arrested for a crime. They are held in separate cells and cannot communicate. The police offer each suspect the following deal: - If you confess and your accomplice does not, you go free, and your accomplice gets 10 years. - If you both confess, you each get 5 years. - If you do not confess and your accomplice does, you get 10 years, and your accomplice goes free. - If neither of you confesses, you each get 1 year. ### Payoff Matrix | | Suspect B Confesses | Suspect B Stays Silent | | :---------- | :------------------ | :--------------------- | | Suspect A Confesses | -5, -5 | 0, -10 | | Suspect A Stays Silent | -10, 0 | -1, -1 | ### Analysis - Each player's dominant strategy is to confess. - The Nash Equilibrium is for both players to confess. - The socially optimal outcome is for both players to stay silent. ## Nash Equilibrium ### Definition A strategy profile where no player can improve its utility by unilaterally changing its strategy, assuming the other players' strategies remain fixed. ### Notation - $n$ players $\{1, 2,..., n\}$ - $S_i$ is the set of strategies for player $i$ - $s_i \in S_i$ is a strategy for player $i$ - $s = (s_1, s_2,..., s_n)$ is a strategy profile - $s_{-i} = (s_1,..., s_{i-1}, s_{i+1},..., s_n)$ is a strategy profile without player $i$'s strategy - $u_i(s)$ is the utility of player $i$ in strategy profile $s$ ### Formal Definition A strategy profile $s = (s_1, s_2,..., s_n)$ is a Nash Equilibrium if for every player $i$ and every strategy $s_i' \in S_i$: $u_i(s_i, s_{-i}) \ge u_i(s_i', s_{-i})$ ### Alternate Definition A strategy profile $s = (s_1, s_2,..., s_n)$ is a Nash Equilibrium if for every player $i$: $s_i \in \argmax_{s_i' \in S_i} u_i(s_i', s_{-i})$ ### Examples - Prisoner's Dilemma: (Confess, Confess) is a Nash Equilibrium. - Routing Game: A strategy profile where each agent chooses a shortest path given the congestion caused by other agents is a Nash Equilibrium. ## Existence of Nash Equilibria ### Theorem (Nash, 1950) Every game with a finite number of players and a finite number of strategies has at least one Nash Equilibrium (possibly in mixed strategies). ### Mixed Strategy A probability distribution over the set of pure strategies. ### Example: Matching Pennies Two players simultaneously choose to show heads (H) or tails (T). If the choices match, player 1 wins. If the choices differ, player 2 wins. ### Payoff Matrix | | Player 2: H | Player 2: T | | :---- | :---------- | :---------- | | Player 1: H | 1, -1 | -1, 1 | | Player 1: T | -1, 1 | 1, -1 | ### Analysis - There is no pure strategy Nash Equilibrium. - The mixed strategy Nash Equilibrium is for each player to choose H with probability 1/2 and T with probability 1/2. ## Next Time - Price of Anarchy - Mechanism Design