Efficient Computation of Optimal Auctions via Reduced Forms

• 成果类型: Article
• 署名作者: Alaei, Saeed; Fu, Hu; Haghpanah, Nima; Hartline, Jason; Malekian, Azarakhsh
• 署名单位: Alphabet Inc.; Google Incorporated; University of British Columbia; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Northwestern University; University of Toronto
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0958
• 发表日期: 2019
• 页码: 1058-1086
• 关键词: Mechanism design; implementation; incentives; prices

摘要

We study an optimal auction problem for selecting a subset of agents to receive an item or service, whereby each agent's service can be configured, the agent has multidimensional preferences over configurations, and there is a limit on the number of agents that can be simultaneously served. We give a polynomial time reduction from the multiagent problem to appropriately defined single-agent problems. We further generalize the setting to matroid feasibility constraints and obtain exact and approximately optimal reductions. As applications of this reduction we give polynomial time algorithms for the problem with quasi-linear preferences over configurations or with private budgets. Our approach is to characterize, and in polynomial time optimize and implement feasible interim allocation rules. With a single item, we give a new characterization showing that any mechanism has an ex post implementation as a simple token-passing process. These processes can be parameterized and optimized with a quadratic number of linear constraints. With multiple items, we generalize Border's characterization and give algorithms for optimizing interim and implementing ex post allocation rules. These implementations have a simple form; they are randomizations over greedy mechanisms that serve types in a given order.