5D Library › Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks · 中文
Chapter 5 Exploration and Exploitation: Bandits, the Matthew Effect and Traffic Pools in Recommendation
Note
The models in this chapter are schematic. The “items”, “click rates” and “traffic pools” are fictional and the parameters illustrative. The three-tier traffic-pool program was written to show the statistical structure of “staged screening”; it does not represent any platform’s real recommendation algorithm and cannot be used to infer how any platform allocates traffic.
Exposure is scarce
A recommender system faces an allocation problem every day: screen positions are limited, users’ attention is more limited still, and the quality of most new content is not known in advance. Giving the positions to the content that currently performs best is called exploitation; giving some of them to content not yet well understood is called exploration. A system that only exploits soon locks onto whatever was lucky early; a system that only explores shows users too much bad content. Statisticians call this dilemma the multi-armed bandit problem.
The multi-armed bandit
Evidence
From Thompson to UCB. In 1933, discussing the comparison of two treatments, Thompson proposed allocating the next patient according to the posterior probability that one treatment is better than the other; this is what is now called Thompson sampling (Thompson 1933). In 1985 Lai and Robbins proved that for any reasonable allocation rule, the expected loss from wrong choices in trials (the regret) must grow at least as , and gave rules achieving this rate (Lai and Robbins 1985). In 2002 Auer, Cesa-Bianchi and Fischer gave the simple UCB1 rule (choose the arm with the largest “mean reward + ”) together with a finite-time bound on its regret (Auer et al. 2002). In 2010 Li, Chu, Langford and Schapire applied a bandit algorithm using user features to news recommendation on the Yahoo! front page and, evaluating it on logged data of more than 33 million events, reported a 12.5 % click lift over a standard context-free bandit algorithm (Li et al. 2010).
Calculation
Eight items with true click rates of 6.0, 5.0, 4.5, 4.0, 3.5, 3.0, 2.5 and 2.0 %; item 0 is a new niche item and is in fact the best. Four rules allocate 20,000 impressions: greedy (show each item once, then always the item with the highest observed click rate), -greedy (greedy 90 % of the time, random 10 %), UCB1, and Thompson sampling with a Beta(1, 1) prior. Each is run 60 times; regret is “expected clicks lost relative to always showing item 0”.
Calculation
# 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.")
# 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.The greedy rule loses 355.2 clicks on average, not far short of random display (437.5); in 50 of the 60 runs the best item 0 receives less than 10 % of impressions: it was not clicked in its first few showings and never got another chance. -greedy and Thompson sampling have similar mean regret (117.1 and 118.9), but Thompson sampling is steadier: its 90th percentile is 177.2 against 228.2 for -greedy, because the latter always spends 10 % of impressions at random, including on items that are clearly poor.
UCB1 does badly here (mean 364.9), and its 60 runs are nearly identical (90th percentile 375.1): it is not locked in but over-explores. Its exploration bonus is designed for general rewards between 0 and 1; when click rates are a few per cent and items differ by one percentage point, the bonus dwarfs the differences between items, so within 20,000 impressions it keeps rotating among them. Which rule is “better” depends on the scale of the problem, and textbook rules cannot be copied without adjustment.
The last three lines explain why exploration cannot be skipped: the two best items differ by one percentage point, which is only 0.31 standard errors with 100 impressions each, 0.98 with 1,000, and 3.10 only with 10,000. Early data are almost pure noise.
Rich get richer, and the Matthew effect
Evidence
The Matthew effect and social influence. In 1968 Merton used “the Matthew effect” for cumulative advantage in science: eminent scientists receive more recognition for the same contribution (Merton 1968). In 2006 Salganik, Dodds and Watts ran an artificial music market: 14,341 participants listened to and downloaded 48 unfamiliar songs, randomly assigned either to one of eight “worlds” in which they could see others’ download counts or to an independent condition in which they could not. When people could see others’ choices, inequality of success between songs was greater and outcomes were less predictable: the same song ranked very differently in different worlds; the best songs rarely did poorly and the worst rarely did well (Salganik et al. 2006). In 2009 Fleder and Hosanagar used a model and simulations to show that sales-based recommenders can reduce aggregate diversity in a market even while each individual sees more new things (Fleder and Hosanagar 2009). In 2018 Chaney, Stewart and Engelhardt showed by simulation that training recommender systems on data already shaped by recommendations homogenises user behaviour without increasing utility (Chaney et al. 2018).
Evidence
The evidence on “filter bubbles” is disputed. In 2015 Bakshy, Messing and Adamic analysed about ten million US Facebook users and found that individuals’ own choices reduced exposure to cross-cutting content more than the feed’s ranking algorithm did (Bakshy et al. 2015). In a randomised experiment during the 2020 US election, Guess and colleagues switched some users’ feeds to chronological order for about three months; these users spent markedly less time on the platform, but polarisation, political knowledge and other attitude measures did not change significantly (Guess et al. 2023). So “recommendation algorithms create filter bubbles” is not an established conclusion; this chapter is about the statistical structure of exposure allocation, not its effect on attitudes.
Calculation
Forty-eight items, each with a true “chance of being liked” drawn from a Beta(2, 18) distribution (median about 0.10, best about 0.34). In each of 8 independent “worlds”, 5,000 users arrive one by one; the recommender shows each user one item, and the user likes it with probability . Four display rules: random; always show the currently “most liked” item; show items at random in proportion to “1 + likes so far” (rich get richer); and Thompson sampling. The program compares total likes, the Gini coefficient of exposure, whether the most-shown item in each world is the best item, the share of exposure going to the true top five, and the rank correlation between exposure and true quality.
Calculation
# Rich-get-richer exposure versus learning about quality (a MODEL in the spirit of
# Salganik, Dodds & Watts 2006, not a replication). 48 items with fixed true appeal q
# (the chance that a user who is shown the item "likes" it). In each of 8 independent
# "worlds", 5,000 users arrive one by one; the recommender shows each user ONE item, and
# the user likes it with chance q.
import random
rng = random.Random(10)
M, USERS, WORLDS = 48, 5000, 8
Q = sorted((rng.betavariate(2, 18) for _ in range(M)), reverse=True) # item 0 is best
TOP5 = set(range(5))
def world(policy):
shown, liked = [0] * M, [0] * M
for _ in range(USERS):
if policy == "random":
i = rng.randrange(M)
elif policy == "most liked": # show the current chart-topper
top = max(liked); i = rng.choice([j for j in range(M) if liked[j] == top])
elif policy == "rich get richer": # chance proportional to 1 + likes
i = rng.choices(range(M), weights=[1 + x for x in liked])[0]
else: # Thompson sampling on q
i = max(range(M), key=lambda j: rng.betavariate(1 + liked[j],
1 + shown[j] - liked[j]))
shown[i] += 1; liked[i] += rng.random() < Q[i]
return shown, liked
def gini(x):
x = sorted(x); n = len(x); s = sum(x)
return sum((2 * (k + 1) - n - 1) * v for k, v in enumerate(x)) / (n * s)
def ranks(v): # average ranks for ties
order = sorted(range(len(v)), key=lambda j: v[j], reverse=True)
r, k = [0.0] * len(v), 0
while k < len(order):
m = k
while m + 1 < len(order) and v[order[m + 1]] == v[order[k]]: m += 1
for j in order[k:m + 1]: r[j] = (k + m) / 2
k = m + 1
return r
def spearman(a, b):
ra, rb = ranks(a), ranks(b); n = len(a); ma = sum(ra) / n; mb = sum(rb) / n
cov = sum((x - ma) * (y - mb) for x, y in zip(ra, rb))
va = sum((x - ma) ** 2 for x in ra); vb = sum((y - mb) ** 2 for y in rb)
return cov / (va * vb) ** 0.5
print(f"best true appeal {Q[0]:.3f}, 5th {Q[4]:.3f}, median {Q[M // 2]:.3f}")
print("policy likes per Gini of top-shown"
" item exposure share rank corr.")
print(" 1000 users exposure ="
" best item to true top 5 w. quality")
distinct = {}
for pol in ("random", "most liked", "rich get richer", "Thompson"):
res = [world(pol) for _ in range(WORLDS)]
distinct[pol] = len({max(range(M), key=lambda j: s[j]) for s, _ in res})
likes = sum(sum(l) for _, l in res) / WORLDS / USERS * 1000
g = sum(gini(s) for s, _ in res) / WORLDS
best = sum(max(range(M), key=lambda j: s[j]) == 0 for s, _ in res)
top = sum(sum(s[j] for j in TOP5) / USERS for s, _ in res) / WORLDS
rho = sum(spearman(Q, s) for s, _ in res)
print(f"{pol:16s} {likes:6.1f} {g:.2f} {best} of {WORLDS} "
f"{top:.2f} {rho / WORLDS:+.2f}")
print("distinct most-shown items in the 8 worlds:\n "
+ ", ".join(f"{p} {d}" for p, d in distinct.items()))
# best true appeal 0.342, 5th 0.229, median 0.103
# policy likes per Gini of top-shown item exposure share rank corr.
# 1000 users exposure = best item to true top 5 w. quality
# random 114.4 0.05 0 of 8 0.10 +0.07
# most liked 156.2 0.98 0 of 8 0.13 +0.07
# rich get richer 229.7 0.68 5 of 8 0.59 +0.63
# Thompson 258.8 0.72 8 of 8 0.69 +0.69
# distinct most-shown items in the 8 worlds:
# random 8, most liked 8, rich get richer 3, Thompson 1“Always show the most liked” is the most extreme Matthew effect: a Gini coefficient of 0.98, with almost all exposure going to whichever item was liked first; the 8 worlds have 8 different “champions”, none of them the best item, and exposure is almost unrelated to quality (rank correlation +0.07, the same as random display). The proportional “rich get richer” rule is much better: 229.7 likes per thousand users, and in 5 of the 8 worlds the champion is the best item; but the champions are still 3 different items, so the outcome depends partly on early luck, the unpredictability that Salganik and colleagues described. Thompson sampling earns 258.8 likes per thousand users; all 8 worlds crown the same champion, which is the best item, the true top five receive 69 % of exposure, and the rank correlation is +0.69.
A result that is easy to miss is that Thompson sampling’s exposure is also very unequal: its Gini coefficient of 0.72 is even higher than the 0.68 of the rich-get-richer rule. So what the author’s framework calls “correcting the Matthew effect” needs to be stated precisely: a good exploration rule does not equalise exposure; it makes the concentration of exposure agree with quality and be reproducible, rather than depend on who was lucky first. If diversity itself is a goal, it must be written into the rule separately.
Three tiers of traffic pools
Many platforms are described as allocating new content through a ladder of “cold-start test → expanded test → network-wide recommendation”. The program below treats this structure only as a screening problem: how to use limited exposure so that the truly best content reaches the last tier.
Calculation
Five thousand new items, each with a true click rate (Beta(3, 57), mean 5 %) and a true completion rate (Beta(4, 6), mean 40 %), independent; the true value of an impression is . The aim is for the true top 50 by value (1 %) to reach the third tier. Tier 1: 200 impressions per item, with the top 10 % (500 items) going to tier 2; tier 2: 2,000 impressions each, ranked by completed views, with the top 50 going to tier 3. Five designs are compared: tier 1 ranked by clicks only; by completed views; by completed views with a retest of 200 more impressions for items near the threshold (within one standard error); and versions in which items from large accounts are first shown to their fans in tier 1, inflating their click rate 1.5-fold. Each design is replicated 20 times.
Calculation
# A three-tier "traffic pool" funnel as a screening problem (an illustrative MODEL; it
# does not describe any platform's real algorithm). 5,000 new items; item i has a true
# click rate c_i ~ Beta(3, 57) (mean 5 %) and a true completion rate r_i ~ Beta(4, 6)
# (mean 40 %), independent. True value per impression = c_i r_i. Goal: the true top 50
# (1 %) should reach the third tier. Tier 1 (cold start): 200 impressions each, top 10 %
# go on. Tier 2: 2,000 impressions each, ranked by completed views (retention-weighted),
# top 50 go to tier 3. 20 replications.
import math, random
rng = random.Random(11)
N, N1, N2, KEEP2, TOP = 5000, 200, 2000, 500, 50
def binom(n, p): # exact binomial by geometric waiting times
if p <= 0: return 0
k, t, lq = 0, 0, math.log(1 - p)
while True:
t += int(math.log(1 - rng.random()) / lq) + 1
if t > n: return k
k += 1
def run(rule1, retest=False, fans=1.0):
c = [rng.betavariate(3, 57) for _ in range(N)]
r = [rng.betavariate(4, 6) for _ in range(N)]
head = [i < N // 5 for i in range(N)] # 20 % from large accounts
v = [c[i] * r[i] for i in range(N)]
best = set(sorted(range(N), key=lambda i: v[i], reverse=True)[:TOP])
c1 = [min(1.0, c[i] * (fans if head[i] else 1)) for i in range(N)] # fans see tier 1
imp = [N1] * N
clk = [binom(N1, c1[i]) for i in range(N)]
done = [binom(clk[i], r[i]) for i in range(N)]
score = [(clk[i] if rule1 == "clicks" else done[i]) / imp[i] for i in range(N)]
if retest: # second test for the borderline items
cut = sorted(score, reverse=True)[KEEP2]
for i in range(N):
se = math.sqrt(max(score[i], 1e-4) / imp[i])
if abs(score[i] - cut) < se:
k = binom(N1, c1[i]); d = binom(k, r[i]); imp[i] += N1
clk[i] += k; done[i] += d
score[i] = (clk[i] if rule1 == "clicks" else done[i]) / imp[i]
tier2 = sorted(range(N), key=lambda i: score[i], reverse=True)[:KEEP2]
s2 = {i: binom(N2, c[i]) for i in tier2}
s2 = {i: binom(k, r[i]) / N2 for i, k in s2.items()}
tier3 = sorted(tier2, key=lambda i: s2[i], reverse=True)[:TOP]
return (len(best & set(tier2)) / TOP, len(best & set(tier3)) / TOP,
sum(v[i] for i in tier3) / sum(v[i] for i in best),
sum(not head[i] for i in tier3) / TOP, sum(imp) + KEEP2 * N2)
DESIGNS = [("tier 1 by clicks", dict(rule1="clicks")),
("tier 1 by completed views", dict(rule1="done")),
("completed views + borderline retest", dict(rule1="done", retest=True)),
("by clicks, large accounts' fans click 1.5x", dict(rule1="clicks", fans=1.5)),
("completed views + retest, fans 1.5x",
dict(rule1="done", retest=True, fans=1.5))]
print("design top-50 kept top-50 in "
"value of tier 3 small")
print(" to tier 2 tier 3 "
"/ best possible accts")
for lab, kw in DESIGNS:
res = [run(**kw) for _ in range(20)]
m = [sum(x[j] for x in res) / 20 for j in range(5)]
print(f"{lab:42s} {m[0]:5.2f} {m[1]:5.2f} {m[2]:5.2f}"
f" {m[3]:4.2f}")
print(f"impressions used per replication: about {m[4] / 1e6:.1f} million;"
" small accounts are"
f" 80 % of items")
cs = sorted(rng.betavariate(3, 57) for _ in range(20000))
spread = cs[int(0.99 * 20000)] - cs[10000]
for n in (N1, N2):
print(f"signal-to-noise with {n:4d} impressions: (99th pct - median click rate)"
" / s.e. = "
f"{spread / math.sqrt(0.05 * 0.95 / n):.1f}")
# design top-50 kept top-50 in value of tier 3 small
# to tier 2 tier 3 / best possible accts
# tier 1 by clicks 0.87 0.78 0.97 0.79
# tier 1 by completed views 0.96 0.82 0.98 0.78
# completed views + borderline retest 0.99 0.82 0.98 0.80
# by clicks, large accounts' fans click 1.5x 0.84 0.78 0.97 0.76
# completed views + retest, fans 1.5x 0.99 0.82 0.98 0.79
# impressions used per replication: about 2.2 million; small accounts are 80 % of items
# signal-to-noise with 200 impressions: (99th pct - median click rate) / s.e. = 6.0
# signal-to-noise with 2000 impressions: (99th pct - median click rate) / s.e. = 18.9When tier 1 looks only at clicks, 87 % of the true top 50 reach tier 2 and 78 % reach tier 3; when tier 1 looks at completed views, 96 % reach tier 2 and 82 % tier 3; adding the retest near the threshold brings tier 2 to 99 %, but tier 3 stays at 82 %. In this setting the bottleneck has moved from tier 1 to tier 2: 2,000 impressions per item, with about 40 completed views on average, are not enough to separate the top 50 reliably from items ranked 51 to 100. The total value of the content reaching tier 3 is 97–98 % of the best possible, because the items missed are mostly almost as good as those selected.
The signal-to-noise calculation explains why tier 1 needs a generous threshold: with 200 impressions, the difference between the 99th-percentile and the median click rate is only about 6 standard errors, while what really has to be distinguished are items near the threshold that differ only slightly; with 2,000 impressions it is 18.9. In the fan-inflation case, with tier 1 ranked by clicks, the share of the top 50 reaching tier 2 falls from 87 % to 84 %, and the small accounts’ share of tier 3 falls from 79 % to 76 %; with tier 1 ranked by completed views plus the retest, the bias essentially disappears (79 %). In this model, choosing the right metric matters more than adding tiers. A click-only first tier also leaves room for “clickbait”, an instance of Goodhart’s law discussed in Chapter 6 of Volume 27: once a measure becomes a target, it is optimised until it parts company with its purpose.
Hypothesis · not established
The cold-start metric hypothesis (not yet established). The author conjectures that when exposure is allocated in stages, using completion instead of click rate in the first tier raises the share of high-quality small-account content that reaches wide recommendation. The testable prediction is that in a platform-randomised A/B test, small-account content judged high-quality by independent reviewers reaches the last tier more often in the completion arm than in the click arm; if not, the hypothesis is refuted. Only platforms, or researchers working with them, can run such a test.
Summary
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 -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.
References
Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: From Wardrop Equilibria and Selfish Routing to Platform Congestion, Read Beside Classical Chinese Hydraulic Engineering [算法博弈论、布雷斯悖论与流量分配的无秩序代价] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).