Answer: \(\kappa_{\operatorname{AV}}(k,p)=k^{-1}\min_{0\le h\le k}[h+(k-h)p^{-h}]\). For CC, the guarantee is \(1\) for \(k=1\) and \(p/(p+1)\) for \(k=2\). For \(k\ge3\), put \(a=p-(p-1)/k\) and \(Z=2(k-1)p-k+3\). The CC guarantee is \((1+\max_{3\le h\le k}(ah-1)p^{-h})^{-1}\) when \((2p-3)a\le p-1\), and \(pZ/[pZ+2(k-1)p+1]\) otherwise. Every value is attained by a rational society and a worst tied winner.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe AV-guarantee of the p-geometric rule is be- tween W(k log(p)) k log(p) + W(k log(p)) and 2W(k log(p)) k log(p) + 1 k , its CC-guarantee is between p−1 p and p p+ k k+2 .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), \(p\ge1\), and a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\) over approval types, choose \(W\in\binom{C}{k}\) maximizing \(G_{p,\mu}(W)=\sum_{A\subseteq C}\mu_A\sum_{j=1}^{|A\cap W|}p^{-j}\), where \(\operatorname{AV}_\mu(W)=\sum_A\mu_A|Acap W|\) and \(\operatorname{CC}_\mu(W)=\sum_A\mu_A\mathbf{1}[A\cap W\ne\varnothing]\); compute the resulting AV and CC ratios and characterize their worst cases over \(\mu\) and tied winners.
Let \(C\) be a finite candidate set, \(m=|C|\), \(1\le k\le m\), and \(p\ge1\) a binary rational. A society is given by its support: the list of the \(\tau\) approval types \(A\subseteq C\) with positive mass, each mass \(\mu_A\) a binary rational; \(\sum_A\mu_A=1\). Here \(\tau\) is the support size, not the number of possible approval sets. Let \(L\) be the total input bit length; state any running times in \(m,\tau,L,k\).
Empty approval sets are allowed, but require \(\sum_{A\ne\varnothing}\mu_A>0\). Committees are ordinary subsets of exactly \(k\) candidates.
Define \(G_{p,\mu}(W)=\sum_A\mu_A\sum_{j=1}^{|A\cap W|}p^{-j}\), with an empty inner sum equal to zero, and let \(R_p(\mu,k)=\operatorname*{arg\,max}_{W\in\binom{C}{k}}G_{p,\mu}(W)\); retain every tied winner.
Define \(\operatorname{AV}_\mu(W)=\sum_A\mu_A|A\cap W|\) and \(\operatorname{CC}_\mu(W)=\sum_A\mu_A\mathbf1[A\cap W\ne\varnothing]\).
For \(X\in\{\operatorname{AV},\operatorname{CC}\}\), the instance ratio is \(r_X(\mu,k,p)=\frac{\min_{W\in R_p(\mu,k)}X_\mu(W)}{\max_{V\in\binom{C}{k}}X_\mu(V)}\), and its worst-case guarantee is \(\kappa_X(k,p)=\inf_{C,\mu}r_X(\mu,k,p)\), over all finite candidate sets and admissible rational societies.
What are the sharp worst-case AV and CC approximation guarantees \(\kappa_{\operatorname{AV}}(k,p)\) and \(\kappa_{\operatorname{CC}}(k,p)\), and which societies and tied winners attain or approach them?
For finite electorates, known bounds for \(k\ge2\) and \(p>1\) are \(\frac{\mathcal W(k\log p)}{k\log p+\mathcal W(k\log p)}\le\kappa_{\operatorname{AV}}\le\frac{2\mathcal W(k\log p)}{k\log p}+\frac1k\) and \(\frac{p-1}{p}\le\kappa_{\operatorname{CC}}\le\frac{p}{p+k/(k+2)}\), where \(\mathcal W\) is the principal Lambert W function and \(\log\) is natural. [Lackner–Skowron](https://www.ijcai.org/proceedings/2019/0058.pdf)
The later full version retains these bounds; no exact characterization for rational-mass societies was located in the search. [Full version](https://arxiv.org/pdf/1801.01527)
Both guarantees admit exact formulas, and every value below is attained by a rational society and a worst tied winner.
For every \(k\ge1\) and rational \(p\ge1\),
\( \displaystyle \boxed{\kappa_{\operatorname{AV}}(k,p) =\frac1k\min_{0\le h\le k}\left(h+(k-h)p^{-h}\right).} \)
For CC, the boundary cases are
\( \displaystyle \boxed{\kappa_{\operatorname{CC}}(1,p)=1, \qquad \kappa_{\operatorname{CC}}(2,p)=\frac{p}{p+1}.} \)
For \(k\ge3\), define
\( \displaystyle a=p-\frac{p-1}{k}, \qquad d_h=(ah-1)p^{-h}, \qquad Z=2(k-1)p-k+3. \)
Then
\( \displaystyle \boxed{ \kappa_{\operatorname{CC}}(k,p)= \begin{cases} \left(1+\max_{3\le h\le k}d_h\right)^{-1}, & (2p-3)a\le p-1,\\[2mm] \displaystyle\frac{pZ}{pZ+2(k-1)p+1}, & (2p-3)a>p-1. \end{cases}} \)
The two expressions agree at the regime boundary. In particular,
\( \displaystyle \kappa_{\operatorname{AV}}(k,1)=1, \qquad \kappa_{\operatorname{CC}}(k,1)=\frac1k. \)
For example,
\( \displaystyle \kappa_{\operatorname{CC}}(3,p)= \begin{cases} \displaystyle\frac{p^2}{p^2+2},&1\le p\le\frac74,\\[2mm] \displaystyle\frac{4p^2}{(2p+1)^2},&p\ge\frac74. \end{cases} \)
The bounds quoted in the question appear in Theorem 5 of the [full version of Lackner–Skowron](https://arxiv.org/pdf/1801.01527). The proofs of the exact formulas follow.
Write
\( \displaystyle g_p(t)=\sum_{j=1}^{t}p^{-j}, \qquad g_p(0)=0, \)
and let \(\mathbb E\) denote expectation over approval types with masses \(\mu_A\).
The denominators in both instance ratios are positive: some candidate has positive approval mass, and some size-\(k\) committee contains that candidate.
Fix a winning committee \(W\) and any other size-\(k\) committee \(V\). Define
\( \displaystyle I=W\cap V,\qquad B=W\setminus V,\qquad D=V\setminus W. \)
Suppose \(s=|B|=|D|>0\). For an approval type \(A\), put
\( \displaystyle i=|A\cap I|,\quad b=|A\cap B|,\quad d=|A\cap D|, \quad w=i+b,\quad v=i+d. \)
For \(x\in B\) and \(y\in D\), direct examination of the four approval possibilities gives
\( \displaystyle g_p\!\left(|A\cap(W-\{x\}+\{y\})|\right)-g_p(w) = \mathbf1[y\in A]p^{-(w+1)} -\mathbf1[x\in A]p^{-w} +(p-1)\mathbf1[x,y\in A]p^{-(w+1)}. \)
Every such exchange has nonpositive expected gain because \(W\) is a winner. Summing over all \(s^2\) exchanges and multiplying by \(p/s\) yields
\[ \displaystyle \mathbb E[\delta]\ge0, \qquad \delta= b p^{1-w} -d\left(1+\frac{(p-1)b}{s}\right)p^{-w}. \tag{1} \]
We also have the global comparison
\[ \displaystyle \mathbb E[g_p(w)-g_p(v)]\ge0. \tag{2} \]
These inequalities allow \(W\) and \(V\) to overlap.
Set
\( \displaystyle \rho=\frac1k\min_{0\le h\le k}\left(h+(k-h)p^{-h}\right). \)
Thus \(0<\rho\le1\). We prove the pointwise inequality
\[ \displaystyle w-\rho v\ge\delta. \tag{3} \]
For fixed \(i,b\), the difference between the two sides is affine in \(d\). Since \(0\le d\le s\), checking its endpoints suffices.
At \(d=0\), this difference is
\( \displaystyle (1-\rho)i+b\left(1-p^{1-w}\right). \)
It is zero when \(w=0\), and nonnegative when \(w\ge1\).
At \(d=s\), the difference is
\( \displaystyle w-\rho(i+s)+(s-b)p^{-w}. \)
Let \(n=i+s\). Then \(w\le n\le k\), and this expression equals
\( \displaystyle w+(n-w)p^{-w}-\rho n. \)
For \(n>0\),
\( \displaystyle \frac{w+(n-w)p^{-w}}{n} =p^{-w}+\frac{w}{n}(1-p^{-w}) \ge p^{-w}+\frac{w}{k}(1-p^{-w}) \ge\rho. \)
This proves (3). Taking expectations and using (1) gives
\( \displaystyle \operatorname{AV}_\mu(W)\ge\rho\,\operatorname{AV}_\mu(V). \)
If \(W=V\), the same conclusion is immediate. Choosing an AV-optimal \(V\) proves the lower bound for every winning \(W\).
Choose a minimizing integer \(h\). Take a party block \(P\) of \(k\) candidates and \(k-h\) additional candidates \(D\). Assign masses
\( \displaystyle \mu_P=t,\qquad \mu_{\{d\}}=t p^{-h}\quad(d\in D), \qquad t=\frac{1}{1+(k-h)p^{-h}}. \)
Let \(W\) contain \(h\) candidates of \(P\) and every candidate of \(D\).
Any size-\(k\) committee contains some number \(b\ge h\) of party candidates. Its score is
\( \displaystyle t g_p(b)+t(k-b)p^{-(h+1)}. \)
Increasing \(b\) by one changes this score by
\( \displaystyle t\left(p^{-(b+1)}-p^{-(h+1)}\right)\le0. \)
Thus \(W\) is a winner. Whenever \(h<k\), committees containing \(h+1\) party candidates also tie with \(W\).
Each party candidate has approval mass \(t\), while each additional candidate has approval mass \(tp^{-h}\le t\). Hence \(P\) is AV-optimal, and
\( \displaystyle \frac{\operatorname{AV}_\mu(W)} {\operatorname{AV}_\mu(P)} = \frac{h+(k-h)p^{-h}}{k} =\rho. \)
The universal lower bound ensures that \(W\) is a worst tied winner. This society has \(m=2k-h\) and \(\tau=1+k-h\).
Assume \(p>1\) and \(k\ge3\). Put \(q=p^{-1}\), and define
\( \displaystyle T_h=\sum_{j=1}^{h-1}q^j, \qquad d_h=(ah-1)q^h, \qquad a=p-\frac{p-1}{k}. \)
For \(0\le\lambda\le1\), let
\( \displaystyle F_h(\lambda)=\lambda d_h+(1-\lambda)T_h, \quad z_\lambda=\max_{1\le h\le k}F_h(\lambda), \quad \rho_\lambda=\frac{1}{1+z_\lambda}. \)
We will prove
\[ \displaystyle \operatorname{CC}_\mu(W) \ge\rho_\lambda\,\operatorname{CC}_\mu(V) \tag{4} \]
for every winning \(W\), every size-\(k\) committee \(V\), and every \(\lambda\).
When \(W\ne V\), use the notation of Section 2 and set
\( \displaystyle J=p\bigl(g_p(w)-g_p(v)\bigr). \)
By (1) and (2), both \(\mathbb E[\delta]\) and \(\mathbb E[J]\) are nonnegative. It therefore suffices to prove
\[ \displaystyle \mathbf1[w>0]-\rho_\lambda\mathbf1[v>0] \ge \rho_\lambda\bigl(\lambda\delta+(1-\lambda)J\bigr) \tag{5} \]
pointwise.
Both committees cover the type. If \(w>0\) and \(v>0\), then \(J\le T_w\). Also \(\delta\le d_w\):
\( \displaystyle \delta \le \left[\left(p-\frac{p-1}{s}\right)b-1\right]q^w \le(aw-1)q^w=d_w. \)
\( \displaystyle \delta\le(w-1)p^{1-w}\le d_w. \)
The last inequality follows from
\( \displaystyle d_w-(w-1)p^{1-w} =(p-1)\left(1-\frac wk\right)q^w\ge0. \)
Consequently, the right side of (5) is at most
\(\rho_\lambda z_\lambda=1-\rho_\lambda\).
Only \(W\) covers the type. Here \(i=d=0\), so
\( \displaystyle \delta=w p^{1-w},\qquad J=1+T_w. \)
Bernoulli’s inequality gives
\( \displaystyle p^w\ge1+w(p-1)\ge1+\frac{w(p-1)}{k}, \)
and therefore \(\delta\le1+d_w\). The right side of (5) is at most
\(\rho_\lambda(1+z_\lambda)=1\).
Only \(V\) covers the type. Here \(w=0\), \(d\ge1\), and
\( \displaystyle \delta=-d\le-1,\qquad J=-p g_p(v)\le-1. \)
Thus the right side of (5) is at most \(-\rho_\lambda\).
Neither committee covers the type. Both sides vanish.
Taking expectations proves (4). The case \(W=V\) is immediate.
First observe that, for \(h\ge3\),
\[ \displaystyle p^hT_h =\sum_{r=1}^{h-1}p^r \ge(h-1)+\frac{h(h-1)}2(p-1) \ge ah-1=p^h d_h. \tag{6} \]
The first inequality is Bernoulli’s inequality applied separately to each power.
The successive differences are
\[ \displaystyle d_{h+1}-d_h =q^h\left[aq-(ah-1)(1-q)\right]. \tag{7} \]
The bracket strictly decreases with \(h\).
If \((2p-3)a\le p-1\), equivalently \(d_3\ge d_2\), a maximizer of \(d_h\) can be chosen with \(h\ge3\). Taking \(\lambda=1\) in (4) gives
\[ \displaystyle \kappa_{\operatorname{CC}}(k,p) \ge\left(1+\max_{3\le h\le k}d_h\right)^{-1}. \tag{8} \]
If \((2p-3)a>p-1\), choose
\( \displaystyle \lambda_*=\frac{p}{a(2p-3)+1}. \)
The regime condition implies \(0<\lambda_*<1\). Furthermore,
\[ \displaystyle F_{h+1}(\lambda)-F_h(\lambda) =q^h\left[1+\lambda q(a-1)-\lambda ah(1-q)\right]. \tag{9} \]
For \(\lambda=\lambda_*\), the bracket is zero at \(h=2\), positive below it, and negative above it. Hence the maximum is attained at \(h=2,3\).
To evaluate its value, define
\( \displaystyle \theta_2=\frac{k(p-1)+3}{Z}, \qquad \theta_3=\frac{(k-2)p}{Z}, \qquad Z=2(k-1)p-k+3. \)
These are positive and sum to one. Direct calculation gives
\( \displaystyle d_2-T_2=\frac{(p-1)(k-2)}{kp^2}, \qquad T_3-d_3=\frac{(p-1)(p-1+3/k)}{p^3}. \)
Thus
\[ \displaystyle \theta_2d_2+\theta_3d_3 =\theta_2T_2+\theta_3T_3 =\frac{2(k-1)p+1}{pZ} =:z. \tag{10} \]
Since \(F_2(\lambda_*)=F_3(\lambda_*)\), averaging them with these weights shows that their common value is \(z\). Therefore (4) gives
\[ \displaystyle \kappa_{\operatorname{CC}}(k,p) \ge\frac1{1+z} =\frac{pZ}{pZ+2(k-1)p+1}. \tag{11} \]
The following lemma supplies the sharpness check beyond single exchanges.
Lemma. Let \(B,D\) be disjoint candidate blocks of size \(k\), and suppose a covered voter approves a uniformly chosen \(h\)-subset of \(B\) and one uniformly chosen candidate of \(D\), independently. Allow either a fixed \(h\), or a mixture of \(h=2\) and \(h=3\).
For a committee containing \(k-l\) candidates of \(B\) and \(l\) candidates of \(D\), define
\( \displaystyle A_l=\frac{kp}{l}\left( \text{expected covered-voter score of }B -\text{expected covered-voter score of that committee} \right). \)
For every \(1\le l\le k\),
\[ \displaystyle A_l\ge\min(A_1,A_k). \tag{12} \]
If \(\theta_h\) denotes the distribution of approval counts, then
\[ \displaystyle A_1=\sum_h\theta_h d_h, \qquad A_k=\sum_h\theta_h T_h. \tag{13} \]
Proof. Put \(q=p^{-1}\) and \(\gamma=1-q\). Let \(M_l\) be the expected value of \(q\) raised to the number of approved candidates among the \(k-l\) selected candidates of \(B\). Sampling the \(l\) omitted candidates gives
\[ \displaystyle M_l= \frac{[t^l]Q(t)}{\binom{k}{l}}, \qquad Q(t)=\sum_h\theta_h q^h(1+pt)^h(1+t)^{k-h}. \tag{14} \]
Here \([t^l]Q(t)\) means the coefficient of \(t^l\).
The approved candidate in \(D\) belongs to the committee with probability \(l/k\), independently. Hence, with
\( \displaystyle P_l=\left(1-\frac{\gamma l}{k}\right)M_l, \)
the expected covered-voter score is \((1-P_l)/(p-1)\). Consequently,
\[ \displaystyle A_l=\frac{kp}{p-1}\frac{P_l-P_0}{l}. \tag{15} \]
We verify that the secant slopes in (15) have no strict interior minimum.
For a pure approval count \(h\),
\( \displaystyle Q(t)=q^h(1+pt)^h(1+t)^{k-h}. \)
For a mixture of counts \(2,3\),
\( \displaystyle Q(t)=c(1+pt)^2(1+t)^{k-3}(1+rt), \quad c=q^2(\theta_2+q\theta_3), \quad r=\frac1{\theta_2+q\theta_3}. \)
In the latter case \(1\le r\le p\). Thus in both cases
\( \displaystyle Q(t)=c\prod_{j=1}^{k}(1+w_jt) \)
with all \(w_j\ge1\).
Let \(e_l\) denote the elementary symmetric polynomial of degree \(l\), and put \(u_l=M_{l+1}-M_l\). A counting identity gives
\[ \displaystyle u_l= \frac{c}{k\binom{k-1}{l}}[t^l]H(t), \quad H(t)=\sum_{j=1}^{k}(w_j-1)\prod_{i\ne j}(1+w_it). \tag{16} \]
For a pure count,
\( \displaystyle H(t)=h(p-1)(1+pt)^{h-1}(1+t)^{k-h}. \)
For the mixture,
\( \displaystyle H(t) =(1+t)^{k-3}(1+pt) \left[2(p-1)(1+rt)+(r-1)(1+pt)\right]. \)
The bracket is a positive constant times \(1+st\), where
\( \displaystyle s=\frac{2(p-1)r+(r-1)p}{2(p-1)+(r-1)}\ge1. \)
Therefore, in either case, \(u_l\) is a positive constant times
\(e_l(v_1,\ldots,v_{k-1})/\binom{k-1}{l}\), with all \(v_j\ge1\).
We use Newton’s inequalities in their precise normalized form: for positive \(v_1,\ldots,v_n\), the sequence
\(e_l(v_1,\ldots,v_n)/\binom nl\) is log-concave. Thus
\( \displaystyle u_l^2\ge u_{l-1}u_{l+1}. \)
This sequence is also nondecreasing. Indeed, couple a uniformly chosen subset of size \(l\) with one of size \(l+1\) by adding a uniformly chosen remaining element; the product cannot decrease because every \(v_j\ge1\).
It follows that \(u_{l+1}/u_l\) is nonincreasing and at least one. Direct subtraction now yields
\[ \displaystyle P_{l+2}-2P_{l+1}+P_l = u_l\left[ \left(1-\frac{\gamma(l+2)}k\right) \left(\frac{u_{l+1}}{u_l}-1\right) -\frac{2\gamma}{k} \right]. \tag{17} \]
The bracket is nonincreasing in \(l\): its two factors before the subtraction are nonnegative and nonincreasing. Hence the second differences of \(P_l\) can change sign only from nonnegative to nonpositive. Its first differences therefore increase and then decrease.
The averages of initial segments of an increasing-then-decreasing sequence also increase and then decrease. To see this explicitly, once a new term falls below the preceding average, the new average remains above that term, and every subsequent term is no larger. Thus the averages cannot start increasing again.
The quantities \((P_l-P_0)/l\) are precisely these initial-segment averages. Their minimum is therefore at \(l=1\) or \(l=k\), proving (12).
Finally,
\( \displaystyle M_0=\sum_h\theta_hq^h,\quad M_1=\sum_h\theta_hq^h\left(1+\frac{h(p-1)}k\right), \quad M_k=1. \)
Substitution into (15) gives (13). This completes the lemma. ∎
Take disjoint blocks \(B,D\), each of size \(k\). Choose a number \(z\) and a distribution \(\theta_h\) as follows:
Put \(\rho=1/(1+z)\). For every \(d\in D\), assign singleton mass
\( \displaystyle \mu_{\{d\}}=\frac{1-\rho}{k}. \)
For every \(S\subseteq B\) of size \(h\) and every \(d\in D\), assign
\[ \displaystyle \mu_{S\cup\{d\}} =\frac{\rho\theta_h}{k\binom{k}{h}}. \tag{18} \]
Omit types whose indicated weight is zero. These masses sum to one.
Every voter approves exactly one candidate of \(D\). Therefore
\( \displaystyle \operatorname{CC}_\mu(D)=1, \qquad \operatorname{CC}_\mu(B)=\rho. \)
Consider any competing committee containing \(l\) candidates of \(D\). Symmetry makes its score depend only on \(l\). For \(l\ge1\), the sampling lemma gives
\[ \displaystyle G_{p,\mu}(B)-G_{p,\mu}(T_l) =\frac{\rho l}{kp}(A_l-z). \tag{19} \]
In the first regime, \(A_1=d_H=z\), while \(A_k=T_H\ge d_H\) by (6). In the second regime, (10) gives \(A_1=A_k=z\). Thus (12) proves that (19) is nonnegative for every competing committee.
Consequently, \(B\) is a winning committee with ratio \(\rho\), matching the universal lower bound. It is therefore a worst tied winner.
There are explicit ties:
All masses are rational. The first construction has
\( \displaystyle m=2k,\qquad \tau=k\left(1+\binom{k}{H}\right), \)
and the second has
\( \displaystyle m=2k,\qquad \tau=k\left(1+\binom{k}{2}+\binom{k}{3}\right). \)
For \(k=1\), both objectives equal the approval mass of the selected candidate, so both guarantees are one.
For \(p=1\), the rule is AV. If \(W\) is an AV winner and \(V\) is CC-optimal, then
\( \displaystyle \operatorname{CC}_\mu(W) \ge\frac{\operatorname{AV}_\mu(W)}k \ge\frac{\operatorname{AV}_\mu(V)}k \ge\frac{\operatorname{CC}_\mu(V)}k. \)
To attain equality, take a block \(B\) of \(k\) candidates and \(k-1\) additional singleton candidates. Give approval type \(B\) mass \(1/k\), and each singleton type mass \(1/k\). Every candidate has the same approval mass, so every size-\(k\) committee wins. The committee \(B\) covers mass \(1/k\), whereas one member of \(B\) together with all singleton candidates covers everyone.
For \(k=2\), every committee \(T\) satisfies
\( \displaystyle p^{-1}\operatorname{CC}_\mu(T) \le G_{p,\mu}(T) \le(p^{-1}+p^{-2})\operatorname{CC}_\mu(T). \)
Comparing a winning \(W\) with a CC-optimal \(V\) therefore gives the lower bound \(p/(p+1)\).
For attainment, use three candidates \(a,b,d\), with
\( \displaystyle \mu_{\{a,b\}}=\frac{p}{p+1}, \qquad \mu_{\{d\}}=\frac1{p+1}. \)
All three size-two committees have score \(1/p\). The committee \(\{a,b\}\) covers mass \(p/(p+1)\), while either mixed committee covers everyone.
The constructions prove exact attainment; no limiting sequence is required. Clearing a common denominator of the rational masses produces a finite electorate with identical scores up to scaling, identical tied winners, and identical ratios.
The values require only a scan of \(k+1\) AV expressions and, in the first CC regime, at most \(k-2\) CC expressions. All comparisons can be performed exactly over rationals.
Using schoolbook integer arithmetic, a conservative bound for computing both guarantees is
\( \displaystyle O\!\left(L+k^3\bigl(L+\log(k+1)\bigr)^2\right) \)
bit operations. The calculation is independent of \(m,\tau\), apart from reading the input: the guarantees depend only on \(k,p\).
If an attaining society is output as an explicit support list, its construction takes \(O(\tau m\,\operatorname{poly}(k,L))\) bit operations, with \(m,\tau\) as stated above. In particular, the first CC witness can have exponentially many support types; evaluating its guarantee does not require listing them.
⟨structured verdict parsed — rendered above⟩
Verdict: proved with a minor domain clarification. The AV and CC formulas, their universal lower bounds, and their rational attaining societies are correct. The sampling lemma establishes global optimality of the proposed CC winners, so the sharpness argument checks every competing committee, including committees differing by several replacements.
The only issue is that the sampling lemma should state its parameter restrictions explicitly. Its actual applications satisfy those restrictions.
The output addresses both requested guarantees and supplies explicit attaining societies and winning committees. It also addresses rationality, finite-electorate realization, support sizes, and running times.
The positivity of both ratio denominators is correctly justified: the positive mass on nonempty approval sets ensures that some candidate has positive approval mass, and that candidate belongs to a size-\(k\) committee.
Empty approval types cause no difficulty. Their contributions to all objectives and exchange inequalities vanish.
The attribution of the previously known bounds to Theorem 5 is accurate. [Lackner–Skowron, full version](https://arxiv.org/pdf/1801.01527)
The four approval possibilities give the stated exchange identity, including the correction term when both exchanged candidates are approved.
Summing over the \(s^2\) exchanges gives exactly the stated \(\delta\), with the correct sign in inequality (1). Division by \(s\) is valid because this argument explicitly assumes \(s>0\).
Inequality (2) follows directly from global optimality of \(W\). The notation and inequalities correctly accommodate overlapping committees. The separate treatment of \(W=V\) avoids division by zero.
Assessment: correct.
The difference in (3) is affine in \(d\), so checking \(d=0\) and \(d=s\) suffices.
At \(d=0\), the stated expression is correct. For \(w\ge1\), both terms are nonnegative because \(\rho\le1\) and \(p^{1-w}\le1\). For \(w=0\), both \(i\) and \(b\) vanish.
At \(d=s\), the expression correctly simplifies using \(n=i+s\). The restrictions \(w\le n\le k\) hold. The subsequent comparison is valid because \(1-p^{-w}\ge0\), and \(w\) is an integer in the minimization defining \(\rho\).
Taking expectations and applying (1) therefore proves the AV comparison for every winning committee. Choosing an AV-optimal \(V\) establishes the claimed universal lower bound.
The masses are positive rationals and sum to one. Every size-\(k\) committee contains at least \(h\) party candidates, and the displayed score and successive score differences are correct. Thus the proposed \(W\) is globally winning.
The individual candidate approval masses establish that \(P\) is AV-optimal, including when those masses tie. The displayed ratio equals \(\rho\).
The universal lower bound then correctly establishes that \(W\) is a worst winning committee. The claimed support size, candidate count, and additional ties are correct.
Assessment: correct, including \(p=1\), \(k=1\), and the endpoint choices of \(h\).
The pointwise argument covers all four coverage possibilities.
Consequently, (5) and its expectation correctly establish (4). In particular, this is a bound for every winning committee, as required by the adversarial treatment of ties.
Assessment: correct.
The calculation in (6) is valid for \(h\ge3\). The successive differences (7) and (9) are correct, and their brackets have the claimed monotonicity.
In the first regime, \(d_3\ge d_2\), together with the decreasing successive-difference bracket, justifies choosing a maximizer with \(h\ge3\). This also excludes \(h=1\) from being a necessary maximizer.
In the second regime:
Thus (8) and (11) follow. The expressions agree at the regime boundary, and the stated specialization for \(k=3\) is algebraically consistent.
Assessment: correct.
For the parameter ranges used in the attainment constructions, the lemma’s proof is valid.
The coefficient formula (14) correctly describes sampling omitted candidates. Independence of the chosen approved candidate in \(D\) gives the displayed \(P_l\), and the geometric-score identity gives (15).
The factorizations of \(Q\) and \(H\), the counting identity (16), and the expression for the mixture parameter \(r\) are correct.
Newton’s inequalities are stated in the appropriate normalized form. Their hypotheses hold: all the relevant variables are positive. The additional condition that they are at least one justifies the monotonicity argument using coupled subsets.
Equation (17) is correct. Over its applicable index range, both factors identified in its bracket are nonnegative and nonincreasing. The resulting sign pattern of second differences therefore gives the asserted unimodality of first differences.
The argument about initial-segment averages is valid, including equality cases. It establishes the endpoint minimum needed for (12). Substituting the stated endpoint values of \(M_l\) correctly gives (13).
The lemma does not explicitly state \(p>1\) or that a fixed approval count satisfies \(1\le h\le k\). Its proof divides by \(p-1\) and by positive \(u_l\), so those restrictions matter. The mixture case also requires \(k\ge3\).
Minimum clarification: explicitly state these restrictions in the lemma. All applications in Section 6 already satisfy them, and the boundary cases are handled separately.
The masses in (18), together with the singleton masses, are positive on the listed support and sum to one. The societies are admissible and rational.
Every voter approves exactly one candidate in \(D\), so the stated CC values of \(D\) and \(B\) are correct. Because the candidate set consists of the two blocks, every competing committee is covered by the parameter \(l\). Symmetry legitimately removes dependence on the particular selected candidates.
Equation (19) correctly accounts for both covered voters and singleton voters. The sampling lemma then establishes that \(B\) beats or ties every competing committee.
The stated one-replacement ties follow from \(A_1=z\). In the second regime, \(A_k=z\) also establishes the tie with \(D\). The support-size calculations are correct.
As supplementary arithmetic checks, exact rational evaluations passed for all constructed committees at seven values of \(p>1\) and every \(3\le k\le15\). These checks support, but do not replace, the general proof.
Assessment: correct global attainment.
The \(k=1\) argument is correct for both objectives.
At \(p=1\), the rule is AV. The CC comparison chain is valid, and the proposed society attains equality.
For \(k=2\), the score bounds hold for each possible intersection size. Their comparison gives the claimed lower bound, and all three committees in the attaining construction indeed have score \(1/p\).
Clearing rational denominators preserves scores up to a common positive factor, hence preserves winners, ties, and ratios.
The exact rational scans and the conservative bit-operation bound are consistent with the sizes of the powers and rational comparisons involved. The explicit-support construction bound appropriately permits an exponentially large witness support.
This establishes polynomial-time evaluation of the worst-case guarantees in the stated parameters. It does not assert polynomial-time winner determination or instance-ratio computation for an arbitrary society.
⟨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.