d4-conf-aaai-2017-0012

The strongest positive mirror I believe is Fractional Substitutable Hospital Choice, anchored on the paper’s Theorem 1, proved here (with its detailed proof deferred to the full version). The theorem says that there is a class of substitutable preferences without ties for which *any algorithm needs \(\Omega(2^n)\) preference-oracle queries to compute the induced choice function*, where \(n\) is the number of doctors. The paper’s construction hides a preferred subset among exponentially many possibilities.

In the mirror, an instance has a finite support \(T\) of doctor types, with rational masses \(\mu_t>0\) summing to one. A type completely specifies everything relevant to the matching problem: the doctors’ hospital rankings and the attributes hospitals use to evaluate them. The hospital has an oracle for its strict preference over accepted-mass vectors. Given available supply \(a\), its choice is \(C(a)\in\arg\max_{0\le x\le a} U(x)\), where \(x_t\) is the mass of type \(t\) it accepts. The problem is to compute \(C(\mu)\) exactly using comparisons between such vectors. This is an oracle-query question, matching the paper’s model; it does not claim a standard exponential running-time lower bound.

Use the direct mass analogue of the paper’s rejection form of substitutability: for \(a\le b\), the rejected mass \(a-C(a)\) cannot decrease coordinatewise as supply grows. To see why the hardness has a plausible continuous lift, consider the \(2^\tau\) vectors \(z^S\) with \(z^S_t=\mu_t\) for \(t\in S\) and \(0\) otherwise. A preference oracle can make one unknown \(z^{S^*}\) its uniquely preferred bundle, while ranking all other bundles by a fixed increasing order. Then \(C(a)=z^{S^*}\) when \(z^{S^*}\le a\), and \(C(a)=a\) otherwise. This choice rule satisfies the stated rejection condition. At full supply the answer is the hidden vector \(z^{S^*}\); comparisons reveal which one is hidden only if they query it. Fractional queries therefore need not expose the answer. I expect an \(\Omega(2^\tau)\) query lower bound for this mirror.

A credible regime is a large annual matching market with repeated applicant profiles: for example, many applicants sharing the same hospital rankings and the same modeled credentials, with \(\tau\) such profiles among \(N\) applicants and \(N\gg\tau\). A mass \(x_t\) is the fraction of type \(t\) accepted; each individual doctor still receives an ordinary matched-or-unmatched outcome. This is population continuization, and the paper’s one-hospital case makes choice computation the underlying problem directly. The mirror covers Theorem 1’s choice-function result, not every many-to-one stable-matching result in the paper.

I expect this to be B-style hardness transfer in the oracle model: the hidden combinatorics persist among the type-corner bundles, so increasing multiplicity within types does not remove them. The result also generates useful follow-up questions: whether regular classes of fractional preferences, such as suitably defined concave or submodular valuations, admit efficient exact choice algorithms; whether approximate choice takes fewer queries; and how a choice oracle over masses supports computation of a stable matching across many hospitals.

The soft spot is substantial: the hard preference can be an artificial oracle with a spike at one bundle, and Theorem 1 itself is a query lower bound, not a bit-complexity or NP-hardness result. If the mirror were restricted to smoother economic preferences, the construction might be excluded. But that is also the paper’s stated worst-case question—choice computation across general substitutable preferences—so the mass-vector version remains a recognizable and testable continuous analogue of that particular result.