Efficient computation of optimal auctions via reduced forms

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

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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
Issue number3
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


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

Cite this