5D Library › Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks · 中文
Preface: Why One More Road Made Traffic Worse
Note
Please read this first. This book introduces several mathematical models from algorithmic game theory on congestion, selfish routing, tolls, recommendation and matching, together with their empirical evidence, and uses short programs to make its arguments. Unless a source is given, the networks, teams, sellers, creators, platforms and data in the book are fictional or synthesised by the programs, and the parameters are illustrative. This book is not investment, business, marketing or legal advice, and it makes no forecasts about any company, platform or market. The models of “traffic pools”, “recommendation algorithms” and “customer-acquisition costs” are schematic models written to show a structure; they describe no real platform’s algorithm and are not empirical studies of any platform.
When concepts from traffic networks (Wardrop equilibrium, the price of anarchy, Braess’s paradox, tolls) are applied to attention markets, approval workflows or partner matching, they are models and analogies: they help us ask better questions, but creators are not cars and teams are not roads.
In 1968 the German mathematician Dietrich Braess published a short paper showing that in a road network in which every driver takes the route that is fastest for himself, adding a new road can make every driver slower (Braess 1968). The German paper received a formal English translation only in 2005 (Braess et al. 2005). The phenomenon it describes became known as Braess’s paradox. It is not caused by road works, accidents or a poor new road; it arises because the new road changes people’s choices, and each person’s choice imposes an unseen delay on others.
This book asks four questions. First, how does the gap between selfish choices and the collective optimum arise, and how large can it be in the worst case? Second, what prices or rules make individual choices coincide with the optimum, and at what cost? Third, in what form does the same structure appear in attention markets, recommender systems and matching markets, and which of these are only analogies? Fourth, can these ideas be tested in a controlled experiment?
What this book covers
Chapter 1 derives Braess’s paradox exactly from Wardrop’s equilibrium and shows how the same equations describe networks of springs and strings and electrical circuits; Chapter 2 discusses the bounds on the price of anarchy and its actual size in random networks; Chapter 3 discusses Pigouvian tolls, the burden on users once they pay, and potential games with finitely many players; Chapter 4 carries these structures over to attention markets: Hotelling’s model and its correction, a congestion game of hot niches, and a “digital Braess paradox”; Chapter 5 discusses exploration and exploitation in recommendation, the Matthew effect and a schematic three-tier traffic pool; Chapter 6 discusses stable matching and the incentive to tell the truth. Chapter 7 reads these studies beside the Annals of Xia in the Shiji, the “Discourses of Zhou” in the Guoyu, the “Measuring the Land” chapter of the Guanzi and the historical records of Dujiangyan, and states where classical experience of water control ends and modern theory begins. Chapter 8 offers a “four-step checklist for congestion and diversion” and a pre-registered group-randomised controlled experiment.
The book borders on several other volumes of 5D Library, which it only recalls briefly without repeating their programs: Volume 6, The Economics of Attention, and Chapters 4 and 5 of Volume 25, Social Network Topology, Structural Holes and Complex Contagion, covered preferential attachment, power laws and PageRank; Volume 27, Mechanism Design, Incentive Compatibility and the Game Theory of Negotiation, covered the revelation principle and the VCG mechanism, which makes each person pay “the loss she causes others”, the same idea as the Pigouvian toll of Chapter 3; Volume 15, The Sandbox, Determinism and Active Inference, discussed how a prior can lead a person into the same trap again and again, which connects with the “exploit, never explore” dilemma of Chapter 5.
Claims corrected after checking
Several statements in the author’s original framework needed correction or qualification after checking. First, in the diamond network of Chapter 1, each of the two routes consists of one road whose delay rises with traffic (delay ) and one road of fixed delay (delay 1), arranged crosswise; it is not that “one road has delay and the other delay 1”. This numerical example is the simplified textbook version; Braess’s own 1968 example has demand 6, with travel time rising from 83 to 92 when the road is added. Taking the shortcut is a weakly rather than strictly dominant strategy: it is never slower, ties with the other routes only when one congestible road is full, and the equilibrium lies exactly at that tie (all three routes take 2). The paradox appears only for demand between 2/3 and 2. Second, in Cohen and Horowitz’s spring experiment what is cut is a short string linking the two springs, not a spring; the electrical analogue uses resistors and Zener diodes. Braess-like behaviour in power grids (Witthaut and Timme 2012) is a loss of synchrony in oscillator models of alternating-current grids, a mechanism different from the isomorphism discussed here. Third, Koutsoupias and Papadimitriou proposed “the ratio of the worst Nash equilibrium to the optimum” in 1999 in a model of load balancing on parallel links, and the name “price of anarchy” comes from Papadimitriou’s 2001 paper; the 4/3 bound (Roughgarden and Tardos 2002) holds only for nonatomic users (each an infinitesimal share of traffic) and linear latencies with non-negative coefficients, and with finitely many players on unsplittable routes the worst case is 5/2; the topology-independent bound for polynomials of degree is from Roughgarden’s 2003 paper. Fourth, marginal-cost tolls do make the selfish equilibrium coincide with the optimum, but if the toll counts as a cost to users, users themselves need not be better off: in Braess’s network “time plus toll” after tolling is still 2, the same as without tolls, and in the example with demand 6 it even rises from 92 to 116. The gain lies in the toll revenue and how it is returned. The potential function for the nonatomic case is due to Beckmann, McGuire and Winsten (1956); Rosenthal’s potential of 1973 concerns congestion games with finitely many players. Fifth, Hotelling’s 1929 conclusion of “minimum differentiation” was, as the framework says, corrected by d’Aspremont, Gabszewicz and Thisse in 1979: with linear transport costs no price equilibrium exists when the sellers are close together, and with quadratic transport costs the sellers move as far apart as possible; with three sellers there is not even a location equilibrium (Eaton and Lipsey 1975). That “acquisition costs soar convexly” is a modelling assumption, not an established empirical law. Sixth, the “digital Braess paradox” is a mathematical analogy: Braess’s paradox can occur only in networks that are not series-parallel (Milchtaich 2006), and a simple “choose one niche” structure cannot produce it. Seventh, the evidence on “filter bubbles” is disputed: a large Facebook study found that individuals’ own choices limited exposure to cross-cutting content more than the ranking algorithm did, and a randomised experiment during the 2020 US election that switched feeds to chronological order for three months did not significantly change political polarisation. Eighth, the properties of the Gale–Shapley algorithm are as the framework states, with the addition that truth-telling is a dominant strategy for the proposing side but not for the receiving side; the 2012 Nobel Memorial Prize in Economic Sciences was shared by Roth and Shapley (Gale had died in 2008). Ninth, the classical texts: in the Annals of Xia, “Yu was quick and diligent” and “he lived in humble rooms and spent his means on the ditches” are two separate passages, and the received text reads gouxu (淢, equivalent to 洫, field ditches), not goujian; “dredge the shoals deep, build the weir low” does not appear in the Shiji or the Huayang Guozhi accounts of Li Bing and is a later maxim for maintaining the weir; the diversion and desilting at the Fish Mouth, Flying Sand Weir and Bottle-Neck Channel depended on annual maintenance across the dynasties and were not “free of human intervention”. Tenth, the Chapter 8 experiment uses six-person groups, smaller than the groups of about 18 in the experiments of Rapoport and colleagues (2009); “deducting congestion points” is itself a toll, so the trial tests a combination of information and price. Each chapter states these points in place, and they are collected in the editorial notes published with the book.
How to read the boxes
As in other volumes of 5D Library, different kinds of statement are marked separately.
Evidence
Evidence boxes report published research findings, with sources.
Calculation
Calculation boxes give formulas and short Python programs. Every program runs unchanged in a standard Python 3 environment using only the standard library, and its actual output is printed beneath it. The “drivers”, “sellers”, “creators”, “teams” and data in the book are fictional or synthesised by the programs; parameters are illustrative values, not estimates for any real system.
Hypothesis · not established
Hypothesis boxes contain the author’s ideas, are marked “not yet established”, and state what result would show them to be wrong.
Source text
Source boxes quote classical texts, with the author’s explanation.
Note
Note boxes give cautions and explain choices.
About this edition
This is version 1.0.0, the first complete edition: a preface and eight chapters, in Chinese and English. The book contains 16 programs and 4 vector figures. The text, boxes and code were drafted with an AI writing tool from the author’s title, framework and notes; the author is responsible for reviewing and revising them and for checking every source. Corrections and missing references are welcome through the 5D Library website.
Disclosure
The author uses the works of 5D Library, including this book, as the methodological basis of his community courses, the 5D Ascension Cards (Dimensional Shift Card Decks) and the Yafu AI knowledge base, and therefore has a commercial interest in the subject of this book. The author also founded and runs Asia Influencer X and Yafu Global, whose business includes multi-platform traffic distribution and digital-marketing networks, and therefore has a direct commercial interest in the subject of this book. The book promotes no course, card deck or service, is not investment or business advice, and uses no client data from these businesses; the Chapter 8 trial is designed to be run and analysed by researchers independent of the author’s business and does not recruit from the author’s community, students or customers, including the clients of these businesses; all the code and the study protocol are published openly for anyone to check.
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).