Answer: —
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf the satisfaction function used by R is polynomially bounded, then the clustering procedure runs in polynomial time. Naturally, the clustering heuristic never outputs a solu- tion that is worse than the initial assignment. Also, as we will also see in the experimental evaluation of our heuristics, the choice of the initial committee W1 is very important and needs to balance two factors. On the one hand, the commit- tee W1 should be of a relatively high quality, so that the algorithm starts near a very good solution.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), complete ranking types \(T\), rational masses \(\mu\), satisfaction function \(\gamma\), an initial committee \(W_1\), and canonical deterministic tie-breaking, repeatedly compute a maximum-satisfaction assignment \(x_{t,c}\), replace each representative by a candidate maximizing satisfaction over its assigned mass, and recompute the assignment; determine the first terminal pair \((W,x)\) and the complexity of doing so in the mass bit model.
Let \(C=\{c_1,\ldots,c_m\}\), \(1\le k\le m\), and let \(W_1\subseteq C\) have size \(k\). Use the Chamberlin–Courant assignment rule.
A society is given by its support: the list of the \(\tau\) strict complete ranking types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
The input satisfaction table \(\gamma:\{1,\ldots,m\}\to\mathbb Z_{\ge0}\) is nonincreasing and satisfies \(\gamma(1)\le p(m)\), for a fixed polynomial \(p\). Put \(s_{t,c}=\gamma(\operatorname{rank}_t(c))\).
For a committee \(W\), an assignment consists of divisible masses \(x_{t,c}\ge0\), with \(\sum_c x_{t,c}=\mu_t\) and \(x_{t,c}=0\) outside \(W\); there are no representative capacity constraints. Choose the lexicographically least assignment maximizing \(\sum_{t,c}x_{t,c}s_{t,c}\), ordering coordinates by the listed types and candidate indices.
Compute \(x_1\) for \(W_1\). At iteration \(i\ge2\), each \(c\in W_{i-1}\) chooses a candidate \(d\in C\) maximizing \(\sum_t x_{i-1,t,c}s_{t,d}\); retain \(c\) if it is a maximizer, and otherwise choose the smallest-index maximizer. Form \(W_i\) from the distinct choices, fill any vacant places with the smallest-index candidates outside that set, and compute \(x_i\) canonically as above.
Stop at the first \(i\ge2\) with \(x_i=x_{i-1}\), comparing matrices on all of \(T\times C\), and output \((W_i,x_i)\).
Is computing this first terminal pair polynomial-time solvable in \(m,\tau,k,L\), or is it NP-hard?
For explicit finite electorates, the corresponding clustering procedure has a polynomial-time bound when integer satisfaction scores are polynomially bounded and representative ties favor incumbents ([source](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p296.pdf)). No result settling the specified rational-mass iteration was located.
I do not resolve the general polynomial-time-versus-hardness question.
I prove two additional results:
The second result supplies a concrete restricted process whose endpoint hardness would establish hardness for the original task. I do not prove that remaining hardness claim.
Identify candidates with their indices. For a committee $W$, define
$$
h_t(W)=\max_{c\in W}s_{t,c},
\qquad
a_W(t)=\max\{c\in W:s_{t,c}=h_t(W)\}.
$$
The prescribed canonical assignment is
$$
x_{W,t,c}=
\begin{cases}
\mu_t,&c=a_W(t),\\
0,&c\ne a_W(t).
\end{cases}
$$
Proof. For each type $t$, every feasible assignment satisfies
$$
\sum_{c\in W}x_{t,c}s_{t,c}\le \mu_t h_t(W).
$$
There are no capacity constraints, so these bounds can be attained simultaneously.
A maximizing assignment can place positive mass only on satisfaction-maximizing candidates: any positive allocation below $h_t(W)$ produces a strictly positive loss that another type cannot compensate for.
Within the maximizing candidates of a row, lexicographic minimization sets all coordinates before the largest-index maximizing candidate to zero. This is feasible, and the row-sum constraint then places the entire mass on that last candidate. Different rows have independent constraints, proving the formula. $\square$
Thus define the committee score by
$$
F(W)=\sum_{t=1}^{\tau}\mu_t h_t(W).
$$
Let $\phi(c)$ be the choice made by incumbent $c\in W$. If $\phi(c)\ne c$, then
$$
\sum_t x_{W,t,c}s_{t,\phi(c)}
>
\sum_t x_{W,t,c}s_{t,c},
$$
and $\phi(c)\notin W$.
Moreover, if $W'$ is the completed next committee, any representative change implies
$$
F(W')>F(W).
$$
Proof. Incumbent-favoring ties give the first strict inequality.
If type $t$ is assigned to $c$, then $s_{t,c}\ge s_{t,d}$ for every $d\in W$. Consequently,
$$
\sum_t x_{W,t,c}s_{t,c}
\ge
\sum_t x_{W,t,c}s_{t,d}
\qquad(d\in W).
$$
A strictly improving replacement therefore lies outside $W$.
To handle simultaneous changes and collisions, define
$$
y_{t,d}=\sum_{\{c\in W:\phi(c)=d\}}x_{W,t,c}.
$$
This assignment has row sums $\mu_t$, and every candidate receiving positive mass belongs to $W'$. It is therefore feasible for $W'$. Its score is
$$
\sum_{c\in W}\sum_t x_{W,t,c}s_{t,\phi(c)}.
$$
Each incumbent weakly improves its cluster score, and every changed incumbent strictly improves it. Hence, if any incumbent changes,
$$
F(W')
\ge
\sum_{c\in W}\sum_t x_{W,t,c}s_{t,\phi(c)}
>
F(W).
$$
$\square$
If no incumbent changes, the committee and its canonical assignment remain unchanged. Conversely, equal consecutive assignment matrices have equal scores, so Lemma 2 excludes a representative change. Therefore the specified stopping condition is equivalent to having no representative changes.
Let $I$ be the first terminal iteration index. Since every nonterminal transition strictly increases $F$, no committee repeats before the terminal comparison. There are only $\binom{m}{k}$ committees, giving
$$
I\le \binom{m}{k}+1.
$$
In particular, termination always occurs.
Each iteration is computable exactly in polynomial time. To see the bit-complexity bound, write each mass as a binary-encoded fraction and let $Q$ be the product of its denominators. The bit length of $Q$ is at most the sum of their bit lengths. With $w_t=Q\mu_t$, representative comparisons use the integers
$$
\sum_{\{t:a_W(t)=c\}}w_t s_{t,d}.
$$
These are bounded by $Q\gamma(1)$ and have polynomial bit length. Canonical ownership, representative selection, filling, and assignment comparison all require polynomially many arithmetic operations.
Keeping only the current committee, owners, and arithmetic data uses polynomial space. Thus the endpoint is computable in polynomial space and in time
$$
2^{O(m)}\operatorname{poly}(m,\tau,k,L).
$$
The elementary boundary cases are also settled: $k=m$ gives $I=2$, and $k=1$ gives $I\le3$, because the first representative update chooses a population-wide satisfaction maximizer.
Let $\alpha_1,\ldots,\alpha_d$ be the distinct values among the positive masses. Define
$$
T_j=\{t:\mu_t=\alpha_j\},
\qquad
n_j=|T_j|,
\qquad
\Delta=\gamma(1)-\gamma(m).
$$
For every instance,
$$
I\le 1+\prod_{j=1}^{d}(n_j\Delta+1).
$$
Consequently, for each fixed $d$, the first terminal pair is computable in polynomial time in $m,\tau,k,L$.
Proof. For every committee $W$, define the integer
$$
Z_j(W)=\sum_{t\in T_j}\bigl(h_t(W)-\gamma(m)\bigr).
$$
Since satisfaction values are integers,
$$
Z_j(W)\in\{0,1,\ldots,n_j\Delta\}.
$$
Also, using $\sum_t\mu_t=1$,
$$
F(W)
=
\gamma(m)+\sum_{j=1}^{d}\alpha_j Z_j(W).
$$
If two visited committees have the same vector
$$
\bigl(Z_1(W),\ldots,Z_d(W)\bigr),
$$
they have the same score. Lemma 2 therefore prevents repetition of such a vector across strict transitions.
There are at most
$$
\prod_{j=1}^{d}(n_j\Delta+1)
$$
possible vectors. If there are $s$ strict transitions, the initial committee and the committees reached through those transitions give $s+1$ distinct vectors. The terminal comparison occurs at index $s+2$, proving the bound.
Finally,
$$
\prod_{j=1}^{d}(n_j\Delta+1)
\le
(\tau\Delta+1)^d.
$$
For fixed $d$, this is polynomial because $\Delta\le p(m)$. Combining it with polynomial time per iteration completes the proof. $\square$
This argument does not require the distinct masses to be separated numerically, or their denominators to be small. For example, it applies to instances with arbitrarily large binary denominators but only two distinct mass values.
Define the following auxiliary process.
There are $q\ge2$ disjoint candidate pairs
$$
P_g=\{2g-1,2g\},
\qquad
g=1,\ldots,q.
$$
A state $W$ contains exactly one candidate from each pair.
There are types with positive rational weights $w_t$ summing to one and arbitrary utilities
$$
u_{t,c}\in\{0,1,2\}
\qquad(c\in\{1,\ldots,2q\}).
$$
At each state:
This auxiliary definition does not assume that utility rows arise from rankings or share a common multiset of utilities.
Every instance of this paired process can be transformed in polynomial time into an instance of the original procedure with
$$
m=8q,
\qquad
k=q,
$$
and satisfaction table
$$
\gamma(r)=
\begin{cases}
2,&1\le r\le 2q,\\
1,&2q<r\le 4q,\\
0,&4q<r\le 8q.
\end{cases}
$$
Starting from the corresponding committee, the original procedure produces exactly the paired process’s committees at every iteration. No added candidate enters a committee, no collision occurs, and no filling is required. The first terminal iteration agrees in both processes.
This construction belongs to the task’s allowed input family whenever $p(8q)\ge2$.
Put $n=2q$. Retain the $n$ original candidates, with their original indices. Add two sets of candidates, indexed after them:
The total number is
$$
n+(n-2)+(2n+2)=4n=8q.
$$
We construct each satisfaction row to have exactly $n$ entries equal to $2$, exactly $n$ equal to $1$, and exactly $2n$ equal to $0$. Such a row is realizable by a strict complete ranking under the displayed common table: rank all score-$2$ candidates first, then all score-$1$ candidates, then all score-$0$ candidates, ordering candidates strictly within each block.
Original types. For type $t$, preserve its utilities on the original candidates:
$$
s_{t,c}=u_{t,c}.
$$
Give it score $0$ on every member of $D_0$.
Let
$$
a_{t,j}=|\{c\in\{1,\ldots,n\}:u_{t,c}=j\}|
\qquad(j=0,1,2).
$$
Then $a_{t,0}+a_{t,1}+a_{t,2}=n$. Assign scores on $D_1$ with the following multiplicities:
$$
\begin{array}{c|c}
\text{Score}&\text{Multiplicity}\\ \hline
2&n-a_{t,2}\\
1&n-a_{t,1}\\
0&n+2-a_{t,0}
\end{array}
$$
These multiplicities are nonnegative and sum to $2n+2$. The complete row consequently has the required counts $n,n,2n$.
Guard types. For each pair $P_g$, add a type $b_g$ with:
Its score counts are again exactly $n,n,2n$.
Assign masses
$$
\mu_t=\frac{w_t}{3q+1},
\qquad
\mu_{b_g}=\frac{3}{3q+1}.
$$
They are positive and satisfy
$$
\sum_t\mu_t+\sum_{g=1}^{q}\mu_{b_g}
=
\frac{1+3q}{3q+1}
=
1.
$$
Their binary encoding lengths are polynomially bounded by the auxiliary input length.
If constructed rankings coincide, combine their masses. This preserves every representative score and committee update because coincident rankings have identical satisfaction rows and canonical owners. Guard rankings are distinct from one another, and from original-type rankings: on the nonempty set $D_0$, guards have score $2$ whereas original types have score $0$. Original-type assignments can be reconstructed from their original rows after computing the terminal committee.
Suppose the current committee $W$ contains exactly one original candidate from each pair.
For an original type, satisfaction on $W$ equals its auxiliary utility. Lemma 1 therefore gives exactly the auxiliary canonical owner.
Guard $b_g$ has score $2$ on its pair’s selected member and score $0$ on every other selected member. It is consequently assigned wholly to its pair’s selected member.
Fix a selected candidate $c\in P_g$, and let $c'$ be its counterpart. Let $B_c$ be the original types currently assigned to $c$, and define
$$
H_c(d)=\sum_{t\in B_c}w_t s_{t,d}.
$$
Multiply all scores of this cluster by $3q+1$, which does not change comparisons. The scores of its own pair are
$$
6+H_c(c)
\qquad\text{and}\qquad
6+H_c(c').
$$
The constant $6$ comes from guard weight $3$ and guard satisfaction $2$.
Now consider all competing candidates.
Other original candidates and candidates in $D_1$. The guard gives each of them satisfaction at most $1$. Original types have satisfaction at most $2$, and
$$
\sum_{t\in B_c}w_t\le1.
$$
Their cluster score is therefore at most
$$
3+2\sum_{t\in B_c}w_t\le5.
$$
The incumbent’s score is at least $6$, so none can maximize this cluster.
Candidates in $D_0$. They receive score $2$ from the guard and score $0$ from every original type. Their cluster score is exactly $6$, which is at most the incumbent’s score.
It follows that:
Since the counterpart is an original candidate,
$$
H_c(c')-H_c(c)
=
\sum_{t\in B_c}w_t\bigl(u_{t,c'}-u_{t,c}\bigr).
$$
Thus the choice agrees exactly with the auxiliary pair-restricted update.
Every choice lies in its incumbent’s own pair. The pairs are disjoint, so all $q$ choices are distinct. There is no collision or vacancy. Starting from the corresponding initial committee, induction proves correspondence at every iteration.
Finally, whenever a pair changes, its guard’s positive mass moves between two different matrix coordinates. Hence consecutive assignment matrices differ. If no pair changes, the committee and canonical assignment remain identical. The first terminal iteration therefore agrees in both processes.
The construction and recovery of the auxiliary terminal committee are polynomial-time operations. This proves Theorem 4. $\square$
For completeness, the auxiliary endpoint always exists. On corresponding committees,
$$
F_{\mathrm{constructed}}(W)
=
\frac{6q+\sum_t w_t\max_{c\in W}u_{t,c}}{3q+1}.
$$
A paired change is a representative change in the constructed instance, so Lemma 2 strictly increases the auxiliary weighted score as well. There are only $2^q$ paired states.
Theorem 3 gives a denominator-independent polynomial algorithm for an additional class of instances.
Theorem 4 shows that the common-ranking satisfaction table does not prevent the original procedure from expressing arbitrary three-valued utility rows in the paired process. It also shows that collisions and filling need not be involved in a potential hardness construction.
However, the complexity of computing the paired process’s endpoint has not been established here. The simulation is therefore a proved reduction framework, not a hardness proof. A hardness result for that endpoint would transfer immediately to the original problem, already with constant maximum satisfaction $2$.
Nor would an exponential trajectory alone settle endpoint hardness: an algorithm might compute the endpoint without following every update.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with sound proved content. The output explicitly declines to resolve the general complexity question. Its termination argument, polynomial algorithm for a fixed number of distinct masses, and conditional simulation theorem are correct as written. None establishes polynomial-time solvability or hardness for the full input family.
The unresolved target is a major scope issue, not an identified error in the proofs of the partial results.
Lemma 1 correctly characterizes the prescribed lexicographically least maximizing assignment.
For each type, the row contribution is bounded by $\mu_t h_t(W)$. Because rows have independent constraints and there are no capacities, all these bounds are simultaneously attainable. Consequently, a globally maximizing assignment cannot put positive mass on a candidate whose satisfaction is below that row’s maximum.
Among the maximizing candidates, lexicographic minimization in increasing candidate-index order places zero mass at every coordinate before the largest-index maximizer. The row-sum constraint then forces that candidate to receive all of $\mu_t$.
Thus the formula using $a_W(t)$ is correct. Ties in satisfaction, coordinates outside the committee, and the ordering of types introduce no omitted cases.
Finding: correct and rigorous.
The first inequality in Lemma 2 follows from the incumbent tie rule: an incumbent changes only when its current score is strictly below the maximum.
The claim that a changed representative lies outside $W$ is also justified. Every type assigned to $c$ weakly prefers $c$, in satisfaction terms, to every member of $W$. Summing with the nonnegative assignment masses preserves that inequality. An empty cluster has all representative scores equal to zero and therefore retains its incumbent.
The proposed assignment $y$ correctly handles simultaneous updates and collisions. Its row sums remain $\mu_t$, and all its positive coordinates lie in the completed committee. No capacity restriction prevents combining masses at a common selected candidate. Filling adds candidates without invalidating this assignment.
Its objective value is exactly the sum of the individual cluster scores after representative selection. Hence any change gives a strict increase in $F$.
The stopping equivalence follows:
Finding: correct and rigorous, including collisions and empty clusters.
Strict improvement prevents a committee from recurring along the transitions preceding termination. If there are $s$ strict transitions, they visit $s+1$ distinct committees; the subsequent terminal comparison occurs at index $s+2$. This establishes
$$
I\le \binom{m}{k}+1.
$$
The exact arithmetic argument is valid. The product $Q$ of the input denominators has bit length bounded by their total encoding length, up to a routine additive constant. Each $w_t=Q\mu_t$ is an integer, and
$$
\sum_t w_t=Q.
$$
Thus every representative comparison integer is nonnegative and at most $Q\gamma(1)$. Its bit length is polynomial in the input length. Ownership, tie resolution, filling, and equality comparison can all be performed exactly in polynomial time per iteration.
Since $\binom{m}{k}\le 2^m$, the stated exponential-time bound follows. Retaining only the current state and arithmetic data gives polynomial space.
The boundary cases are correct:
Finding: correct. These bounds establish termination and resource upper bounds, but do not settle the requested polynomial-time-versus-hardness question.
Theorem 3 is valid.
Each $h_t(W)-\gamma(m)$ is an integer between zero and $\Delta$, so
$$
0\le Z_j(W)\le n_j\Delta.
$$
The identity
$$
F(W)=\gamma(m)+\sum_{j=1}^{d}\alpha_j Z_j(W)
$$
correctly uses the normalization of the masses.
Repeated vectors would give repeated scores, which strict improvement excludes. Injectivity of the map from vectors to scores is unnecessary: the argument only needs equal vectors to imply equal scores.
There are at most
$$
\prod_{j=1}^{d}(n_j\Delta+1)
$$
vectors. Counting the initial state, strict transitions, and final comparison gives the claimed bound with the correct indexing.
For fixed $d$,
$$
\prod_{j=1}^{d}(n_j\Delta+1)\le(\tau\Delta+1)^d
$$
is polynomial because $\Delta\le p(m)$. The argument is independent of numerical separation between distinct masses and of the magnitudes of their denominators.
The restriction that $d$ is fixed is essential to the stated polynomial conclusion; the output states it explicitly.
Finding: correct restricted polynomial-time result.
The candidate counts are consistent:
$$
n+(n-2)+(2n+2)=4n=8q.
$$
For an original type, the multiplicities assigned on $D_1$ are nonnegative and sum to $2n+2$. Including the original candidates and $D_0$ gives exactly $n$ scores equal to two, $n$ equal to one, and $2n$ equal to zero.
For a guard, the corresponding counts are
$$
2+(n-2)=n,\qquad n,\qquad (n-2)+(n+2)=2n.
$$
Thus every constructed row is realizable by a strict complete ranking under the common table.
The constructed masses are positive, sum to one, and have polynomial encoding length. The ranking construction also has polynomial size.
The restriction $q\ge2$ ensures $D_0$ is nonempty. This supports the stated distinction between guard rankings and original-type rankings. Different guards also have different satisfaction rows on the original candidates.
Combining identical rankings preserves canonical ownership and all weighted representative scores. Recovering original-type assignments from the terminal committee is justified by their preserved utility rows.
The satisfaction-bound qualification is explicit: this construction belongs to the permitted family when $p(8q)\ge2$. The simulation should be read with that qualification.
Finding: correct construction.
At a corresponding committee, original types have precisely their auxiliary owners. Each guard is assigned uniquely to the selected candidate in its own pair.
After multiplying cluster scores by $3q+1$, the two own-pair candidates have scores
$$
6+H_c(c),\qquad 6+H_c(c').
$$
Every other original candidate or member of $D_1$ has score at most
$$
3+2\sum_{t\in B_c}w_t\le5.
$$
Every member of $D_0$ has score exactly six. These bounds are valid even when $B_c$ is empty.
If the counterpart does not strictly improve $H_c$, the incumbent is a global maximizer and is retained. If it does strictly improve $H_c$, it beats the incumbent and every candidate outside the pair, making it the unique global maximizer.
Consequently, every update agrees with the auxiliary process. Choices stay within disjoint pairs, so collisions and filling cannot occur.
A changed pair moves its guard’s positive mass between different candidate coordinates, ensuring that consecutive assignment matrices differ. An unchanged committee has the same canonical assignment. Therefore the stopping events correspond exactly.
Finally, the displayed potential identity has the correct guard contribution $6q$, and establishes termination of the auxiliary process through Lemma 2.
Finding: correct conditional reduction framework. No endpoint-hardness conclusion follows without a hardness result for the auxiliary process.
Major — the assigned general complexity question remains unresolved. Neither the fixed-$d$ bound nor the simulation classifies the full rational-mass problem.
No repair to the proved lemmas is needed on the evidence presented. To complete the assignment, the prover must supply either a polynomial-time algorithm for unrestricted instances or a hardness proof for the specified endpoint computation. If pursuing the simulation, the missing component is endpoint hardness for the precisely defined paired process, with the satisfaction-bound qualification preserved.
An exponential trajectory alone would not supply that component. The output correctly acknowledges this limitation.
⟨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.