Optimal Mechanism Design for Single-Minded Agents

Nikhil R. Devanur, Kira Goldner, Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider optimal (revenue maximizing) mechanism design in the interdimensional setting, where one dimension is the 'value' of the buyer, and the other is a 'type' that captures some auxiliary information. A prototypical example of this is the FedEx Problem, for which Fiat et al. [2016] characterize the optimal mechanism for a single agent. Another example of this is when the type encodes the buyer's budget [DW17]. The question we address is how far can such characterizations goIn particular, we consider the setting of single-minded agents. A seller has heterogenous items. A buyer has a valuation vfor a specific subset of items S, and obtains value vif and only if he gets all the items in S(and potentially some others too). We show the following results. Deterministic mechanisms (i.e. posted prices) are optimal for distributions that satisfy the "declining marginal revenue" (DMR) property. In this case we give an explicit construction of the optimal mechanism. Without the DMR assumption, the result depends on the structure of the minimal directed acyclic graph (DAG) representing the partial order among types. When the DAG has out-degree at most 1, we characterize the optimal mechanism àla FedEx; this can be thought of as a generalization of the FedEx characterization since FedEx corresponds to a DAG that is a line. Surprisingly, without the DMR assumption andwhen the DAG has at least one node with an out-degree of at least 2, then we show that there is no hope of such a characterization. The minimal such example happens on a DAG with 3 types. We show that in this case the menu complexity is unboundedin that for any M, there exist distributions over (v,S) pairs such that the menu complexity of the optimal mechanism is at least M. For the case of 3 types, we also show that for all distributions there exists an optimal mechanism of finitemenu complexity. This is in contrast to the case where you have 2 heterogenous items with additive utilities for which the menu complexity could be uncountably infinite [DDT15, MV07]. In addition, we prove that optimal mechanisms for Multi-Unit Pricing (without a DMR assumption) can have unbounded menu complexity as well, and we further propose an extension where the menu complexity of optimal mechanisms can be countably infinite, but not uncountably infinite. Taken together, these results establish that optimal mechanisms in interdimensional settings are both surprisingly richer than single-dimensional settings, yet also vastly more structured than multi-dimensional settings.

Original languageEnglish (US)
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Number of pages64
ISBN (Electronic)9781450379755
StatePublished - Jul 13 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: Jul 13 2020Jul 17 2020

Publication series

NameEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation


Conference21st ACM Conference on Economics and Computation, EC 2020
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Statistics and Probability
  • Computational Mathematics


  • duality
  • interdimensional
  • menu complexity
  • optimal mechanism design
  • partial lagrangian
  • revenue
  • single-minded valuations

Fingerprint Dive into the research topics of 'Optimal Mechanism Design for Single-Minded Agents'. Together they form a unique fingerprint.

  • Cite this

    Devanur, N. R., Goldner, K., Saxena, R. R., Schvartzman, A., & Weinberg, S. M. (2020). Optimal Mechanism Design for Single-Minded Agents. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation (pp. 193-256). [3399454] (EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3391403.3399454