AF: Small: Non-revelation Mechanism Design

AF：小：非暴露机构设计

• 批准号: 1618502
• 负责人: Jason Hartline
• 金额: $ 45万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618502&HistoricalAwards=false
• 关键词: AF; Small; Non; revelation; Mechanism

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.

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