Algorithmic Game Theory

• Algorithmic Game Theory (AGT) lies at the intersection of computer science and game theory, using algorithm design and analysis to predict behavior in strategic settings.
• AGT designs strategy-proof mechanisms so that selfish behavior yields desirable outcomes.

What is Algorithmic Game Theory?

• Game Theory studies strategic interactions between rational players.
• Algorithm Design involves designing efficient algorithms to compute solutions.

Key Challenges

• Game Theory assumes players can compute optimal strategies but does not consider the computational complexity of doing so.
• Algorithm Design ignores the strategic behavior of participants.

Solution Concepts

• Nash Equilibrium is a game state where no player can improve their payoff by unilaterally changing their strategy.
• A key question is that: How hard is it to compute a Nash Equilibrium?

Mechanism Design

• The goal is to design the rules of a game to ensure that, when each player acts in their best interest, the outcome is socially desirable.
• Auctions, such as those used by Google and Yahoo! to sell advertisement slots, are designed to maximize revenue.
• Social Choice explores the possibility of designing a voting rule that accurately reflects the preferences of the voters.

Price of Anarchy

• Price of Anarchy measure how inefficient selfish behavior is.
• Braess's Paradox demonstrates adding a road to a network can increase the average travel time for all users because of selfish routing.

Fair Division

• Fair Division focuses on how to fairly divide resources among multiple players with different preferences.
• Cake Cutting involves dividing a cake among several people such that everyone feels they have received a fair share.

Selfish Routing (Price of Anarchy)

• A network of n players who want to travel from a source s to a destination t is the basis of selfish routing.
• Each edge e in the network has a cost/latency function $l_e(x)$ that depends on the amount of traffic x on that edge.
• Each player aims to minimize their travel time.
• Selfish routing can increase the total travel time compared to an optimal routing solution.

Braess's Paradox Explained

• Adding a road to a network can increase the total travel time for all players.
• In one scenario, 100 players want to travel from S to E, with a total cost of 1.5 for everyone.
• When a new road with cost 0 from A to B is added, everyone uses the path S -> A -> B -> E, increasing the total cost to 2.

The Price of Anarchy (PoA) Defined

• PoA refers to: ${Cost of worst-case Nash Equilibrium} \over {Cost of optimal solution}$
• For linear latency functions, the Price of Anarchy is at most $\frac{4}{3}$.
• The proof involves showing that the cost of a mixed flow (a combination of Nash Equilibrium and optimal flow) is a convex function.

Mechanism Design in Auctions

• Mechanism Design is the process of creating rules to ensure that when each player acts in their own interest, the outcome is socially desirable.
• An auction's goal is to sell an item to one of n bidders, where each bidder has a private value $v_i$ for the item, and the auctioneer aims to maximize revenue.

Desiderata in Auction Design

• Efficiency means the item should be allocated to the bidder with the highest value.
• Individual Rationality means each bidder should be guaranteed non-negative utility.
• Truthfulness means each bidder should maximize their utility by bidding their true value.

Vickrey-Clarke-Groves (VCG) Mechanism

• VCG allocates the item to the bidder with the highest bid.
• VCG charges the winner $i$ pays the second highest bid.
• Bidding your true value is a dominant strategy in VCG mechanism.
• VCG maximizes social welfare.

Cake Cutting (Fair Division)

• Cake Cutting focuses on dividing a cake among $n$ players such that everyone feels they have received a fair share.

The Cake Cutting Model

• The cake is represented by the interval $[0,1]$.
• Each player $i$ has a valuation function $V_i$ that assigns a value to each subinterval of the cake, with $V_i([0,1]) = 1$ for all players.

Fairness Notions

• Proportionality is where each player receives a piece of the cake that they value at least $\frac{1}{n}$.
• Envy-freeness refers to no player prefers another player's piece of the cake to their own.
• Pareto Optimality means it is impossible to make one player better off without making another player worse off.

Cake Cutting Algorithms and Challenges

• Design algorithms that compute fair allocations, especially when the number of players is large
• Dubins-Spanier algorithm guarantees a proportional division for two players.
• Selfridge-Conway algorithm guarantees an envy-free division for three players.
• Open research questions include designing efficient algorithms that compute envy-free divisions for $n$ players and exploring other fairness notions.