What does Braess's Paradox and the Price of Anarchy conclude, in numbers, about “Exploration and Exploitation: Bandits, the Matthew Effect and Traffic Pools in Recommendation”?
Answer: 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 much as greedy, and the former is steadier; UCB1 over-explores when click rates are low. The "rich get richer" rule, allocating exposure by likes so far, makes outcomes depend partly on luck, while Thompson sampling makes the concentration of exposure agree with quality, without making exposure equal. In the schematic three-tier traffic pool, choosing the right first-tier metric matters more than adding tiers, and the second tier's sample size decides how accurately the final selection can be made. The empirical evidence that recommendation algorithms create filter bubbles is disputed. The next chapter turns to another allocation problem: two-sided matching.
Scope of the numbers: The models of traffic pools and recommender algorithms are schematic and describe no real platform; the book is not investment, business or marketing advice. Marked boxes separate published evidence, runnable Python calculations (16 programs, all checked), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 50, 60
| policy regret (clicks) share of impressions runs (of 60) in which item 0 | |
| mean | 90th pct on item 0 (mean) gets < 10 % gets > 50 % |
| greedy | 355.2 699.9 0.17 50 10 |
| eps-greedy | 117.1 228.2 0.64 7 45 |
| UCB1 | 364.9 375.1 0.20 0 0 |
| Thompson | 118.9 177.2 0.65 3 49 |
| showing items at random would lose 437.5 clicks | |
| with | 100 impressions each, the 1-point gap between the two best items = 0.31 s.e. |
| with | 1000 impressions each, the 1-point gap between the two best items = 0.98 s.e. |
| with 10000 impressions each, the 1-point gap between the two best items | 3.10 s.e. |
Show the full program
# Explore or exploit: four ways to allocate 20,000 impressions among 8 items whose click
# rates are unknown. Item 0 (a new niche item) is truly best at 6 %; the others range
# from 5 % to 2 %. Regret = expected clicks lost relative to always showing item 0.
# Illustrative values.
import math, random
rng = random.Random(9)
P = [0.060, 0.050, 0.045, 0.040, 0.035, 0.030, 0.025, 0.020]
K, T, RUNS = len(P), 20000, 60
def run(policy, trace=None): # trace: optional list for cumulative regret
n, s, reg = [0] * K, [0] * K, 0.0
for t in range(T):
if policy == "greedy":
i = t if t < K else max(range(K), key=lambda j: (s[j] / n[j], rng.random()))
elif policy == "eps-greedy":
if t < K: i = t
elif rng.random() < 0.1: i = rng.randrange(K)
else: i = max(range(K), key=lambda j: (s[j] / n[j], rng.random()))
elif policy == "UCB1":
i = t if t < K else max(range(K), key=lambda j: s[j] / n[j]
+ math.sqrt(2 * math.log(t) / n[j]))
else: # Thompson sampling, Beta(1, 1) prior
i = max(range(K), key=lambda j: rng.betavariate(1 + s[j], 1 + n[j] - s[j]))
n[i] += 1; s[i] += rng.random() < P[i]; reg += P[0] - P[i]
if trace is not None and (t + 1) % 500 == 0: trace.append(reg)
return n
print("policy regret (clicks) share of impressions"
" runs (of 60) in which item 0")
print(" mean 90th pct on item 0 (mean) gets < 10 % gets > 50 %")
for pol in ("greedy", "eps-greedy", "UCB1", "Thompson"):
regs, shares = [], []
for _ in range(RUNS):
n = run(pol)
regs.append(sum(n[j] * (P[0] - P[j]) for j in range(K))); shares.append(n[0] / T)
regs.sort()
print(f"{pol:12s} {sum(regs) / RUNS:6.1f} {regs[53]:6.1f} "
f"{sum(shares) / RUNS:5.2f} {sum(x < 0.1 for x in shares):3d}"
f" {sum(x > 0.5 for x in shares):3d}")
print(f"showing items at random would lose {T * (P[0] - sum(P) / K):.1f} clicks")
gap = P[0] - P[1]
for n in (100, 1000, 10000):
se = math.sqrt(P[0] * (1 - P[0]) / n + P[1] * (1 - P[1]) / n)
print(f"with {n:5d} impressions each, the 1-point gap between the two best items"
f" = {gap / se:.2f} s.e.")Single source and citation
Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks (Version 1.0.0), Chapter 5: Exploration and Exploitation: Bandits, the Matthew Effect and Traffic Pools in Recommendation. 5D Library. https://doi.org/10.5281/zenodo.23782094
DOI: 10.5281/zenodo.23782094 · Read the monograph · 5DL-B-032 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026032,
author = {Fan, Yafu},
title = {Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
doi = {10.5281/zenodo.23782094},
url = {https://doi.org/10.5281/zenodo.23782094}
}Other chapter answers in this book
- Chapter 1 · Braess's Paradox: One More Road, Everyone Slower
- Chapter 2 · The Price of Anarchy: How Much Can Selfishness Cost?
- Chapter 3 · Pigouvian Tolls and Potential Games: Pricing the Unseen Delay
- Chapter 4 · Congestion in Attention: Hot Niches, Hotelling and a Digital Braess Paradox
- Chapter 6 · Stable Matching: Deferred Acceptance, Early Contracting and Telling the Truth
- Chapter 8 · Practice and a Pre-Registered Trial