Game Theory: Prisoner's Dilemma

• Game theory is used to analyze strategic interactions between decision-makers (players).
• Game theory can predict player behavior and design games for desired outcomes.
• Players in game theory are assumed to be selfish and motivated by their own payoff.
• Strategic interactions occur when a player's optimal action depends on other players' actions.

Prisoner's Dilemma

• Two suspects are arrested and held separately with no communication.
• If one confesses and the other doesn't, the confessor is released, and the other gets a 10-year sentence.
• If both confess, they each get a 5-year sentence and if neither confesses, they each get a 1-year sentence.

Payoff Matrix for Prisoner's Dilemma

• The payoff matrix represents the outcomes for Suspect A and Suspect B based on their actions.
• Matrix entries show payoffs for each suspect; confessing is a dominant strategy.
• If Suspect B confesses, Suspect A is also better off confessing (-5 > -10).
• If Suspect B doesn't confess, Suspect A is still better off confessing (0 > -1).

Dominant Strategy

• A strategy is optimal regardless of what other players do.
• In the Prisoner's Dilemma, confessing is a dominant strategy for both suspects.

Nash Equilibrium

• In a Nash equilibrium, no player benefits from changing their strategy unilaterally.
• In the Prisoner's Dilemma, the only Nash equilibrium is both suspects confessing.

Pareto Optimality

• An outcome is Pareto optimal if no player can be made better off without worsening another player's situation.
• In the Prisoner's Dilemma, both suspects confessing isn't Pareto optimal.

Tragedy of the Commons

• The Prisoner's Dilemma exemplifies a tragedy, where individual rationality results in a suboptimal collective outcome.

Algorithmic Game Theory

• Focuses on designing mechanisms/games to align selfish behavior with desirable outcomes.
• Centers around computing (or approximating) game-theoretic solution concepts.

Selfish Routing

Model

• A network is represented by a directed graph $G = (V, E)$.
• Each edge $e \in E$ has a cost function $c_e(x)$ depending on traffic $x$.
• There is a set of $k$ commodities, each with a source node $s_i \in V$, a destination node $t_i \in V$, and a demand $d_i \ge 0$. -The demand $d_i$ is the amount of traffic that needs to flow from $s_i$ to $t_i$.
• Each unit of traffic is controlled by a selfish agent who wants to minimize its own cost.

Wardrop Equilibrium

• Occurs when all traffic between an origin-destination pair travels along a path of minimum cost.

Price of Anarchy

• Price of anarchy (PoA) measures performance degradation due to selfish behavior.
• PoA is calculated as: $$PoA = \frac{\text{cost of worst-case Nash equilibrium}}{\text{cost of social optimum}}$$

Explore game theory with the classic Prisoner's Dilemma. Analyze strategic interactions, payoff matrices, and the concept of dominant strategies. Understand how individual incentives lead to suboptimal outcomes in this scenario.