Efficient computation of optimal auctions via reduced forms

Saeed Alaei, Hu Fu, Nima Haghpanah, Jason D Hartline, Azarakhsh Malekian

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1058-1086
Number of pages29
JournalMathematics of Operations Research
Volume44
Issue number3
DOIs
StatePublished - Jan 1 2019

Keywords

  • Auctions
  • Dimensionality reduction
  • Polymatroid constraints
  • Reduced forms

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Efficient computation of optimal auctions via reduced forms'. Together they form a unique fingerprint.

  • Cite this