Answer: Polynomial-time solvable: at most \(m(m-1)/2\) candidate comparisons suffice to return a committee \(B\) with \(R(B,\mathcal Q)=0\le\delta\), using computation polynomial in \(m,\tau,k,L\).
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 returns a base B ∈B such that MR(B, B, W) ≤δ holds at the end of the execution.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of ranking types, a rational polytope \(\mathcal P\subseteq\Delta(T)\) containing an unknown society \(\mu^\star\), type-specific Borda scores \(a_t(e)\), and a uniform matroid of rank \(k\), can an adaptive algorithm query whether \(\sum_{t\in T}\mu^\star_t a_t(e)\ge\sum_{t\in T}\mu^\star_t a_t(f)\) and return a committee \(B\) with worst-case per-capita regret at most \(\delta\) over the distributions in \(\mathcal P\) consistent with the answers, using polynomially many queries and polynomial-time computation?
Let \(C\) contain \(m\ge1\) candidates, and let \(T\) list \(\tau\ge1\) distinct strict ranking types. A society is given by its support: the types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible rankings. Here the support is known, but its masses are hidden.
The input includes a nonempty rational polytope \(\mathcal P\subseteq\Delta(T)\), given by explicit rational linear inequalities, whose points have positive coordinates; an unknown rational society \(\mu^\star\in\mathcal P\); a uniform matroid of rank \(1\le k\le m\); and a binary rational tolerance \(\delta\ge0\). Let \(L\) be the total bit length of the supplied input, excluding the hidden masses.
Let \(a_t(e)\) be the Borda score of candidate \(e\) in ranking \(t\), shifted upward by one to ensure positive weights. Define additive per-capita committee utility by \(u_\mu(B)=\sum_{e\in B}\sum_{t\in T}\mu_t a_t(e)\), with feasible committees satisfying \(|B|=k\).
An adaptive algorithm may query distinct candidates \(e,f\); the oracle answers yes exactly when \(u_{\mu^\star}(\{e\})\ge u_{\mu^\star}(\{f\})\), including equality. Let \(\mathcal Q\) contain the rational societies in \(\mathcal P\) consistent with every answer. Define \(R(B,\mathcal Q)=\sup_{\mu\in\mathcal Q}\max_{B'\subseteq C,\,|B'|=k}\bigl(u_\mu(B')-u_\mu(B)\bigr)\).
Does this elicitation problem admit an algorithm that, for every hidden society, returns a committee \(B\) with \(R(B,\mathcal Q)\le\delta\), using polynomially many queries and polynomial computation time in \(m,\tau,k,L\), or is it NP-hard?
For finite matroid ground sets, interactive greedy elicitation guarantees final additive regret at most \(\delta\) with polynomially many element comparisons; polynomial computation is stated when independence and the requisite regret computations are polynomial. The same work also treats continuous linear utility parameters, but no separate theorem for this support-encoded Borda formulation was verified. [Benabbou et al. (2021)](https://ojs.aaai.org/index.php/AAAI/article/download/17452/17259)
The elicitation problem is polynomial-time solvable. At most \(m(m-1)/2\) comparisons suffice to return a committee with regret exactly \(0\), for every hidden society and every tolerance \(\delta\ge 0\).
1. Common ordering of candidate utilities
Write \(w_\mu(e)=\sum_{t\in T}\mu_t a_t(e)\), so that \(u_\mu(B)=\sum_{e\in B}w_\mu(e)\).
A yes answer to the query \((e,f)\) imposes \(w_\mu(e)\ge w_\mu(f)\) on every consistent society. A no answer imposes \(w_\mu(e)<w_\mu(f)\).
We construct an ordering \(c_1,\ldots,c_m\) such that every society consistent with the final transcript satisfies
\(w_\mu(c_1)\ge\cdots\ge w_\mu(c_m)\).
This common ordering will certify an optimal committee throughout the final uncertainty set.
The additive utility and uniform-matroid setting also appear in [Benabbou et al. (2021)](https://ojs.aaai.org/index.php/AAAI/article/download/17452/17259). The argument below is self-contained and requires no regret computations.
2. Algorithm and ordering invariant
Process the candidates in any fixed order. Maintain a list of the candidates already processed.
To insert a new candidate \(x\) into the current list \(c_1,\ldots,c_r\), query \((x,c_i)\) successively for \(i=1,\ldots,r\). At the first yes answer, insert \(x\) immediately before \(c_i\) and stop scanning. If every answer is no, append \(x\).
After processing all candidates, return \(B=\{c_1,\ldots,c_k\}\).
We prove the invariant that the current list is weakly decreasing in utility for every rational society consistent with the current transcript.
The invariant holds for lists of size zero or one. Suppose it holds before inserting \(x\). New answers restrict the uncertainty set, so all previously established inequalities remain valid.
If the first yes occurs at position \(i\), then every currently consistent society satisfies:
Transitivity therefore gives the required weak ordering after insertion. If every answer is no, then \(w_\mu(c_j)>w_\mu(x)\) for all existing candidates, so appending \(x\) also preserves the invariant.
Thus the final ordering holds simultaneously for every \(\mu\in\mathcal Q\). Equality causes no difficulty: a yes answer supplies exactly the weak inequality needed.
3. Exact regret certificate
The actual rational society \(\mu^\star\) satisfies every answer it supplies and belongs to \(\mathcal P\). Hence \(\mu^\star\in\mathcal Q\), so \(\mathcal Q\) is nonempty.
Fix any \(\mu\in\mathcal Q\) and any competing committee \(B'\) of size \(k\). Set \(A=B\setminus B'\) and \(D=B'\setminus B\). Since \(|B|=|B'|\), we have \(|A|=|D|\).
Every candidate in \(A\) appears among the first \(k\) positions, while every candidate in \(D\) appears after them. The ordering invariant gives \(w_\mu(a)\ge w_\mu(d)\) for every \(a\in A\) and \(d\in D\).
Choose any bijection \(\phi:D\to A\). Cancellation of the candidates common to both committees yields
\(u_\mu(B')-u_\mu(B)=\sum_{d\in D}\bigl(w_\mu(d)-w_\mu(\phi(d))\bigr)\le 0\).
If \(D\) is empty, the same conclusion follows from the empty sum.
Taking \(B'=B\) gives difference zero. Consequently,
\(\max_{B'\subseteq C,\ |B'|=k}\bigl(u_\mu(B')-u_\mu(B)\bigr)=0\)
for every \(\mu\in\mathcal Q\). Taking the supremum over this nonempty set proves
\(R(B,\mathcal Q)=0\le\delta\).
This establishes robust optimality throughout the final uncertainty set, not merely optimality at the actual hidden society.
4. Complexity and conclusion
Inserting the \((r+1)\)-st candidate uses at most \(r\) queries. The total is therefore at most
\(\sum_{r=0}^{m-1}r=m(m-1)/2\).
Every query involves distinct candidates, and no unordered candidate pair is queried more than once.
List scanning and insertion take \(O(m^2)\) elementary operations. Candidate identifiers have \(O(\log(m+1))\) bits, so the ordinary computation, including input reading, is polynomial in \(m,\tau,k,L\). The algorithm does not evaluate hidden rational utilities, optimize over \(\mathcal P\), or compute regret numerically; the ordering invariant certifies zero regret directly.
Thus the stated interactive problem admits the requested polynomial-time, polynomial-query algorithm.
⟨structured verdict parsed — rendered above⟩
The prover’s output fully resolves the task. The insertion procedure establishes a common ordering for every society consistent with the transcript, and the first \(k\) candidates are optimal throughout that uncertainty set. No correctness or rigor issues were found.
The definition \(w_\mu(e)=\sum_{t\in T}\mu_t a_t(e)\) correctly gives \(u_\mu(B)=\sum_{e\in B}w_\mu(e)\).
The interpretation of both oracle answers is exact:
Additional answers only restrict the consistent societies, so inequalities established earlier remain valid. The proof correctly quantifies over rational societies, as required by the task. It never requires the uncertainty set to be closed or to admit an attained supremum.
The invariant is correctly stated: the current list is weakly decreasing for every rational society consistent with the current transcript.
The base cases of zero and one processed candidate are valid.
Suppose the invariant holds before inserting \(x\). If the first yes answer occurs at position \(i\), the preceding no answers establish \(w_\mu(c_j)>w_\mu(x)\) for every \(j<i\). The yes answer establishes \(w_\mu(x)\ge w_\mu(c_i)\). The previous ordering remains valid after restricting the uncertainty set.
Together, these inequalities establish the entire new ordering: candidates preceding \(x\) remain above it, and \(x\) is at least as good as \(c_i\) and every subsequent candidate. This reasoning holds simultaneously for every currently consistent society.
If all answers are no, every existing candidate has strictly greater utility than \(x\), so appending \(x\) preserves the invariant.
Equality is handled correctly by insertion at the first yes answer. There is no unstated requirement to distinguish equality from strict preference.
The hidden rational society \(\mu^\star\) belongs to \(\mathcal P\) and satisfies every answer it supplies. Therefore \(\mu^\star\in\mathcal Q\), establishing nonemptiness.
For any fixed \(\mu\in\mathcal Q\) and size-\(k\) competitor \(B'\), the sets \(A=B\setminus B'\) and \(D=B'\setminus B\) have equal cardinality. Every member of \(A\) lies in the first \(k\) positions, while every member of \(D\) lies after position \(k\). Consequently, the common ordering gives \(w_\mu(a)\ge w_\mu(d)\) for every such pair.
The bijection and cancellation calculation are valid:
\[
u_\mu(B')-u_\mu(B)
=\sum_{d\in D}\bigl(w_\mu(d)-w_\mu(\phi(d))\bigr)
\le 0.
\]
The empty-set case is explicitly covered.
Since \(B'=B\) is a feasible competitor, the maximum difference is exactly zero for each \(\mu\in\mathcal Q\). Its supremum over the nonempty set \(\mathcal Q\) is therefore exactly zero. No missing optimization or attainment argument is needed.
At insertion into a list of length \(r\), at most \(r\) comparisons occur. Thus the stated bound
\[
\sum_{r=0}^{m-1}r=\frac{m(m-1)}2
\]
is correct.
Each query compares the new candidate with an already processed candidate, so its two candidates are distinct. Each unordered pair can occur only when its later-processed member is inserted, and is queried at most once.
Scanning and inserting into lists requires at most \(O(m^2)\) elementary operations. Accounting for candidate identifiers and input reading preserves polynomial bit complexity in \(m,\tau,k,L\). Hidden rational masses need not be read or manipulated. Oracle calls are counted separately, consistently with the task’s model.
For \(m=1\), the algorithm makes no queries and returns the only feasible committee. For \(k=m\), it returns all candidates, and the regret argument remains valid. For \(\delta=0\), the exact zero-regret guarantee suffices.
The argument does not depend on any theorem from the cited paper. Its mention is contextual, so no unverified theorem application enters the proof.
No additional clarification or repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.