5D Library › Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks · 中文

Chapter 4 Congestion in Attention: Hot Niches, Hotelling and a Digital Braess Paradox

Note

This chapter is model reasoning, not empirical research. It carries the structures of the first three chapters over to markets in which creators, sellers and advertisers compete for attention. All parameters are illustrative; the “niches”, “acquisition costs” and “marketing tools” in the programs are fictional, describe no real platform, and cannot be used to forecast the returns of any account, brand or advertising plan. This chapter is not marketing or business advice.

Two kinds of congestion

Attention markets have two kinds of congestion that look alike but work differently. One is price competition: many sellers crowd into the same category with the same positioning and can compete only by cutting prices, so margins are squeezed. The other is capacity congestion: many people bid for the same keywords and audiences, pushing up everyone’s acquisition cost, as cars slow each other on a road. Hotelling’s linear city concerns the first kind, congestion games the second. This chapter computes each, then asks whether a Braess paradox can occur in attention markets.

Hotelling’s linear city

Evidence

Hotelling (1929) and its correction. Hotelling considered customers spread uniformly along a line and two sellers, with each customer buying from the seller with the lowest “price + travel cost”. He argued that the sellers tend to move together towards the middle and used this tendency to explain why products in many markets are so alike (Hotelling 1929); the idea later became known as the “principle of minimum differentiation”. In 1979 d’Aspremont, Gabszewicz and Thisse showed that Hotelling’s conclusion is invalid: with the linear travel costs he assumed, no price equilibrium exists when the two sellers are fairly close together; if travel cost is the square of distance, a price equilibrium always exists and the sellers move as far apart as possible (d’Aspremont et al. 1979). In 1975 Eaton and Lipsey studied more sellers with fixed prices and found that with three sellers there is no location equilibrium (Eaton and Lipsey 1975).

Calculation

The program has three parts. (1) Prices are fixed and equal; two sellers take turns choosing their best location; then the program checks whether three sellers have a location equilibrium. (2) Linear travel cost t|y−x|t|y – x|, with sellers at aa and 1−a1 – a. Hotelling’s candidate prices are tt each, with profit t/2t/2; the program checks whether it pays one seller to cut her price to “the rival’s price minus the travel cost between them” and take the whole market. (3) Quadratic travel cost t(y−x)2t(y – x)^2; price equilibria are found by best-response iteration, and profit is computed as a function of location. t=1t = 1.

Calculation

# Hotelling's line and its correction. Consumers spread uniformly on [0, 1] buy one unit
# from the seller with the lowest price + travel cost. (1) Fixed, equal prices: sellers
# choose locations only. (2) Linear travel cost t|d| with price competition: Hotelling's
# candidate prices fail when sellers are close (d'Aspremont, Gabszewicz & Thisse 1979).
# (3) Quadratic travel cost t d^2: price equilibria exist for all locations, and sellers
# move APART. t = 1 throughout.
import itertools
G = [i / 20 for i in range(21)]                       # grid of locations

def shares_fixed(locs):          # equal prices: buyers go to the nearest seller
    pts = sorted(set(locs)); cut = [0] + [(u + v) / 2 for u, v in zip(pts, pts[1:])] + [1]
    turf = {x: cut[k + 1] - cut[k] for k, x in enumerate(pts)}
    return [turf[x] / locs.count(x) for x in locs]

a, b = 0.1, 0.9
for _ in range(20):                         # two sellers take turns to best-respond
    a = max(G, key=lambda x: (shares_fixed([x, b])[0], -abs(x - a)))
    b = max(G, key=lambda x: (shares_fixed([a, x])[1], -abs(x - b)))
print(f"fixed prices, two sellers: best replies end at {a:.2f} and {b:.2f}")
G3 = [i / 10 for i in range(11)]
ne = 0
for locs in itertools.combinations_with_replacement(G3, 3):
    s = shares_fixed(list(locs))
    dev = lambda i, x: shares_fixed(list(locs[:i]) + [x] + list(locs[i + 1:]))[i]
    if all(s[i] >= max(dev(i, x) for x in G3) - 1e-9 for i in range(3)):
        ne += 1
print(f"fixed prices, three sellers on an 11-point grid: {ne} location equilibria")

# Linear cost, sellers at a and 1 - a: Hotelling's prices are 1 each (profit 0.5);
# undercutting to the rival's price minus the travel cost between them, 1 - (1 - 2a),
# takes the whole market.
print("linear cost, sellers at a and 1 - a: undercutting profit (vs 0.50), equilibrium?")
for row in ((0.0, 0.1, 0.2), (0.25, 0.3, 0.4)):
    print("   " + "   ".join(f"a = {a:.2f}: {2 * a:.2f} {'yes' if 2 * a <= 0.5 else 'no'}"
                             for a in row))

def demand1(p1, p2, x1, x2):                          # quadratic cost, x1 < x2
    y = (p2 - p1 + x2 * x2 - x1 * x1) / (2 * (x2 - x1))
    return min(1.0, max(0.0, y))

def best_price(p_other, x1, x2, first=True):
    lo, hi = 0.0, 3.0
    f = (lambda p: p * demand1(p, p_other, x1, x2)) if first else \
        (lambda p: p * (1 - demand1(p_other, p, x1, x2)))
    for _ in range(100):                              # golden-section search
        m1, m2 = lo + (hi - lo) * 0.382, lo + (hi - lo) * 0.618
        if f(m1) < f(m2): lo = m1
        else: hi = m2
    return (lo + hi) / 2

def equilibrium(x1, x2):
    p1 = p2 = 0.5
    for _ in range(200):
        p1 = best_price(p2, x1, x2); p2 = best_price(p1, x1, x2, first=False)
    d = demand1(p1, p2, x1, x2)
    return p1, p2, p1 * d, p2 * (1 - d)

print("quadratic cost, sellers at a and 1 - a:   a   price  profit  formula (1 - 2a)/2")
for a in (0.0, 0.1, 0.2, 0.3, 0.4, 0.45):
    p1, _, f1, _ = equilibrium(a, 1 - a)
    print(f"{'':40s}{a:.2f}  {p1:.3f}  {f1:.3f}   {(1 - 2 * a) / 2:.3f}")
prof = [(x, equilibrium(x, 0.7)[2]) for x in (0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6)]
print("seller 2 at 0.70; seller 1's equilibrium profit by its location:")
print("   " + ", ".join(f"{x:.1f}: {f:.3f}" for x, f in prof))
# fixed prices, two sellers: best replies end at 0.50 and 0.50
# fixed prices, three sellers on an 11-point grid: 0 location equilibria
# linear cost, sellers at a and 1 - a: undercutting profit (vs 0.50), equilibrium?
#    a = 0.00: 0.00 yes   a = 0.10: 0.20 yes   a = 0.20: 0.40 yes
#    a = 0.25: 0.50 yes   a = 0.30: 0.60 no   a = 0.40: 0.80 no
# quadratic cost, sellers at a and 1 - a:   a   price  profit  formula (1 - 2a)/2
#                                         0.00  1.000  0.500   0.500
#                                         0.10  0.800  0.400   0.400
#                                         0.20  0.600  0.300   0.300
#                                         0.30  0.400  0.200   0.200
#                                         0.40  0.200  0.100   0.100
#                                         0.45  0.100  0.050   0.050
# seller 2 at 0.70; seller 1's equilibrium profit by its location:
#    0.0: 0.283, 0.1: 0.261, 0.2: 0.234, 0.3: 0.200, 0.4: 0.160, 0.5: 0.114, 0.6: 0.060

With fixed prices, the two sellers’ best responses both end at 0.50: this is “minimum differentiation”, and it holds when prices cannot compete. On an 11-point grid, three sellers have no location equilibrium at all, as Eaton and Lipsey found.

When prices can compete, the conclusion reverses. With linear costs, once the sellers are more than 0.25 from the ends, the profit from undercutting and taking the whole market (0.60 at a=0.3a = 0.3) exceeds the 0.50 earned at Hotelling’s prices, so Hotelling’s candidate prices are no longer an equilibrium; d’Aspremont and colleagues proved that no price equilibrium of any kind then exists. With quadratic costs, symmetric locations aa and 1−a1 – a give equilibrium price 1−2a1 – 2a and profit (1−2a)/2(1 – 2a)/2: 0.5 each when both sit at the ends, only 0.05 when both have moved to 0.45. With the rival fixed at 0.70, seller 1’s equilibrium profit falls steadily from 0.283 at location 0 to 0.060 at location 0.6. The only result of moving closer to the rival is a price war.

Left: price competition with quadratic travel cost. Blue: seller 1’s equilibrium profit with the rival at 0.70; gold, dashed: each seller’s profit when the two are placed symmetrically at a and 1 - a. The nearer the middle, the lower the profit. Right: in the illustrative niche congestion game, the Nash equilibrium (purple) and the allocation with the highest total payoff (green).

Note

What this means for attention markets. Taken together, the two results say that sellers tend to cluster when prices are fixed, and that when prices can compete, clustering costs them their margins through price wars. In many attention markets content is free to users and creators cannot compete on “price”, which is close to Hotelling’s fixed-price case, so the pressure to cluster may be stronger; sellers in homogeneous product categories face price wars directly. This is a conjecture derived from the models, not an empirical finding. The author’s framework notes that Hotelling’s “minimum differentiation” was later corrected; on checking, this is right.

A congestion game of hot niches

Calculation

Thirty sellers each choose one of five “niches”. Niche kk yields total revenue Akn/(n+2)A_k\,n/(n + 2): one more seller attracts a little extra attention, but this soon saturates, and the revenue is shared equally within the niche. Each seller also pays an acquisition cost 0.05n0.05\,n, rising with the number of competitors in the same niche. The payoff per seller in niche kk is thus uk(n)=Ak/(n+2)−0.05nu_k(n) = A_k/(n + 2) – 0.05\,n, with AA = 30 (hot), 18, 18, 10 and 10 (edge). This is a congestion game with payoffs in place of costs, and a potential game. The program finds the Nash equilibria and the allocation with the highest total payoff, computes the loss that one more seller in each niche imposes on the others, makes each seller pay that loss, and finds the equilibrium again. The “digital Braess” network in the last two lines of output is explained in the next section.

Evidence

Auctions make prices depend on rivals. Search advertising widely uses the “generalised second-price” auction: ad positions are ranked by bid, and each advertiser pays the bid of the one ranked below him. Edelman, Ostrovsky and Schwarz analysed the equilibria of this auction in 2007; in them each advertiser’s price is set by others’ bids (Edelman et al. 2007). So the more competitors there are, the higher the price of a given position tends to be. The assumption in the program that acquisition cost rises linearly with the number of competitors is an illustrative stand-in for this structure; its functional form has no empirical basis.

Calculation

# Crowding into the "hot" niche: a congestion game among content sellers (an
# illustrative MODEL, not data about any platform). 30 sellers each pick one of 5 niches
# on a taste line. Niche k yields total revenue R_k(n) = A_k n / (n + 2) (more sellers
# attract a little more attention, with saturation), shared equally, and each seller
# pays an acquisition cost 0.05 n that rises with the number of rivals bidding for the
# same audience. Payoff u_k(n) = R_k(n)/n - 0.05 n.
import itertools, random
rng = random.Random(8)
A = [30, 18, 18, 10, 10]                    # niche 0 is the central "hot" niche
NAMES = ["hot", "near-1", "near-2", "edge-1", "edge-2"]
N, KAPPA, H = 30, 0.05, 2

def u(k, n):
    return A[k] / (n + H) - KAPPA * n if n > 0 else 0.0

def welfare(ns):
    return sum(n * u(k, n) for k, n in enumerate(ns))

def ext(k, n):                              # loss one seller imposes on the n - 1 others
    return (n - 1) * (u(k, n - 1) - u(k, n)) if n > 1 else 0.0

def nash_from(ns, pay):
    ns = list(ns)
    while True:
        moves = [(pay(j, ns[j] + 1) - pay(i, ns[i]), i, j)
                 for i in range(5) for j in range(5)
                 if i != j and ns[i] > 0 and pay(j, ns[j] + 1) > pay(i, ns[i]) + 1e-12]
        if not moves: return ns
        _, i, j = max(moves); ns[i] -= 1; ns[j] += 1

def equilibria(pay):
    eqs = set()
    for _ in range(200):
        start = [0] * 5
        for _ in range(N): start[rng.randrange(5)] += 1
        eqs.add(tuple(nash_from(start, pay)))
    return sorted(eqs)

eqs = equilibria(u)
best = max((c for c in itertools.product(range(N + 1), repeat=4) if sum(c) <= N),
           key=lambda c: welfare(list(c) + [N - sum(c)]))
best = list(best) + [N - sum(best)]
for ns in eqs:
    print(f"Nash allocation {list(ns)}: total {welfare(ns):.2f}; payoff by niche "
          + " ".join(f"{u(k, n):.2f}" for k, n in enumerate(ns)))
print(f"best allocation  {best}: total {welfare(best):.2f}; payoff in hot niche "
      f"{u(0, best[0]):.3f}, edge {u(3, best[3]):.3f}")
ne = list(eqs[0])
print("at the Nash allocation, what one more seller costs the others in each niche:")
print("   " + ", ".join(f"{NAMES[k]} {ext(k, ne[k] + 1):.3f}" for k in range(5)))
taxed = equilibria(lambda k, n: u(k, n) - ext(k, n))
print("with each seller charged the loss she imposes (a congestion charge), equilibria:")
for ns in taxed:
    print(f"   {list(ns)}: total {welfare(ns):.2f}")

# A "digital Braess" network: the same mathematics as Chapter 1 with a convex cost.
# Stage 1: a paid keyword (cost x^2 per customer, x = share of sellers using it) or a
# broad feed (1); stage 2: a crowded marketplace (x^2) or the seller's own shop (1). A
# new tool links the keyword directly to the marketplace at no extra cost. Equilibrium =
# minimum of the potential  k^3/3 + m^3/3 + (1 - k) + (1 - m)  on a grid.
for link in (False, True):
    grid = [(i / 200, j / 200) for i in range(201) for j in range(201 - i)
            if link or i + j == 200]
    phi = lambda g: ((1 - g[1]) ** 3 + (1 - g[0]) ** 3) / 3 + g[1] + g[0]
    p1, p2 = min(grid, key=phi)
    k, m = 1 - p2, 1 - p1                            # loads on keyword and marketplace
    cost = p1 * (k * k + 1) + p2 * (1 + m * m) + (1 - p1 - p2) * (k * k + m * m)
    print(f"{'with' if link else 'without'} the linking tool: shares {p1:.2f}/{p2:.2f}/"
          f"{1 - p1 - p2:.2f}, cost per customer {cost:.2f}")
# Nash allocation [11, 6, 7, 3, 3]: total 53.68; payoff by niche 1.76 1.95 1.65 1.85 1.85
# Nash allocation [11, 7, 6, 3, 3]: total 53.68; payoff by niche 1.76 1.65 1.95 1.85 1.85
# best allocation  [8, 6, 6, 5, 5]: total 55.99; payoff in hot niche 2.600, edge 1.179
# at the Nash allocation, what one more seller costs the others in each niche:
#    hot 2.363, near-1 1.800, near-2 1.750, edge-1 1.150, edge-2 1.150
# with each seller charged the loss she imposes (a congestion charge), equilibria:
#    [8, 6, 6, 5, 5]: total 55.99
# without the linking tool: shares 0.50/0.50/0.00, cost per customer 1.25
# with the linking tool: shares 0.00/0.00/1.00, cost per customer 2.00

At equilibrium, 11 sellers crowd into the hot niche, 6 and 7 into the two next-hottest, and 3 into each edge niche; payoffs per seller are roughly equalised across niches (between 1.65 and 1.95), which is what equilibrium means: no one can gain noticeably by switching niche. The total payoff is 53.68. The allocation with the highest total puts only 8 sellers into the hot niche and 5 into each edge niche, for a total of 55.99, 4.3 % more. The gap is small, consistent with Chapter 2: in structures like this the loss from selfish allocation is usually limited.

More striking is the shape of the allocation. In the optimal allocation, sellers in the hot niche earn 2.600 each and those in the edge niches only 1.179. The optimum thus requires some people to stay in the less lucrative edge niches, which no one would do voluntarily. At equilibrium, one more seller entering the hot niche costs the others 2.363, while one entering an edge niche costs them only 1.150: the entrant into the hot niche collects the average payoff but imposes on others twice the loss of an entrant into an edge niche. If each seller must pay the loss she causes (a congestion charge in the sense of Chapter 3), the unique equilibrium is exactly the optimal allocation [8, 6, 6, 5, 5].

In this model the claim that “differentiated positioning avoids the congestion tax” needs to be stated carefully. For an individual seller at equilibrium, switching to an edge niche is no better (otherwise it would not be an equilibrium); for sellers as a whole, a more dispersed allocation has a higher total payoff. Differentiation pays an individual only if others have not yet spread out (the market is away from equilibrium), or if someone (a platform’s rules or fees) builds the congestion externality into individual payoffs.

A digital Braess paradox

Can a Braess paradox, in which adding an option makes everyone worse off, occur in the niche congestion game? In traffic networks this depends on the topology.

Evidence

Braess’s paradox needs a particular topology. In 2006 Milchtaich proved that in a network with one origin–destination pair, Braess’s paradox can occur if and only if the network is not “series-parallel”; equivalently, if and only if a Wheatstone-bridge structure like that of Chapter 1 is embedded in it (Milchtaich 2006). A set of parallel roads (“choose one niche”) is series-parallel, and adding a road to it cannot worsen the nonatomic equilibrium.

So for a “digital Braess paradox” to occur, the flow of attention must pass through at least two linked stages that both congest, and a new tool must connect them in Braess’s pattern. The second part of the program builds such an illustrative example. In the first stage, a seller acquires customers through a paid keyword (cost x2x^2 per customer, where xx is the share of sellers using it) or a broad traffic channel (cost 1); in the second stage, the sale is closed in a crowded platform marketplace (cost x2x^2) or the seller’s own shop (cost 1). Originally the two routes are “keyword → own shop” and “broad channel → marketplace”. Then a new tool sends keyword traffic straight into the marketplace at no extra charge.

Without the tool, sellers split evenly and the cost per customer is 0.25+1=1.250.25 + 1 = 1.25. With it, every seller uses both the keyword and the marketplace, and the cost per customer becomes 1+1=2.001 + 1 = 2.00, a rise of 60 %. The mathematics is exactly that of Chapter 1, with delay replaced by a convex acquisition cost.

Hypothesis · not established

The digital Braess hypothesis (not yet established). The author conjectures that some “one-stop” marketing tools connect two previously separate congestible stages (for example, a kind of paid traffic and a concentrated sales venue), so that adopters’ average acquisition cost rises after a while, above its level before the tool was introduced. The testable prediction is that in panel data on comparable sellers before and after a tool’s launch, adopters show rising unit costs in both stages at once, and a total unit cost above the pre-launch level, relative to non-adopters (or later adopters). If independent researchers using such data find that adopters’ total unit cost falls or stays the same, the hypothesis is refuted. The author has no such data, and the book uses no client data from the author’s businesses.

Summary

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 equilibrium crowds too many sellers into the hot niche, about 4 % below the optimal total; entering the hot niche imposes twice the loss on others as entering an edge niche, and charging that loss makes the equilibrium optimal. A “digital Braess paradox” requires two linked congestible stages and is an analogy awaiting test. The next chapter turns to how recommender systems allocate exposure.

References

d’Aspremont, Claude, J. Jaskold Gabszewicz, and Jacques-François Thisse. 1979. “On Hotelling’s ‘Stability in Competition’.” Econometrica 47 (5): 1145–50. https://doi.org/10.2307/1911955.
Eaton, B. Curtis, and Richard G. Lipsey. 1975. “The Principle of Minimum Differentiation Reconsidered: Some New Developments in the Theory of Spatial Competition.” Review of Economic Studies 42 (1): 27–49.
Edelman, Benjamin, Michael Ostrovsky, and Michael Schwarz. 2007. “Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords.” American Economic Review 97 (1): 242–59. https://doi.org/10.1257/aer.97.1.242.
Hotelling, Harold. 1929. “Stability in Competition.” The Economic Journal 39 (153): 41–57. https://doi.org/10.2307/2224214.
Milchtaich, Igal. 2006. “Network Topology and the Efficiency of Equilibrium.” Games and Economic Behavior 57 (2): 321–46.

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).