d4-conf-aaai-2017-0012 (d4-conf-aaai-2017-0012)

Given a finite support \(T\) of \(\tau\) complete doctor types with rational masses \(\mu_t>0\), and a strict preference-comparison oracle over fractional accepted-mass vectors, determine the exact oracle-query complexity of computing the hospital’s unique choice \(C(\mu)=\max_{\succ}\{x:0\le x\le\mu\}\), for preferences whose rejected mass is coordinatewise nondecreasing as supply increases.

A society is given by its support: a list \(T\) of \(\tau\geq1\) doctor types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; types distinguish all attributes relevant to hospital preferences.
Consider one hospital, so \(m=1\), and let \(L\) be the total bit length of the support descriptions and masses. Accepted-mass vectors range over \(B(\mu)=\{x\in\mathbb R^T:0\leq x\leq\mu\}\), with coordinatewise inequalities.
The hospital has a strict total order \(\succ\) on \(B(\mu)\). For every supply \(s\in B(\mu)\), assume the maximum \(C(s)=\max_{\succ}\{x:0\leq x\leq s\}\) exists; additionally, \(C(s)\) is rational whenever \(s\) is rational.
Substitutability means \(s-C(s)\leq s'-C(s')\) whenever \(0\leq s\leq s'\leq\mu\). A comparison query supplies distinct binary-rational vectors \(x,y\in B(\mu)\) and returns which is preferred; no other preference access is available.
Compute \(C(\mu)\) exactly as a binary-rational vector. Use deterministic algorithms, with no imposed denominator bound on queries or choices; measure oracle calls separately from bit computation, and express bounds in \(m,\tau,L\).

What is the optimal worst-case comparison-query complexity of computing \(C(\mu)\): is it polynomial in \(m,\tau,L\), or necessarily superpolynomial, possibly with no finite uniform bound?

For \(n\) discrete doctors, strict substitutable preferences can require \(\Omega(2^n)\) oracle queries; an additional oracle deciding whether \(C(A)=A\) permits \(O(n^3)\) verification queries and \(O(n^2)\) comparisons. [Source](https://ojs.aaai.org/index.php/AAAI/article/view/10595/10454).
No result settling exactly the fractional comparison-oracle problem stated here was located.

Result

There is no finite uniform comparison-query bound, already for fixed \(m=\tau=1\) and fixed input length \(L\).

More strongly, no deterministic comparison-oracle algorithm can be guaranteed to terminate with the exact answer on every admissible preference order. This holds even for an explicit family of single-peaked preferences with rational peaks.

1. An admissible family with fixed support

Fix one doctor type with mass \(\mu_1=1\). Thus \(B(\mu)=[0,1]\), and the support description and its bit length \(L=L_0\) remain fixed throughout.

For each dyadic rational \(a\in(0,1)\), define preferences by lexicographically comparing the pairs
\(\bigl(-(x-a)^2,-x\bigr)\), with larger pairs preferred.

Equivalently, the hospital prefers the amount closer to \(a\); when two distinct amounts are equally close, it prefers the smaller amount.

This defines a strict total order on all of \([0,1]\): lexicographic order is transitive and total, and distinct amounts have distinct second coordinates.

Claim. For every real supply \(s\in[0,1]\), the unique choice is
\(C_a(s)=\min\{s,a\}\).

Proof. If \(s<a\), then for \(0\leq x<y\leq s\), we have \(a-x>a-y\), so \(y\) has strictly greater first score than \(x\). Hence \(s\) is the unique maximum. If \(s\geq a\), the feasible amount \(a\) has first score zero, whereas every other feasible amount has strictly negative first score. Hence \(a\) is the unique maximum. This also covers \(s=a\). ∎

Consequently, maxima exist for every real supply, and choices are rational whenever supplies are rational.

Substitutability also holds. Indeed, the rejected mass is
\(s-C_a(s)=\max\{s-a,0\}\), which is nondecreasing in \(s\). Thus
\(s-C_a(s)\leq s'-C_a(s')\) whenever \(s\leq s'\).

Every member of this family therefore satisfies every preference promise in the task, and its target answer is \(C_a(1)=a\).

2. What a comparison reveals

Consider any legal query involving distinct amounts \(x,y\). Write
\(\ell=\min\{x,y\}\), \(h=\max\{x,y\}\), and \(q=(\ell+h)/2\).

The difference between their first scores is
\(-( \ell-a)^2+(h-a)^2=(h-\ell)(h+\ell-2a)\).

Since \(h-\ell>0\), the smaller amount has the greater first score exactly when \(a<q\). When \(a=q\), the first scores agree and the prescribed tie-breaking prefers the smaller amount. Therefore,

\(\ell\succ_a h\quad\Longleftrightarrow\quad a\leq q.\)

Thus a comparison distinguishes \(a\leq q\) from \(a>q\). It does not distinguish equality from being slightly below the threshold. This remains true regardless of the denominators or bit lengths of the queried amounts.

3. Finite transcripts cannot certify the answer

Suppose, for contradiction, that a deterministic algorithm terminates and returns the exact choice on every admissible oracle.

Run it on the fixed support above with parameter \(a_0=1/2\). By the assumed guarantee, it terminates after finitely many comparisons, say \(k\), with corresponding thresholds \(q_1,\ldots,q_k\). It must output \(1/2\).

Define
\(\lambda=\max\bigl(\{0\}\cup\{q_i:q_i<a_0,\ 1\leq i\leq k\}\bigr)\).

The set is finite, and every element is strictly below \(a_0\). Hence \(\lambda<a_0\).

Choose an integer \(N\geq2\) such that \(2^{-N}<a_0-\lambda\), and put
\(b=a_0-2^{-N}\). Then \(b\) is dyadic rational and
\(0\leq\lambda<b<a_0<1\).

Every comparison in the recorded execution receives the same answer under parameters \(a_0\) and \(b\):

• If \(q_i<a_0\), then \(q_i\leq\lambda<b<a_0\). Both parameters exceed the threshold, so both oracles prefer the larger queried amount.
• If \(q_i\geq a_0\), then \(b<a_0\leq q_i\). Both parameters are at most the threshold, so both oracles prefer the smaller queried amount.

To account for adaptivity, proceed inductively through the execution. The support inputs are identical. After identical answers to the first \(i-1\) queries, determinism gives the same internal state and the same \(i\)-th query. The preceding calculation gives the same answer to that query. Therefore the complete execution, including termination and output, is identical.

The algorithm consequently outputs \(1/2\) under parameter \(b\). But the correct answer there is \(C_b(1)=b\neq1/2\), a contradiction. ∎

4. Complexity consequence

The obstruction is stronger than an unbounded finite worst-case query requirement: a universally correct deterministic algorithm cannot have a terminating execution even at \(a_0=1/2\) within this family.

Accordingly, no finite function of \(m,\tau,L\) bounds the comparison queries needed for guaranteed exact recovery. Unlimited finite bit computation and arbitrarily long query encodings cannot overcome the indistinguishability proof.

This is a separate obstruction from the finite-domain exponential lower bound in [Deng, Panigrahi, and Waggoner](https://ojs.aaai.org/index.php/AAAI/article/view/10595/10454). Here the support is fixed and contains only one type; the proof verifies attainment, rationality, strictness, and substitutability directly.

⟨structured verdict parsed — rendered above⟩

The argument is correct and fully resolves the requested comparison-oracle problem. It establishes the stronger conclusion that no deterministic algorithm can terminate with the exact answer for every admissible preference order.

• Fixed input and admissible parameters. Setting \(m=\tau=1\) and \(\mu_1=1\) satisfies the support and normalization requirements. The input length \(L\) remains fixed because it measures the support descriptions and masses, not the unknown preference order. Every parameter \(a\) used in the construction is a dyadic rational in \((0,1)\).

• Strict total order. Lexicographic comparison of \(\bigl(-(x-a)^2,-x\bigr)\) is transitive and compares every pair. For distinct \(x,y\), their second coordinates differ, so their score pairs are distinct even when the first coordinates coincide. Thus the construction gives a strict total order on the entire real interval \([0,1]\), as required.

• Existence and formula for choices. For \(s<a\), the first score strictly increases throughout \([0,s]\), making \(s\) the unique maximum. For \(s\geq a\), the feasible point \(a\) uniquely attains first score zero. Consequently,

\[ C_a(s)=\min\{s,a\}. \]
This verifies attainment for every real supply, including \(s=0\), \(s=a\), and \(s=1\). When \(s\) is rational, the displayed minimum is rational because \(a\) is rational.

• Substitutability. The rejected mass is exactly

\[ s-C_a(s)=\max\{s-a,0\}. \]
This function is nondecreasing on \([0,1]\), which is precisely the task’s substitutability condition in one coordinate. No additional preference hypothesis is needed.

• Comparison calculation. The expansion

\[ -(\ell-a)^2+(h-a)^2=(h-\ell)(h+\ell-2a) \]
is correct. Since \(h-\ell>0\), its sign changes at \(q=(\ell+h)/2\). At equality, the second score favors \(\ell\). Therefore,
\[ \ell\succ_a h\quad\Longleftrightarrow\quad a\leq q. \]
The weak inequality is essential and is handled correctly. The argument applies to every permitted query, regardless of encoding length.

• Indistinguishable alternative parameter. A terminating execution at \(a_0=1/2\) contains finitely many comparisons. Every threshold included in the definition of \(\lambda\) is strictly below \(a_0\), including the added value zero, so \(\lambda<a_0\). The chosen \(N\) exists, and

\[ b=a_0-2^{-N} \]
is dyadic with \(0\leq\lambda<b<a_0<1\). For thresholds below \(a_0\), both parameters exceed the threshold; for thresholds at or above \(a_0\), both parameters are at most the threshold. Thus every recorded answer agrees. This also covers an execution with zero comparisons.

• Adaptivity, termination, and contradiction. With identical support inputs and previous oracle answers, determinism forces identical subsequent computation and queries. The induction therefore reproduces the entire terminating execution under \(b\), including the output \(1/2\). That output is wrong because \(C_b(1)=b\). This contradicts the assumed universal guarantee. Arbitrarily large finite query encodings or finite intervening computation do not affect the argument.

No unjustified step, false assertion, missing hypothesis, or missing lemma was found. No repair is needed. The cited discrete result is contextual; the fractional impossibility proof does not depend on it.

For the requested status taxonomy, this is classified as other: it proves an exact-recovery impossibility in the comparison-oracle model, rather than a polynomial algorithm or a hardness result for a specified complexity class.

⟨structured verdict parsed — rendered above⟩