IMG_9445.jpeg

# Algorithmic Game Theory ## What is Game Theory? * **Deals with**: multi-agent settings = strategic interactions * **Agents**: rational(utility-maximizing) * each agent has a set of possible actions * an agent's utility depends on the actions of all agents ## Examples ### Conges...

# Algorithmic Game Theory ## What is Game Theory? * **Deals with**: multi-agent settings = strategic interactions * **Agents**: rational(utility-maximizing) * each agent has a set of possible actions * an agent's utility depends on the actions of all agents ## Examples ### Congestion games * **Example**: routing games * **Players**: computer programs/drivers * **Actions**: possible routes(between origin and destination) * **Utility**: minus the delay on the route ### Auction * **Players**: bidders * **Actions**: possible bids * **Utility**: value for the item - payment ### Social Networks * **Players**: people * **Actions**: join the network, buy a product, adopt a technology * **Utility**: subjective ## What is Algorithmic Game Theory? ### Traditional game theory * mainly existence results * characterization * computationally intractable ### Algorithmic game theory * Also considers computational issues * **Examples**: * Can we compute an equilibrium? * How long does it take until the system reaches an equilibrium? * What is the quality of an equilibrium? * Can we design the game so that the outcome is "good"? ## Complexity Classes ### Complexity Classes in Algorithmic Game Theory * **Polynomial Time**: P * **Nondeterministic Polynomial Time**: NP * **co-NP**: complement of NP * **PPAD**: Polynomial Parity Arguments on Directed graphs * **PLS**: Polynomial Local Search * **FIXP**: Fixed Point ### Relationships between complexity classes The image shows the relationships between different complexity classes: P is a subset of NP, which is a subset of PPAD, which is a subset of FIXP. PLS is also a subset of FIXP, and co-NP is not necessarily related to any of these classes. ## What is a Solution Concept? * Describes the behavior of "rational" agents in a game * A prediction of the outcome * **Examples**: * Nash equilibrium * Dominant strategy equilibrium * Pareto optimality * Social welfare maximization ## Nash Equilibrium ### Nash Equilibrium Definition A Nash Equilibrium is a set of strategies, one for each player, such that no player has an incentive to unilaterally deviate. ### Nash Equilibrium Example **Game**: Prisoner's Dilemma | | Player 2: Cooperate | Player 2: Defect | | :-------- | :------------------ | :--------------- | | **Player 1: Cooperate** | -1, -1 | -3, 0 | | **Player 1: Defect** | 0, -3 | -2, -2 | **(Defect, Defect) is a Nash Equilibrium** ### Existence of Nash Equilibria **Theorem (Nash, 1951)**: Every game with a finite number of players and a finite number of actions has at least one Nash equilibrium (possibly in mixed strategies). * **Mixed Strategy**: assign a probability distribution over your actions * **Example**: each player flips a coin; if heads play C, otherwise D ## Price of Anarchy ### Definition * How much does the system performance degrade due to selfish behavior? * Ratio between the "worst" Nash equilibrium and the optimum $PoA = \frac{\text{cost of worst Nash equilibrium}}{\text{optimal cost}}$ * Measures the inefficiency of selfish behavior ### Example: Braess's Paradox #### The Paradox Adding a link to a network can worsen the travel time for all users #### Braess's Paradox Example **Scenario 1**: 2000 drivers want to travel from A to B * Road A to C: travel time = x/100 * Road A to D: travel time = 45 * Road C to B: travel time = 45 * Road D to B: travel time = x/100 **What will happen?** * All drivers take the path A -> C -> B * Travel time for everyone is 2000/100 + 45 = 65 **Scenario 2**: Add a road from C to D with travel time 0 * Now, each driver takes path A -> C -> D -> B * Travel time for everyone is now 2000/100 + 0 + 2000/100 = 40 **What will happen now?** * Everyone switches to A -> C -> D -> B * Travel time for everyone is 2000/100 + 0 + 2000/100 = 40 **Equilibrium**: everyone takes path A -> C -> D -> B **Social optimum**: everyone takes path A -> C -> B **Price of Anarchy**: 40/65 = 8/13 ## Topics in Algorithmic Game Theory * Mechanism design * Auctions * Social network analysis * Information economics * Learning in games * Evolutionary game theory * Congestion games * Cost sharing