Optimal Mechanism Design for Single-Minded Agents

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.