ICES: Small: Frontiers in Mechanism Design

机制设计研究的问题是，自利参与者的偏好-例如商品的价值或执行一项任务的成本--是决策者未知的先验知识。高层次的目标是设计一种协议或“机制”，与参与者互动，使自利行为产生理想的结果。计算机科学为机制设计的经典经济学理论带来了新的思想和技术。计算机科学方法的一个主要特征是近似性-通过证明其性能始终在理想(且通常无法实现的)解决方案的一个小因素内来为提议的解决方案建立可信度的想法。近似保证是衡量次最优性的基本工具，在机械设计中，由于计算可操纵性限制、博弈论均衡的低效或获得完全最优性的信息理论障碍，次最优性可能会出现。这项研究的目标是：推广收益最大化的先验独立和先验自由拍卖理论；将近似的概念应用于价值相互依赖的拍卖；追求低维竞价空间拍卖的均衡性能保证；以及寻求关于可处理组合拍卖的新结果。首先，机制设计有几个与计算行业高度相关的应用，例如无线频谱的组合拍卖、搜索关键字拍卖以及在线广告和更传统广告的实时分配。这项拟议的研究应用了理论计算机科学的概念和技术，以获得关于机构设计基本模型的新见解，并产生可能与计算机科学应用更密切相关的新模型和结果。第二，项目资金将有助于指导博士生，创新研究生教学，传播技术调查和教育材料，并招募本科生从事研究。

Mechanism design studies problems where the preferences of self-interested participants --- such as a value of a good or a cost of performing a task --- are a priori unknown to the decision-maker. The high-level goal is to design a protocol, or "mechanism," that interacts with participants so that self-interested behavior yields a desirable outcome.Computer science has brought new ideas and techniques to the classical economic theory of mechanism design. A primary signature of the computer science approach is approximation --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. Approximation guarantees are a fundamental tool for measuring suboptimality, which can arise in mechanism design because of computational tractability constraints, the inefficiency of game-theoretic equilibria, or information-theoretic barriers to obtaining full optimality. The goals of the proposed research are: to further the theory of prior-independent and prior-free auctions for revenue maximization; to apply the concept of approximation to auctions with interdependent values; to pursue equilibrium performance guarantees for auctions with low-dimensional bid spaces; and to seek new results on tractable combinatorial auctions.The broader significance and importance of the project are as follows. First, mechanism design has several applications highly relevant tothe computing industry, such as combinatorial auctions for wireless spectrum, search keyword auctions, and the real-time allocation of both online and more traditional advertising. The proposed research applies concepts and techniques from theoretical computer science to obtain new insights about fundamental models in mechanism design, and to produce new models and results that may be more germane for computer science applications. Second, the project funding will enable the mentoring of PhD students, innovation in graduate teaching, the dissemination of technical surveys and educational materials, and the recruitment of undergraduates into research.