Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: chapter answers
Why can building one more road make everyone slower? This book uses algorithmic game theory to examine the gap between selfish choices and the collective optimum: where it comes from, how large it can be, what prices or rules can close it, and in what form the same structure appears in attention markets, recommender systems and matching markets. It covers Wardrop's user equilibrium and system optimum; Braess's diamond network, in which a zero-delay shortcut raises travel time from 1.5 to 2.0 (the shortcut is weakly, not strictly, dominant, and the paradox appears only for demand between 2/3 a…
DOI 10.5281/zenodo.23782094 · Read the monograph · 中文版
- Chapter 1 · Braess's Paradox: One More Road, Everyone Slower
The user equilibrium requires all used routes to be equally fast; the system optimum requires total cost to be as low as possible; the two differ by the marginal delay each person adds for others. In Braess's diamond ne… - Chapter 2 · The Price of Anarchy: How Much Can Selfishness Cost?
The price of anarchy is the ratio of the worst selfish equilibrium to the optimum. In networks with linear delays and nonatomic users it is at most 4/3, and the worst case is Pigou's two-road network whatever the topolo… - Chapter 3 · Pigouvian Tolls and Potential Games: Pricing the Unseen Delay
Selfish users bear only the average delay, not the marginal delay they add for others. A toll of $x^c'(x)$ on each road at the optimum makes the selfish equilibrium coincide with the optimum; but unless the revenue is r… - Chapter 4 · Congestion in Attention: Hot Niches, Hotelling and a Digital Braess Paradox
Hotelling's linear city predicts clustering when prices are fixed, but under price competition the sellers move apart, because moving towards a rival only invites a price war. In the niche congestion game the equilibriu… - Chapter 5 · Exploration and Exploitation: Bandits, the Matthew Effect and Traffic Pools in Recommendation
Exploiting without exploring locks exposure onto content that was lucky early: in 50 of 60 runs the greedy rule gave the best item almost no chance. Thompson sampling and $\varepsilon$-greedy lose only about a third as… - Chapter 6 · Stable Matching: Deferred Acceptance, Early Contracting and Telling the Truth
The program checks these properties one by one on 500 random 6 × 6 markets: every result is stable; every proposer gets his best partner among all stable matchings (found by enumerating all 720 pairings); every receiver… - Chapter 8 · Practice and a Pre-Registered Trial
The sample size is therefore based on much more conservative assumptions: 60 % of control groups trapped and 30 % of arm A groups, two-sided $\alpha = 0.05$, 90 % power. Each arm needs 56 analysable groups; allowing abo…
Illustrative model calculation, not a live quote