  We consider revenue-optimal mechanism design in the interdimensional setting,
where one dimension is the 'value' of the buyer, and one is a 'type' that
captures some auxiliary information. One setting is the FedEx Problem, for
which FGKK [2016] characterize the optimal mechanism for a single agent. We
ask: how far can such characterizations go? In particular, we consider
single-minded agents. A seller has heterogenous items. A buyer has a value v
for a specific subset of items S, and obtains value v iff he gets (at least)
all the items in S. We show:
  1. Deterministic mechanisms are optimal for distributions that satisfy the
"declining marginal revenue" (DMR) property; we give an explicit construction
of the optimal mechanism.
  2. Without DMR, the result depends on the structure of the directed acyclic
graph (DAG) representing the partial order among types. When the DAG has
out-degree at most 1, we characterize the optimal mechanism a la FedEx.
  3. Without DMR, when the DAG has some node with out-degree at least 2, we
show that in this case the menu complexity is unbounded: for any M, there exist
distributions over (v,S) pairs such that the menu complexity of the optimal
mechanism is at least M.
  4. For the case of 3 types, we show that for all distributions there exists
an optimal mechanism of finite menu complexity. This is in contrast to 2
additive heterogenous items or which the menu complexity could be uncountable
[MV07; DDT15].
  In addition, we prove that optimal mechanisms for Multi-Unit Pricing (without
DMR) can have unbounded menu complexity. We also propose an extension where the
menu complexity of optimal mechanisms can be countable but not uncountable.
  Together these results establish that optimal mechanisms in interdimensional
settings are both much richer than single-dimensional settings, yet also vastly
more structured than multi-dimensional settings.
