Algorithmic Game Theory (AGT)

• Algorithmic Game Theory (AGT) merges game theory and algorithm design, crucial for understanding strategic interactions in online economic activities.

Algorithmic Game Theory vs Traditional Game Theory

• Traditional game theory focuses on mathematical analysis of strategic interactions and equilibrium properties between rational agents.
• Algorithmic Game Theory (AGT) brings computation into game theory and game-theoretic aspects into algorithm design.

Importance of AGT

• AGT is important because it considers strategic participants, extensive resources, distributed networks, and the impossibility of centralized control, common in Internet-based economic activities.

Key Areas in AGT

• Mechanism Design: Designing game rules to reach a desired outcome, accounting for selfish players, applicable in areas like auctions and voting.
• Price of Anarchy: Quantifying the inefficiency of a game's outcome due to selfish actions, relative to a centrally controlled optimum, seen in network routing and load balancing.
• Solution Concepts: Identifying potential game outcomes and efficiently computing them, such as Nash equilibrium and correlated equilibrium.

Selfish Routing Model

• Involves a network with n agents, each controlling traffic flow ri from origin si to destination ti.
• Edge latency le(x) depends on traffic amount; agents choose paths to minimize their own latency.
• Social cost is the sum of every agent's latency.

Selfish Routing Key Questions

• What does the equilibrium look like in a selfish routing model?
• How inefficient is the equilibrium when compared to the optimal assignment?
• How hard is it to compute the equilibrium?

Braess's Paradox

• Braess's Paradox demonstrates that adding a new road to a network can increase overall latency due to selfish routing.
• In an example network with 1 unit of traffic from A to D, adding a zero-latency road from B to C causes drivers to switch to the longer A-B-C-D route.
• Despite the new road, each driver's latency increases from 1 to 2.
• The inclusion of a new resource may negatively impacts overall efficiency because it creates a new, worse equilibrium.

Conclusion

• Algorithmic Game Theory combines game theory with computer science.
• AGT has applications in economics, computer science, and engineering.
• Understanding AGT principles helps in designing systems more resilient to selfish behavior.