Questions: Algorithmic Game Theory

Question 1

The complexity class PPAD captures the difficulty of finding Nash equilibria. What distinguishes PPAD from NP?

• A. PPAD problems may have no solution, while NP problems always do
• B. PPAD is a subclass of TFNP (total search problems) -- a solution is guaranteed to exist by a parity argument, but finding it is hard. NP decision problems may have no yes-certificate
• C. PPAD problems are harder than NP problems
• D. PPAD and NP are identical classes

Answer: (B)

PPAD (Polynomial Parity Arguments on Directed graphs) is a subclass of TFNP, which consists of NP search problems where a solution is guaranteed to exist. Nash's theorem guarantees a Nash equilibrium exists for every game, so finding one is a total search problem. PPAD captures problems where existence follows from the fact that a directed graph with an unbalanced node (more out-edges than in-edges) must have another unbalanced node. The PPAD-completeness of Nash equilibrium means: (1) a solution always exists, (2) finding it is unlikely to be polynomial-time (unless PPAD subset FP), but (3) the problem is probably not NP-hard (since NP-hard total search problems would collapse complexity classes).

Question 2

The price of anarchy for selfish routing in networks with linear latency functions is 4/3. This means that the worst-case Nash equilibrium has total latency at most 4/3 times the social optimum.

• T. True
• F. False

Answer: True

Roughgarden and Tardos (2002) proved that in nonatomic selfish routing (Wardrop equilibrium) on networks with linear latency functions l_e(x) = a_e * x + b_e, the price of anarchy is exactly 4/3. The tight example is Pigou's network: two parallel links, one with constant latency 1 and one with latency x. Selfish routing sends all traffic on the variable-latency link until both links have equal latency, producing total latency 1 versus the optimal 3/4. For polynomial latency functions of degree d, the price of anarchy grows as Theta(d / ln d), showing that steeper latency functions lead to more inefficient equilibria.

Question 3

Explain the VCG (Vickrey-Clarke-Groves) mechanism and why it achieves truthful reporting as a dominant strategy.

Model answer: The VCG mechanism selects the outcome that maximizes the sum of reported valuations, then charges each agent a payment equal to the externality they impose on others: the difference between the total value others would get without agent i and the total value others get with agent i. Under VCG, truthful reporting is a dominant strategy because each agent's payment is independent of their own report (it depends only on others' valuations), and the mechanism maximizes the sum of valuations, so reporting truthfully maximizes the agent's own utility (valuation minus payment). No matter what others report, truthful reporting is each agent's best response.

VCG generalizes the second-price (Vickrey) auction to combinatorial settings. In a second-price auction, the winner pays the second-highest bid -- their payment is independent of their own bid, making truthfulness dominant. VCG extends this to multi-item, multi-agent settings. The limitation is computational: computing the welfare-maximizing outcome is often NP-hard (e.g., combinatorial auctions), and VCG requires solving this optimization exactly. Approximate VCG mechanisms that use approximate welfare maximization generally lose the truthfulness guarantee, creating a fundamental tension between computational efficiency and incentive compatibility.

Question 4

A mechanism is truthful (strategyproof) if every agent maximizes their utility by reporting their true valuation regardless of what other agents report. Can every social welfare maximizing algorithm be converted into a truthful mechanism by adding appropriate payments?

• T. True
• F. False

Answer: False

Only algorithms satisfying specific monotonicity properties can be made truthful via payments. For single-parameter domains (each agent has one private value), Myerson's characterization shows that an allocation rule can be made truthful if and only if it is monotone: increasing your bid never decreases your allocation. For multi-parameter domains, the conditions are more complex (weak monotonicity / cycle monotonicity). In particular, many polynomial-time approximation algorithms for NP-hard problems are not monotone and cannot be made truthful. This creates a gap between the best achievable approximation ratio for truthful mechanisms versus unrestricted algorithms -- a central concern in algorithmic mechanism design.

Question 5

What is the price of stability, and how does it differ from the price of anarchy?

Model answer: The price of stability is the ratio of the cost of the BEST Nash equilibrium to the cost of the social optimum, while the price of anarchy is the ratio for the WORST Nash equilibrium. The price of stability measures the inefficiency inherent in any equilibrium, even the most favorable one, while the price of anarchy captures the worst-case inefficiency. For network design games (fair cost-sharing), the price of anarchy can be as bad as n (number of players), but the price of stability is only H(n) = O(log n), meaning there always exists a near-optimal equilibrium even though selfish dynamics might converge to a terrible one.

The distinction is practically important: if the price of stability is low, a central coordinator can suggest a good equilibrium and agents will have no incentive to deviate. If the price of anarchy is also low, no coordination is needed -- even the worst equilibrium is near-optimal. Games where the price of anarchy is high but the price of stability is low benefit from equilibrium selection (nudging agents toward the good equilibrium) rather than mechanism redesign.