English
Some computational systems serve participants who choose actions in their own interests. A routing rule, auction, or allocation algorithm changes those choices, which in turn changes the system’s inputs. Economics supplies models of preferences and strategic interaction; computer science asks how the resulting rules and outcomes can be computed.
The central distinction is between optimizing a fixed input and designing a system whose participants respond to the rule. An algorithm that works well when everyone reports honestly may fail when reporting a different value gives a participant an advantage. Incentives therefore become part of the specification.
Background: Algorithms (§2.6), probability (§2.5), optimization (§2.4, §5.2), and complexity (§3.3). Game theory adds explicit assumptions about players, available actions, information, and objectives.
The Relationship: Where Strategy Meets Computation
Algorithmic Game Theory: The Computation of Strategic Interaction
A Nash equilibrium is a profile of strategies in which no player improves their expected payoff by changing only their own strategy. It is a stability condition relative to the modeled options and payoffs. It need not be socially desirable, unique, or a prediction that people will reach it.
Matching pennies makes mixed strategies concrete. Each of two players chooses heads or tails. One receives one unit when they match and loses one otherwise; the other receives the opposite payoff. Any fixed pair lets one player improve by switching. If each independently chooses heads with probability one half, neither can improve their expected payoff by a unilateral change. The expected payoff is zero, although each actual round still has a winner and loser.
Nash’s existence theorem ensures a mixed-strategy equilibrium for finite games, but existence does not give an efficient general method. Computing an equilibrium of a general two-player game with rational payoffs is PPAD-complete. This is a complexity classification for a search problem with guaranteed solutions, not a proof that every game is hard or that equilibria never occur. Special game structures, approximation goals, and the dynamics of learning require separate analysis.
The price of anarchy compares the worst equilibrium with a specified social optimum. Consider a divisible unit of traffic with individually negligible travelers and two routes: one has travel cost x when fraction x uses it, and the other has constant cost one. All traffic on the first route is an equilibrium with average cost one. The average cost is x² + (1 - x) = (x - 1/2)² + 3/4, which is minimized at x = 1/2. The optimal split therefore costs 3/4, and the equilibrium-to-optimum ratio is 4/3. The example explains how individually reasonable choices can impose a shared congestion cost. Its conclusion depends on the route costs and traffic model.
Mechanism Design: Engineering the Rules of the Game
Mechanism design chooses rules for interaction: what participants report, how an outcome is selected, and what transfers or payments occur. State the goal first. Maximizing revenue, total value, access, and stability are different goals and may favor different rules.
In a sealed-bid second-price auction for one item, the highest bidder wins and pays the highest other bid. Under the standard private-value model with utility equal to value minus payment, truthful bidding is a weakly dominant strategy. If your value is ten and the highest competing bid is seven, bidding ten wins at price seven, giving utility three; bidding six loses a beneficial purchase. If the competing bid is eleven, bidding twelve would instead win at a loss, while bidding ten avoids it. Your report changes whether you win, but not the competing price you pay when you win.
The guarantee depends on the model, including the payment rule and assumptions about preferences and participation. Collusion, external effects, or budget constraints may change the analysis. Multi-slot advertising auctions with similar names need their own reasoning; the single-item result cannot be transferred just because both use a second-price idea.
VCG mechanisms generalize truthful reporting in suitable settings by selecting an outcome that maximizes reported total value and charging for external effects on others. Computing that outcome can itself be difficult, and replacing it with an arbitrary approximation can change incentives. Economic and computational requirements must therefore be checked together.
Matching without payments poses other questions. Deferred acceptance can produce a stable matching under its model: there is no unmatched pair who both prefer each other to their assignments. Stability is not the same as equal satisfaction, and the side making proposals matters. Real matching programs can add capacities, couples, or eligibility rules that require further analysis.
Computation as a Constraint on Economic Rationality
Bounded rationality was already a concern in economics and psychology, including Herbert Simon’s work. Computational complexity gives one way to make resource limits precise. A model that assumes a participant repeatedly solves an optimization problem should account for the time, information, and representation needed to do so.
NP-hardness is a statement about a family of problems in a specified formulation. Under the usual assumption that P differs from NP, it rules out a general polynomial-time exact algorithm for all instances; it does not say that every instance is unsolvable. Small inputs, special structure, approximation, and heuristics may still be useful. Likewise, a worst-case equilibrium result does not establish how quickly a particular market or learning process behaves.
Interaction can change the target while computation is running. Participants learn, information arrives, and others change their actions. Ask whether the proposed update rule converges, oscillates, or only achieves a weaker performance guarantee. An equilibrium analysis and a model of how participants reach an outcome are different contributions.
For a computer system, make incentives as explicit as resource constraints. A rate limit per account may encourage creating extra accounts; a reward for one measured quantity may encourage improving that quantity while neglecting the intended task. State what an agent can observe and change, how deviations are detected, and which behavior the rule rewards. A strategic model does not cover every malicious or irrational action, so it complements rather than replaces security and reliability analysis.
What This Perspective Changes
When participants can respond to a system’s rules, include their choices in the model. Separate existence of an outcome, cost of finding it, incentives to follow it, and evidence that it is reached in practice.
Work through the second-price example with several valuations and competing bids, then change the payment rule and recheck the argument. The exercise shows why a mechanism’s properties belong to its exact rules and assumptions, not to the general label “auction.”
Resources
Foundational and Bridging Texts
Roughgarden’s Twenty Lectures offers a route from auctions to routing and equilibrium computation. Nisan and colleagues provide a broader reference. Osborne develops game-theory foundations, while Roth connects matching and market design to institutional requirements. Work through a small game or mechanism before interpreting a general theorem about it.
| Resource | Role | Type |
|---|---|---|
| Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory (free) | Reference on algorithms, incentives, and equilibria | Reference |
| Roughgarden, Twenty Lectures on Algorithmic Game Theory | A lecture-based introduction with worked arguments | Entry |
| Roth, Who Gets What — and Why | Matching and market design in institutions | Entry |
| Osborne, An Introduction to Game Theory | Players, strategies, information, and equilibrium | Depth |
Key Results and Applications
The CS364A auction lecture derives the incentive property of second-price auctions. Chen, Deng, and Teng’s two-player equilibrium result specifies the complexity claim used above; read it alongside the Daskalakis and colleagues work already listed. Routing, auction, and matching references develop different models, so keep their assumptions separate. Social-good mechanism design and ACM EC provide applications in which institutional constraints are part of the problem.
| Resource | Role | Type |
|---|---|---|
| Roughgarden CS364A course (free) | Lectures and exercises on algorithms and incentives | Entry |
| Mechanism Design for Social Good (free) | Mechanism design with public-interest objectives | Reference |
| ACM EC proceedings / SIGecom resources (often free) | Research on economics and computation | Reference |
| Daskalakis et al., PPAD-completeness of Nash | Computational complexity of equilibrium problems | Depth |
| Roughgarden, Selfish Routing and the Price of Anarchy | Selfish routing and efficiency loss | Depth |
| Krishna, Auction Theory (2nd ed.) | Auction models and incentive analysis | Depth |
| Gale & Shapley, deferred acceptance (1962) | Stable matching and deferred acceptance | Depth |
Traps
| Trap | Why it misleads | Better response |
|---|---|---|
| Confusing equilibrium with efficiency or observed behavior | Stability under unilateral deviations does not establish either. | State the social objective and analyze the process of reaching outcomes. |
| Reading worst-case hardness as every instance being impossible | Complexity depends on the problem family, representation, and required accuracy. | Look for special structure and distinguish exact from approximate goals. |
| Transferring incentive guarantees after changing the rules | Allocation, payment, and preference assumptions jointly determine the result. | Recheck strategic behavior for the implemented mechanism. |
中文
有些计算系统服务于按自身利益选择行动的参与者。路由规则、拍卖或分配算法会改变这些选择，进而改变系统输入。经济学提供偏好与策略交互的模型；计算机科学考察怎样计算相应规则与结果。
关键区别是：对固定输入进行优化，与设计参与者会根据规则作出反应的系统，并不是同一任务。一个在人人诚实报告时表现良好的算法，如果谎报能带来好处，就可能失效。因此，激励需要成为规格的一部分。
背景知识：算法（§2.6）、概率（§2.5）、优化（§2.4、§5.2）与复杂度（§3.3）。博弈论还需要明确参与者、可选行动、信息和目标。
这种关系：策略与计算相遇之处
算法博弈论：策略互动的计算问题
Nash 均衡是一组策略：任何参与者只改变自己的策略，都不能提高预期收益。它是在给定行动与收益模型下的稳定条件，不必然符合社会目标、不必然唯一，也不保证人们会到达它。
猜硬币正反的对抗可以说明混合策略。两位参与者各选正面或反面。相同时，一方获得一个单位，否则损失一个单位；另一方收益相反。任意固定选择组合，都会让其中一方能通过改变选择获益。如果双方独立地以二分之一概率选择正面，任何一方单独改变策略，都不能提高预期收益。预期收益为零，但实际每轮仍然有输赢。
Nash 的存在定理保证有限博弈具有混合策略均衡，但存在性不等于高效的一般求解方法。计算一般双人、有理收益博弈的均衡，是 PPAD 完全问题。这是在保证有解的搜索问题中的复杂度分类，不能证明每个博弈都难，也不能证明均衡从不出现。特殊博弈结构、近似目标和学习动态，需要分别分析。
无政府代价比较最差均衡与指定的社会最优结果。考虑可分割的一个单位交通流，每位出行者的影响可忽略不计，两条路线中，第一条在比例 x 的流量使用时成本为 x，第二条成本恒为一。全部流量走第一条，构成平均成本为一的均衡。平均成本为 x² + (1 - x) = (x - 1/2)² + 3/4，在 x = 1/2 时最小。因此，最优分流的成本为 3/4，均衡与最优成本之比为 4/3。例子说明，个体合理选择可以产生共同承担的拥堵成本。结论依赖所给路线成本与交通模型。
机制设计：设计游戏规则的工程
机制设计选择交互规则：参与者报告什么，怎样选择结果，以及发生哪些转移或支付。应先说明目标。收入最大、总价值最大、可获得性和稳定性，是不同目标，可能需要不同规则。
在单件物品的密封第二价格拍卖中，最高出价者获胜，支付其他出价中的最高价。在标准私人估值模型中，效用等于价值减去支付，诚实出价是弱占优策略。如果你的估值为十，竞争者最高出价为七，出价十会以七成交，效用为三；出价六则失去一次有利购买。如果竞争者出价十一，出价十二反而会亏损成交，而出价十可以避免亏损。你的报告改变是否获胜，但获胜时支付的竞争价格并不由自己的出价决定。
保证依赖模型，包括支付规则，以及关于偏好和参与的假设。串通、外部影响或预算限制，都可能改变分析。名称相似的多广告位拍卖也需要独立推理；不能仅因为两者都使用第二价格思想，就直接移植单物品结论。
VCG 机制在适用场景下推广诚实报告：选择使报告总价值最大的结果，并根据给别人造成的外部影响收费。计算这一结果本身可能很困难，随意换成近似算法还可能改变激励。因此，经济要求与计算要求必须一起检查。
不使用支付的匹配提出其他问题。延迟接受算法可以在其模型下产生稳定匹配：不存在尚未彼此匹配、却都更喜欢对方而非当前分配的双方。稳定不等于满意程度相同，提出申请的一方也会影响结果。实际匹配项目可能加入容量、成对参与者或资格规则，需要进一步分析。
计算作为经济理性的约束
有限理性早已是经济学与心理学关心的问题，包括 Herbert Simon 的工作。计算复杂度提供了一种精确表达资源限制的方法。如果模型假定参与者反复求解某个优化问题，就应考虑所需时间、信息与表示方式。
NP 困难性是在指定形式下，关于一族问题的陈述。在通常的 P 不等于 NP 假设下，它排除了适用于所有实例的通用多项式时间精确算法，却不表示每个实例都无法求解。小输入、特殊结构、近似与启发式方法，仍可能有用。同样，均衡的最坏情况结果，也不能确定某个具体市场或学习过程有多快。
交互可能在计算过程中改变目标。参与者学习，新信息到来，其他人也改变行动。需要问所建议的更新规则会收敛、振荡，还是只能达到较弱的性能保证。均衡分析，与说明参与者怎样到达结果的模型，是不同贡献。
对于计算系统，应像明确资源约束那样明确激励。按账户限流可能鼓励创建额外账户；奖励某个测量指标，可能鼓励只改善指标而忽略原任务。说明行动者能观察和改变什么、怎样发现偏离，以及规则奖励什么行为。策略模型不能覆盖所有恶意或非理性行动，因此它补充安全与可靠性分析，而不能替代两者。
这种视角会改变什么
当参与者会对系统规则作出反应时，就把他们的选择纳入模型。区分结果是否存在、求解成本、遵循结果的激励，以及实际能否到达的证据。
用几组估值与竞争出价检查第二价格例子，再改变支付规则，重新检查论证。这个练习说明，机制性质属于精确规则及其假设，而不是“拍卖”这个一般名称。
资源
基础与桥接文本
Roughgarden 的《Twenty Lectures》提供从拍卖到路由与均衡计算的学习路线，Nisan 等人的教材适合更广泛查阅。Osborne 发展博弈论基础，Roth 则把匹配和市场设计联系到制度要求。阅读一般定理之前，先算清一个小型博弈或机制。
| 资源 | 作用 | 类型 |
|---|---|---|
| Nisan、Roughgarden、Tardos & Vazirani，Algorithmic Game Theory（免费） | 算法、激励与均衡参考 | 参考 |
| Roughgarden，Twenty Lectures on Algorithmic Game Theory | 通过讲义与推导入门 | 入门 |
| Roth，Who Gets What — and Why | 制度中的匹配与市场设计 | 入门 |
| Osborne，An Introduction to Game Theory | 参与者、策略、信息与均衡 | 深入 |
关键结果与应用
CS364A 拍卖讲义推导第二价格拍卖的激励性质。Chen、Deng 和 Teng 的双人博弈均衡结果明确给出了前文使用的复杂度结论，可以与表中 Daskalakis 等人的工作结合阅读。路由、拍卖与匹配参考文献发展不同模型，不应混用假设。面向社会公益的机制设计与 ACM EC 提供了把制度约束纳入问题的应用。
| 资源 | 作用 | 类型 |
|---|---|---|
| Roughgarden CS364A 课程（免费） | 算法与激励的讲义和练习 | 入门 |
| Mechanism Design for Social Good（免费） | 具有公共利益目标的机制设计 | 参考 |
| ACM EC 论文集 / SIGecom 资源（通常免费） | 经济学与计算的研究 | 参考 |
| Daskalakis 等，纳什均衡的 PPAD 完全性 | 均衡问题的计算复杂度 | 深入 |
| Roughgarden，Selfish Routing and the Price of Anarchy | 自私路由与效率损失 | 深入 |
| Krishna，Auction Theory（第 2 版） | 拍卖模型与激励分析 | 深入 |
| Gale & Shapley，延迟接受算法（1962） | 稳定匹配与延迟接受算法 | 深入 |
陷阱
| 误区 | 为什么会误导 | 更好的做法 |
|---|---|---|
| 混淆均衡、效率与实际行为 | 对单方偏离稳定，不能证明后两者。 | 明确社会目标，并分析到达结果的过程。 |
| 把最坏情况困难读成每个实例都不可能 | 复杂度取决于问题族、表示与精度要求。 | 寻找特殊结构，区分精确与近似目标。 |
| 改变规则后直接沿用激励保证 | 分配、支付与偏好假设共同决定结果。 | 针对实际机制重新检查策略行为。 |