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

点击翻译按钮获取中文摘要

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.