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
mean90th pct on item 0 (mean) gets < 10 % gets > 50 %
greedy355.2 699.9 0.17 50 10
eps-greedy117.1 228.2 0.64 7 45
UCB1364.9 375.1 0.20 0 0
Thompson118.9 177.2 0.65 3 49
showing items at random would lose 437.5 clicks
with100 impressions each, the 1-point gap between the two best items = 0.31 s.e.
with1000 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 items3.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