算法与理论计算机2018arxiv.org
复杂性理论、博弈论与经济学
Complexity Theory, Game Theory, and Economics
进阶 · 约 90 分钟读完前置知识：算法复杂度基础、概率论基础、微观经济学基本概念
导读
这篇论文（讲义）探讨复杂性理论、博弈论与经济学的交叉领域，即算法博弈论，研究计算复杂性如何影响博弈均衡与经济机制设计。据 arXiv 摘要，文章不假设读者具备博弈论背景，面向希望了解该领域的读者。
HN 关注点：计算机科学与经济学的交叉领域，讨论焦点集中在相关学习资源和博弈论概念的理解上。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
补充推荐一本免费的算法博弈论/多智能体系统教材作为补充资料
对计算机科学与经济学交叉领域感兴趣的人，我强烈推荐免费开放的《Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations》（Yoav Shoham 和 Kevin Leyton-Brown 著）。
lpage查看英文原文
For those interested in the intersection of computer science and economics, I highly recommend the freely available Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations by Yoav Shoham and Kevin Leyton-Brown [1]. [1] http://www.masfoundations.org/mas.pdf
质疑以石头剪刀布为例质疑教科书对混合策略均衡的标准表述
用石头剪刀布和一个 AI 引擎做实验时，我偶然发现教科书答案有个瑕疵：并不一定要求双方都以随机方式出三种选项，只要有一方随机出招即可达到均衡，此时另一方可以任意选择策略，包括 100% 只出某一种。
bluetwo查看英文原文
Using Rock-Paper-Scissors and an AI engine I stumbled across a bit of a flaw in the textbook answer around this game. The solution is not necessarily that both players will play all three options randomly. It is only necessary for ONE player to play randomly in order to reach an equilibrium. The other player at that point is free to pick any strategy they choose, including playing a single option 100% of the time.
补充询问阅读该论文所需的预备知识
文章说不要求博弈论背景，那需要什么样的背景呢？
elbear查看英文原文
The article says that no background in game theory is assumed. What kind of background is required though?
亲历以自身经历印证该交叉领域的价值
很好的资源。（一名应用数学家，经由微分博弈论和算法博弈论最终进入了宏观经济学领域。）
qubex查看英文原文
Very nice resource. (Applied mathematician that ended up in macroeconomics by way of differential and algorithmic game theory).
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2018Hacker News 讨论帖208 分 · 28 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选