Answer: Yes: mass-weighted CSS always certifies a necessary co-winner when \(\mathrm{MMR}=0\), and otherwise returns a positive-mass type and an incomparable pair. Computing the complete CSS step is in \(\mathrm{P}\), polynomial in \(m,\tau,L\).
Proposition 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateUnless MMR = 0, CSS will always select a voter k and comparison query ai ≻k aj s.t. Inck(ai, aj). If partial vote pk falls into Case 3, this is obvious. In cases 1, 2, we can show that at least one of the designated sets for some voter must be nonempty if MMR > 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(A\), positive rational masses \(\mu_t\) on partial-ranking types \(P_t\), and the assumption that each type shares one hidden complete ranking, can a mass-weighted CSS procedure certify \(\mathrm{MMR}=0\), or, whenever \(\mathrm{MMR}>0\), return a positive-mass type \(t\) and a pair incomparable in \(P_t\) for its next comparison query?
Let \(A\) contain \(m\geq2\) alternatives. A society is given by its support: \(\tau\geq1\) types, each with a strict partial order \(P_t\) and positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. All individuals of type \(t\) share one hidden strict complete ranking extending \(P_t\); different types have no shared-ranking constraint.
Write \(C(P)=\prod_t C(P_t)\) for the compatible complete profiles and \(b(a,v_t)\) for the standard Borda score. Define \(s(a,v)=\sum_t\mu_t b(a,v_t)\), \(\mathrm{PMR}(a,w,P)=\max_{v\in C(P)}[s(w,v)-s(a,v)]\), \(\mathrm{MR}(a,P)=\max_{w\in A}\mathrm{PMR}(a,w,P)\), and \(\mathrm{MMR}(P)=\min_{a\in A}\mathrm{MR}(a,P)\). Score ties count as co-winning.
A query \(x\succ y\) to type \(t\) receives its shared ranking's truthful answer and adds the answered orientation to \(P_t\), taking transitive closure, for the entire mass \(\mu_t\).
The mass-weighted current solution strategy (CSS) first computes \(\mathrm{MMR}\). If it is zero, it returns a minimizing alternative as a necessary co-winner; otherwise it chooses \(a\in\arg\min_z\mathrm{MR}(z,P)\) and \(w\in\arg\max_z\mathrm{PMR}(a,z,P)\).
For each type, write \(x\parallel_t y\) for incomparability and \(U_t=\{u:u\parallel_t a,\ u\parallel_t w\}\). If \(a\parallel_t w\), its only candidate query is \(a\succ w\).
If \(a\succ_t w\), let \(D_t=\{d:a\succ_t d,\ d\parallel_t w\}\) and \(C_t=\{c:c\succ_t w,\ c\parallel_t a\}\). Candidate queries are \(d\succ w\) and \(a\succ c\); if \(C_t\cup D_t=\varnothing\), use the fallback candidates \(u\succ w\) and \(a\succ u\) for \(u\in U_t\).
If \(w\succ_t a\), let \(F_t=\{f:w\succ_t f,\ f\parallel_t a\}\) and \(E_t=\{e:e\succ_t a,\ e\parallel_t w\}\). Candidate queries are \(a\succ f\), \(e\succ w\), \(a\succ u\), and \(u\succ w\), with \(f\in F_t\), \(e\in E_t\), and \(u\in U_t\).
For an ordinary candidate \(q\), its potential is \(\mu_t[g_t(P_t)-g_t(P_t^q)]\), where \(g_t(Q)=\max_{v_t\in C(Q)}[b(w,v_t)-b(a,v_t)]\) and \(P_t^q\) is the closure after an affirmative answer. For a fallback candidate its potential is \(\mu_t\) times the number of elements leaving \(U_t\) after that answer, including the queried element. CSS selects a candidate of greatest potential across all types; every tie uses a fixed lexicographic order.
Does mass-weighted CSS always certify \(\mathrm{MMR}=0\) or, whenever \(\mathrm{MMR}>0\), return a positive-mass type and an incomparable pair? Is computing this CSS step in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite unweighted electorates, CSS always selects an incomparable pair when minimax regret is positive, and Borda minimax regret is computable in \(O(nm^3)\) arithmetic operations ([Lu–Boutilier, 2011](https://www.cs.toronto.edu/~cebly/Papers/LuBoutilier_Elicitation_ijcai11.pdf)). The later journal treatment confirms the discrete progress guarantee ([Lu–Boutilier, 2020](https://www.cs.toronto.edu/~tl/papers/vote_elicitation_aij2019.pdf)); no result for exactly the rational-mass, type-shared-ranking CSS model was located.
Both guarantees hold. Mass-weighted CSS always either certifies a necessary co-winner or returns a positive-mass type and an incomparable pair. Its entire step is computable in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
We prove this directly for the specified model. The corresponding unweighted arguments appear in [Lu–Boutilier (2011), Section 4](https://www.cs.toronto.edu/~cebly/Papers/LuBoutilier_Elicitation_ijcai11.pdf) and [Lu–Boutilier (2020), Proposition 7](https://www.cs.toronto.edu/~tl/papers/vote_elicitation_aij2019.pdf).
For a strict partial order \(Q\), define
\(\operatorname{Anc}_Q(x)=\{z:z\succ_Q x\}\) and
\(\operatorname{Desc}_Q(x)=\{z:x\succ_Q z\}\).
Let \(r_v(x)\) denote the position of \(x\) in a linear extension \(v\), with the best position numbered \(1\). Standard Borda satisfies
\(b(x,v)=m-r_v(x)\), so
\(b(w,v)-b(a,v)=r_v(a)-r_v(w)\).
Write
\(g_Q(a,w)=\max_{v\in C(Q)}[b(w,v)-b(a,v)]\).
For \(a=w\), this is zero. For distinct \(a,w\), the following formulas hold:
\(g_Q(a,w)=-1-|\{z:a\succ_Q z\succ_Q w\}|\).
\(g_Q(a,w)=m-1-|\operatorname{Anc}_Q(w)|-|\operatorname{Desc}_Q(a)|\).
Each formula is computable by scanning the alternatives once, given a transitive-closure matrix.
Put \(B=\{z:a\succ_Q z\succ_Q w\}\). Every linear extension places all of \(B\) between \(a\) and \(w\). Consequently,
\(r_v(w)-r_v(a)\geq |B|+1\), which gives the claimed upper bound on \(g_Q(a,w)\).
To attain it, put
\(I=\{a,w\}\cup B\),
\(H=\operatorname{Anc}_Q(w)\setminus I\), and
\(R=A\setminus(H\cup I)\).
The set \(H\) is closed under predecessors. Indeed, if \(x\in H\) and \(y\succ_Q x\), then \(y\succ_Q w\). If \(y\in I\), then either \(y=w\), contradicting acyclicity, or \(a\succ_Q x\succ_Q w\), contradicting \(x\notin I\). Thus \(y\in H\).
Also,
\(H\cup I=\operatorname{Anc}_Q(w)\cup\{w\}\)
is closed under predecessors. Therefore, concatenating linear extensions of \(H,I,R\), in that order, extends \(Q\): neither boundary admits a comparison directed from a later block to an earlier block.
Within \(I\), every extension has \(a\) first and \(w\) last. Thus precisely the elements of \(B\) occur between them, attaining the bound.
Put \(H=\operatorname{Anc}_Q(w)\) and \(T=\operatorname{Desc}_Q(a)\). These sets are disjoint: membership of an element in both would imply \(a\succ_Q w\). Neither set contains either endpoint.
For every extension,
\(r_v(w)\geq |H|+1\) and
\(r_v(a)\leq m-|T|\).
Hence
\(r_v(a)-r_v(w)\leq m-1-|H|-|T|\).
Let \(M=A\setminus(H\cup T\cup\{a,w\})\). Concatenate linear extensions of the blocks
\(H,\{w\},M,\{a\},T\).
This extends \(Q\). Specifically, \(H\) is closed under predecessors, \(T\) is closed under successors, every predecessor of \(w\) lies in \(H\), and every successor of \(a\) lies in \(T\). These facts exclude every backward comparison between blocks, except potentially \(a\succ_Q w\), which the hypothesis excludes.
The resulting positional gap is \(|M|+1=m-1-|H|-|T|\), attaining the bound. This also handles \(a\parallel_Q w\).
For every pair \(a,w\),
\(\mathrm{PMR}(a,w,P)=\sum_{t=1}^{\tau}\mu_t g_{P_t}(a,w)\).
To justify the equality, each compatible profile has its type contribution bounded above by the corresponding local maximum. Conversely, each finite set \(C(P_t)\) contains a maximizing extension. Choosing one independently for each type produces a profile in \(\prod_t C(P_t)\) attaining the sum. Positivity of the masses ensures that maximizing each unweighted contribution also maximizes its weighted contribution.
This uses exactly one ranking per type, as required.
Because \(\mathrm{PMR}(a,a,P)=0\), every \(\mathrm{MR}(a,P)\) is nonnegative. Therefore,
\(\mathrm{MMR}(P)=0\)
if and only if there is an alternative \(a\) such that
\(s(a,v)\geq s(z,v)\)
for every \(z\in A\) and every \(v\in C(P)\).
Indeed, \(\mathrm{MR}(a,P)=0\) means that every pairwise maximum is at most zero, which is precisely this collection of inequalities. Thus any minimizing alternative returned at zero is a necessary co-winner.
Suppose
\(R=\mathrm{MMR}(P)>0\),
and let CSS choose \(a,w\). Then
\(\mathrm{MR}(a,P)=\mathrm{PMR}(a,w,P)=R\).
In particular, \(a\neq w\).
Every listed candidate is an incomparable pair, directly by the definitions of \(C_t,D_t,E_t,F_t,U_t\). Adding either orientation to an incomparable pair preserves acyclicity: a cycle using the new edge would require the reverse comparison already to hold. Hence both answers admit linear extensions.
It remains to prove that the candidate collection is nonempty.
Assume, for contradiction, that every type has no candidates. No type can have \(a\parallel_t w\), since that case supplies a candidate immediately.
If \(a\succ_t w\), absence of ordinary and fallback candidates implies
\(C_t=D_t=U_t=\varnothing\).
Transitivity shows that every other alternative is either above both endpoints, below both, strictly between them, or in one of those three sets. Thus both \(a\) and \(w\) are comparable with every other alternative.
Likewise, if \(w\succ_t a\), absence of candidates implies
\(E_t=F_t=U_t=\varnothing\).
The analogous classification again shows that both endpoints are comparable with every other alternative.
Consequently, in every type, the positions and Borda scores of both \(a\) and \(w\) are fixed across all extensions. Their society-wide scores are therefore constants; write them as \(\alpha\) and \(\beta\). The witness identity gives
\(\beta-\alpha=R\).
For every alternative \(z\) and every compatible profile,
\(s(z,v)-s(w,v)=s(z,v)-s(a,v)-R\).
Taking maxima over profiles and then alternatives yields
\(\mathrm{MR}(w,P)=\mathrm{MR}(a,P)-R=0\).
This contradicts \(\mathrm{MMR}(P)=R>0\). Hence candidates exist. All types have positive mass, so the candidate selected by maximum potential and lexicographic tie-breaking has both required properties.
In fact, every generated candidate has positive potential:
Each change is multiplied by a positive mass. This assertion concerns the defined potential; it does not assert that every truthful answer strictly decreases minimax regret.
First compute each order’s transitive-closure matrix. This requires \(O(\tau m^3)\) Boolean operations.
The local formulas take \(O(m)\) time per ordered pair and type. Thus all pairwise regrets, all maximum regrets, minimax regret, and the lexicographically selected \(a,w\) require \(O(\tau m^3)\) relation and arithmetic operations.
Each type contributes \(O(m)\) candidate queries. Their potentials can also be evaluated within this bound.
For an incomparable query \(x\succ y\), define
\(H_x=\operatorname{Anc}_Q(x)\cup\{x\}\) and
\(T_y=\operatorname{Desc}_Q(y)\cup\{y\}\).
The affirmative closure is exactly
\(Q^{x\succ y}=Q\cup(H_x\times T_y)\).
To verify this identity, every new directed path must use the added edge. It uses that edge only once, since two uses would require an existing path from \(y\) to \(x\), contradicting incomparability. Its endpoints therefore belong to \(H_x\) and \(T_y\). Conversely, every pair in their Cartesian product is implied by the new edge.
A temporary closure matrix consequently takes \(O(m^2)\) operations. Computing its local regret or counting the elements leaving \(U_t\) then takes \(O(m)\). Across all \(O(\tau m)\) candidates, this costs \(O(\tau m^3)\) operations.
For exact arithmetic, write each explicitly binary-encoded rational mass as
\(\mu_t=p_t/q_t\), and put
\(D=\prod_t q_t\) and
\(h_t=p_t(D/q_t)\).
Then \(h_t\) is a positive integer,
\(\sum_t h_t=D\), and
\(\mu_t=h_t/D\).
All pairwise regrets can be compared through their integer numerators:
\(D\,\mathrm{PMR}(a,w,P)=\sum_t h_t g_{P_t}(a,w)\).
Ordinary and fallback potentials likewise have numerators
\(h_t[g_{P_t}(a,w)-g_{P_t^q}(a,w)]\)
and
\(h_t|U_t\setminus U_t^q|\), respectively. Thus zero detection, maximum-potential selection, and all ties are exact.
The bit length of \(D\) is bounded by the sum of the denominator bit lengths, hence by \(O(L)\). Since
\(|g_Q(a,w)|\leq m-1\)
and \(\sum_t h_t=D\), all these numerators have \(O(L+\log m)\) bits. Forming the scaled masses and performing the integer operations therefore requires polynomial bit time.
This establishes the claimed membership in \(\mathrm{P}\), without expanding rational masses into an electorate.
As a consequence, repeated truthful CSS queries terminate after at most
\(\tau\binom{m}{2}\)
queries: each answer resolves a previously incomparable unordered pair in its queried type. If all types become complete, the unique compatible profile has a necessary co-winner, so minimax regret is zero.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves both questions for the specified rational-mass, type-shared-ranking model. The argument is correct and rigorous; no major or minor mathematical issues were found.
The identity \(b(w,v)-b(a,v)=r_v(a)-r_v(w)\) has the correct sign.
Case \(a\succ_Q w\). Every element of \(B=\{z:a\succ_Q z\succ_Q w\}\) must occur between the endpoints, so the stated upper bound \(g_Q(a,w)\leq-1-|B|\) is correct.
The attainment argument also checks out:
Thus the first formula is exact, including when \(B\) is empty.
Case \(a\not\succ_Q w\). The sets \(H=\operatorname{Anc}_Q(w)\) and \(T=\operatorname{Desc}_Q(a)\) are disjoint and exclude both endpoints, as claimed. The two positional bounds imply the stated upper bound with the correct constant \(m-1\).
The proposed block concatenation respects all comparisons. The closure properties of \(H,T\), together with the descriptions of the predecessors of \(w\) and successors of \(a\), exclude backward comparisons. The remaining endpoint comparison is excluded by the hypothesis. The positional gap in this extension attains the bound.
This case correctly covers both \(w\succ_Q a\) and incomparability. The separate treatment of \(a=w\) avoids applying either distinct-endpoint formula incorrectly.
The equality
\(\mathrm{PMR}(a,w,P)=\sum_t\mu_t g_{P_t}(a,w)\)
is justified in both directions.
Each local extension set is finite and nonempty because its order is a finite strict partial order. Positive masses preserve local maximizers, and the product definition of compatible profiles permits choosing a maximizing extension independently for each type.
This reasoning respects the shared-ranking constraint: it chooses one extension per type. It introduces no independent choices within a type.
The argument correctly uses \(\mathrm{PMR}(a,a,P)=0\) to establish nonnegativity of every maximum regret.
The equivalence between \(\mathrm{MR}(a,P)=0\) and
\(s(a,v)\geq s(z,v)\) for every alternative \(z\) and every compatible profile \(v\) is exact. Therefore, every minimizing alternative at zero minimax regret is a necessary co-winner. The handling of score ties agrees with the task.
For positive minimax regret, the selected witness satisfies
\(\mathrm{PMR}(a,w,P)=\mathrm{MR}(a,P)=R>0\), so \(a\neq w\).
Every generated query compares an incomparable pair by its defining membership conditions. The acyclicity argument for adding either orientation is valid: a cycle would require a pre-existing path in the reverse direction.
The candidate-existence contradiction is sound:
The subsequent use of constants \(\alpha,\beta\) is legitimate. Since \(\beta-\alpha=R\), subtracting the constant \(R\) commutes with both maxima, yielding
\(\mathrm{MR}(w,P)=\mathrm{MR}(a,P)-R=0\).
This contradicts positive minimax regret.
Therefore the candidate collection is nonempty. Positive mass and incomparability hold for every candidate, so maximum-potential selection and lexicographic tie-breaking preserve both properties.
The additional assertion about positive potential is also correct:
Multiplication by a positive mass preserves positivity. The output correctly distinguishes this potential assertion from a guarantee that every truthful answer strictly decreases minimax regret.
The operation counts are consistent:
The closure identity
\(Q^{x\succ y}=Q\cup(H_x\times T_y)\)
is valid under the stated incomparability assumption. Its path argument establishes both inclusions.
The exact-arithmetic analysis also holds. The common denominator \(D\) has \(O(L)\) bits, and the scaled masses satisfy \(h_t>0\) and \(\sum_t h_t=D\). Pairwise-regret numerators have magnitude at most \(D(m-1)\); ordinary-potential numerators have magnitude at most \(2D(m-1)\), which gives the same asserted asymptotic bit bound. Fallback numerators also satisfy that bound.
Thus arithmetic, comparisons, zero detection, and ties can all be handled exactly in polynomial bit time. No expansion into an electorate is required.
The additional termination bound is correct: each query resolves a previously incomparable unordered pair in its type. Transitive closure preserves earlier resolutions, so at most \(\tau\binom{m}{2}\) queries occur.
The historical references are consistent with the stated discrete results: the regret computation appears in [Lu–Boutilier (2011), Section 4](https://www.cs.toronto.edu/~cebly/Papers/LuBoutilier_Elicitation_ijcai11.pdf), and the CSS progress guarantee appears in [Lu–Boutilier (2020), Proposition 7](https://www.cs.toronto.edu/~tl/papers/vote_elicitation_aij2019.pdf). The rational-mass conclusion is established directly by the submitted argument.
Required clarification or repair: none.
⟨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.