AF: Small: Non-revelation Mechanism Design

机制设计管理向战略(即自私)代理人分配货物问题的协议设计，并在计算机科学和经济学中都有应用。这样的分配问题随处可见：广告商通过在线搜索引擎在拍卖中竞争，在查询回复旁边发布他们的链接；互联网流量竞争路由器接入；小学生竞争精英磁石学校的有限名额。这些过程可以达到不同的目标：搜索引擎想要最大化广告销售的收入；互联网想要最小化所有用户的总通信延迟；学区想要尊重学校分配的公平性。从历史上看，机制设计的研究几乎完全集中在对代理来说简单的机制上，要求真实地透露自己的偏好符合每个代理的最佳利益。这种机制被称为启示机制。由此产生的机制往往既有复杂的规则，又依赖于对环境的详细假设。该项目发展了非披露机制的设计和分析理论，该机制可能需要代理人进行战略优化，但简单而健壮。这个项目的更广泛的影响包括对经济学文献的贡献，为工业中的机制设计提供信息的理论的发展，以及对本科生和博士生的培训，他们将在软件开发工作和研究中使用所开发的技能。本项目将解决非启示性机制设计的一些基本问题。首先，简单的非揭示机制可能有需要根据环境调整的参数，而这个环境可能不是固定的。例如，供应和需求可能都在演变。该项目的一个目标是了解既有良好性能又可以从机构的历史数据直接调整的机构族，并确定执行这种调整的统计上有效的程序。第二，一个特别稳健的设计标准是机构在任何环境条件下都表现良好；即，没有任何参数化。该项目将调查稳健的非披露机制的设计，并量化对非披露机制的稳健保证可能在多大程度上好于对披露机制的最佳稳健保证。第三，在非披露机制中，真实的披露不是代理人的最佳反应，代理人将需要战略性地采取行动。代理可能会发现，只有在一些试验和错误之后，例如通过学习算法，才能采取战略性的好行动。当所有代理都这样行为时，产生的操作将相互关联。该项目旨在研究机构在这种自然动力学条件下的性能及其收敛特性。

Mechanism Design governs the design of protocols for problems of allocation-of-goods to strategic (i.e., selfish) agents and has applications in both computer science and economics. Such allocation problems are all around: advertisers compete in an auction through online search engines to post their links beside query responses; Internet traffic competes for router access; elementary students compete for a limited number of openings in an elite magnet school. These processes can aim to achieve different objectives: search engines want to maximize revenue from ad sales; the Internet wants to minimize the total communication delays of all users; school districts want to respect fairness in school assignments.Historically, research in mechanism design focuses almost exclusively on mechanisms that are simple for the agents, requiring that it is in each agent's best interest to truthfully reveal its preference. Such mechanisms are known as revelation mechanisms. The mechanisms that result often both have complex rules and are dependent on detailed assumptions about the environment. This project develops the theory for design and analysis of non-revelation mechanisms, which may require strategic optimization by the agents, but are simple and robust. Broader impacts of this project include contribution to the economics literature, development of theory that informs the design of mechanisms in industry, and the training of undergraduates and Ph.D. students who will use the developed skills in software development jobs and research.This project will address a number of foundational questions in non-revelation mechanism design. First, simple non-revelation mechanisms may have parameters that need to be tuned to the environment and this environment may not be stationary. For example, both supply and demand may be evolving. A goal of the project is to understand families of mechanisms that both have good performance and can be tuned directly from historical data from the mechanism, and to identify statistically efficient procedures for performing this tuning.Second, an especially robust criterion for design is that the mechanism perform well under any environmental conditions; i.e., without any parameterization. The project will investigate the design of robust non-revelation mechanisms and quantify the extent to which robust guarantees for non-revelation mechanisms may be better than the best robust guarantees possible for revelation mechanisms. Third, in non-revelation mechanisms, where truthful revelation is not an agent's best response, agents will need to take actions strategically. Agents may find strategically good actions may only come after some trial and error, e.g., via learning algorithms. When all agents are behaving thus, the resulting actions will be correlated. The project aims to study the performance of mechanisms under such natural dynamics and their convergence properties.