AF: Small: Duality-based tools for simple vs. optimal mechanism design and applications to cryptocurrency

传统上，我们认为算法是为了“产生输出”而“处理输入”。例如，设想一家公司试图在其员工之间分配各种资源：它可能会向每个员工询问每种资源如何影响他们的生产率(“投入”)，并以最大化总生产(“产出”)的方式分配资源。当每个用户都有相同的目标(最大限度地提高公司的生产力)时，传统的算法范式完美地捕捉到了公司的目标。如果相反，我们希望对云计算服务进行建模，在其用户之间分配各种资源，会发生什么？现在，个人用户的目标(最大化他们自己的生产力)与服务的目标不一致。因此，用户可能会操纵部署的任何算法，以提高自己的生产率，这可能是以牺牲他人的生产率为代价的。为这些领域设计适当的解决方案不可避免地需要机制设计，这既利用了算法工具，也利用了博弈论工具。作为该项目的一部分，国际计算机协会正在开发一门新的本科课程“经济学与计算”，以向下一代计算机科学家提供严格推理用户与其系统交互的动机的能力。许多先前的工作规定了在实践中无法使用的极其复杂的机制，激励国际协会和其他人以前的工作来研究简单机制的理论属性。本项目的主要研究重点是通过严谨的理论基础，极大地扩大我们对如何适当部署简单机构的理解。作为该项目的一部分，PI将继续提供讲座和教程，介绍用于获得这些新结果的具体方法，称为“二元论”。该项目的次要重点是应用这些理论基础来解决比特币这一新兴加密货币中出现的加密货币激励问题。尽管比特币在很大程度上仍不受传统安全漏洞的影响，但人们已经发现了许多激励问题，如果解决不好，这些问题可能会破坏比特币未来的安全性。作为这个项目的一部分，PI将通过教程帮助扩大其他机构设计者在这个方向上的参与。更详细地说，这个项目的主要研究重点旨在回答这样的问题，例如：一个环境的什么属性使简单的机构合适或不合适？或者“从数量上讲，一个机制需要有多‘复杂’才能‘接近’最优？”这种方法的主要技术成分是PI和合著者最近开发的一个新的对偶框架。次要重点具体旨在朝着一种激励兼容的加密货币协议取得进展：在该协议中，所有用户都被激励认真遵守该协议，即使他们拒绝这样做的情况没有被发现。虽然PI的重点将是这种协议的理论基础，但任何发现都将由实验(模拟)或经验(数据)研究跟进。

Traditionally, we think of algorithms as "processing an input" in order to "produce an output." For example, imagine a firm trying to allocate various resources among its employees: It might solicit from each employee how each resource affects their productivity (the "input"), and allocate the resources in a way to maximize the total production (the "output"). When each user has the same goal (maximize the firm's productivity), the traditional algorithmic paradigm perfectly captures the firm's objective. What if instead we wish to model a cloud computing service allocating various resources among its users? Now, the goals of the individual users (maximize their own productivity) are misaligned with that of the service. Therefore, users may manipulate whatever algorithm is deployed in order to improve their own productivity, possibly at the cost of others'. Properly designing solutions for such domains inevitably requires mechanism design, which makes use of both algorithmic and game theoretic tools. As part of this project, the PI is developing a new undergraduate course "Economics and Computation" in order to provide the next generation of computer scientists with the ability to reason rigorously about the incentives of users who interact with their systems. Much prior work prescribes wildly complex mechanisms which are unusable in practice, motivating prior work of the PI and others to investigate the theoretical properties of simple mechanisms. The main research focus of this project is to greatly expand our understanding of how to appropriately deploy simple mechanisms, via a rigorous theoretical foundation. As part of this project, the PI will continue giving talks and tutorials about the specific approach used to obtain these new results, referred to as a "duality theory." A secondary focus of this project is to apply these theoretical foundations to resolve cryptocurrency incentive issues arising within Bitcoin, an emerging cryptocurrency. While Bitcoin has remained largely immune to traditional security breaches, numerous incentive issues have been discovered which could undermine its future security if not properly addressed. As part of this project, the PI will help broaden participation by other mechanism designers in this direction via tutorials. In a little more detail, the main research focus of this project aims to answer questions such as "what properties of a setting make simple mechanisms appropriate or inappropriate?" or "Quantitatively, how 'complex' does a mechanism need to be in order to be 'close' to optimal?" The main technical ingredient in this approach is a novel duality framework recently developed by the PI and co-authors. The secondary focus aims specifically to make progress towards an incentive compatible cryptocurrency protocol: one where all users are incentivized to follow the protocol in earnest, even when their refusal to do so goes undetected. While the PI's focus will be on the theoretical foundations of such a protocol, any findings will be followed up by experimental (simulations) or empirical (data) research as well.