IMG_2691.jpeg

# Algorithmic Game Theory ## What is Game Theory? **Game theory** is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. ### Main applications - Economi...

# Algorithmic Game Theory ## What is Game Theory? **Game theory** is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. ### Main applications - Economics - Political Science - Biology - Computer Science ### Cooperative vs Non-Cooperative - **Cooperative Game Theory**: Players form coalitions and work together to achieve a common goal. - **Non-Cooperative Game Theory**: Players act independently, each pursuing their own self-interest. ### Representation of games 1. **Normal Form**: A normal form game is represented by a matrix that shows the players, strategies, and payoffs associated with each strategy. 2. **Extensive Form**: An extensive form game is a detailed description of the sequence of events in a game, including the choices the players can make at each point. ## Normal Form Game A normal form game is defined by: - A set of players $N = \{1, 2,..., n\}$ - For each player $i$, a set of actions $A_i$ - For each player $i$, a utility function $u_i: A_1 \times... \times A_n \rightarrow \mathbb{R}$ ### Example: Prisoner's Dilemma Two suspects are arrested for a crime. They are held in separate cells and cannot communicate with each other. The police offer each suspect a deal: - If one confesses and the other does not, the confessor goes free and the other gets 10 years in prison. - If both confess, they each get 5 years in prison. - If neither confesses, they each get 1 year in prison. | | **Suspect B Confesses** | **Suspect B Doesn't Confess** | | :---------- | :----------------------: | :-----------------------------: | | **Suspect A Confesses** | A: -5, B: -5 | A: 0, B: -10 | | **Suspect A Doesn't Confess** | A: -10, B: 0 | A: -1, B: -1 | ## Solution Concepts A **solution concept** is a rule that predicts the outcome of a game. ### Dominant Strategy A strategy $s_i \in S_i$ is a **dominant strategy** for player $i$ if it produces the best outcome for that player regardless of the strategies chosen by the other players. ### Nash Equilibrium A **Nash Equilibrium** is a set of strategies, one for each player, such that no player has an incentive to unilaterally change their strategy. #### How to find it 1. **Best Response**: For each player $i$ and for each possible strategy profile of the other players $s_{-i}$, find the set of player $i$'s best responses. 2. **Intersection**: Find a strategy profile $s^*$ that is a best response for all players. #### Example: Prisoner's Dilemma | | **Suspect B Confesses** | **Suspect B Doesn't Confess** | | :---------- | :----------------------: | :-----------------------------: | | **Suspect A Confesses** | **A: -5**, B: -5 | **A: 0**, B: -10 | | **Suspect A Doesn't Confess** | A: -10, **B: 0** | A: -1, **B: -1** | Confess is a dominant strategy for both players. Therefore, (Confess, Confess) is the Nash Equilibrium. ## Algorithmic Game Theory ### Definition Algorithmic Game Theory is an area that brings together algorithm design and game theory. Its goal is to design algorithms for strategic environments. ### Main topics - **Mechanism Design**: How to design games so that the players' self-interested behavior results in a desirable outcome. - **Price of Anarchy**: Measures the degradation in social welfare due to selfish behavior in a system. - **Computational Social Choice**: Deals with the design and analysis of voting rules and other collective decision-making mechanisms.