Answer: Polynomial-time solvable in \(m,\tau,L\); a \(\mathrm{BSP}\) allocation always exists.
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIt can be verified in polynomial time whether a given committee is BSP. Besides, for given election instance and price p, a BSP committee can be found in polynomial time. We discuss this issue in detail in Appendix A.10— intuituvely, we design a voting rule computable in polynomial time characterizing the set of BSP committees. This rule is a slight modification of a rule that was recently proposed by Peters and Skowron (2020) under the name of Rule X. Basing on the characterization, in Appendix C.2 we de- scribe a polynomial-time heuristic algorithm for finding BSP committees of a specified size k.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a finite support \(T\subseteq 2^C\) of approval types with rational masses \(\mu_A\geq 0\) summing to \(1\), and a rational mass price \(p>0\), find a BSP committee and supporting allocation, with no prescribed committee size. Choose \(W\subseteq C\), prices \(\rho_c\in[0,1]\), and masses \(x_{A,U}\geq 0\) for \(A\in T\) and \(U\subseteq W\cap A\), where \(\sum_U x_{A,U}=\mu_A\), each used bundle costs at most one, and \(\rho_c\sum_{A,U:c\in U}x_{A,U}=p\) for each \(c\in W\). Require BSP stability: no coalition formed from submasses of the \((A,U)\) cohorts can switch to newly proposed candidates \(W'\subseteq C\setminus W\), use balanced per-candidate prices, stay within each participant’s unit budget, make every participant weakly prefer the new utility/payment pair under the paper’s utility-first and lower-payment tie-break, and raise strictly more than \(p\) for every proposed candidate.
Let \(C\) have \(m\geq1\) candidates. A society is given by its support: \(T\subseteq2^C\), listing its \(\tau=|T|\) approval types with positive binary-rational masses \(\mu_A\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. The input also contains a binary rational \(p>0\); let \(L\) be the total input bit length. Each individual has budget \(1\).
Find a committee \(W\subseteq C\), with no prescribed size, prices \(\rho_c\in[0,1]\), and masses \(x_{A,U}\geq0\) for \(U\subseteq W\cap A\), satisfying \(\sum_Ux_{A,U}=\mu_A\), \(x_{A,U}>0\Rightarrow\sum_{c\in U}\rho_c\leq1\), and \(\rho_c\sum_{A,U:c\in U}x_{A,U}=p\) for every \(c\in W\). A member of cohort \((A,U)\) has utility \(|U|\) and payment \(\sum_{c\in U}\rho_c\); approvals outside the purchased bundle give no utility.
A blocking deviation chooses \(\varnothing\neq W'\subseteq C\setminus W\), common prices \(q_c\in[0,1]\), and nonnegative real submasses \(y_{A,U,R,V}\), indexed by \(R\subseteq U\) and \(V\subseteq W'\cap A\), with \(\sum_{R,V}y_{A,U,R,V}\leq x_{A,U}\). Participants drop \(R\), retain \(U\setminus R\), and purchase \(V\).
For every positive submass, set \(b=\sum_{c\in U}\rho_c\) and \(b'=\sum_{c\in U\setminus R}\rho_c+\sum_{c\in V}q_c\). Require \(b'\leq1\) and either \(|U\setminus R|+|V|>|U|\), or \(|U\setminus R|+|V|=|U|\) and \(b'\leq b\). Require also \(q_c\sum_{A,U,R,V:c\in V}y_{A,U,R,V}>p\) for every \(c\in W'\). The allocation is balanced stably priceable (BSP) exactly when no such deviation exists.
Output prices and nonzero allocation masses as binary rationals, or report that no BSP allocation exists; blocking deviations may use real prices and submasses.
Is this exact BSP search problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicitly listed discrete voters and a fixed candidate price, BSP committees can be found in polynomial time, and whether a given committee is BSP can be verified in polynomial time. [Source](https://comsoc-community.org/assets/proceedings/comsoc-2021/PetersEtAl-2.pdf)
No result settling this exact mass formulation was located in the literature search.
Result. The exact BSP search problem is polynomial-time solvable in \(m,\tau,L\). A BSP allocation always exists, and the algorithm below produces one with exactly one nonzero allocation mass per approval type.
Here, “binary rationals” means rationals represented by binary-encoded numerators and denominators.
The construction uses the largest-demanding-group idea underlying the supplied discrete-voter result ([Theorem 7 and Appendix A.10](https://comsoc-community.org/assets/proceedings/comsoc-2021/PetersEtAl-2.pdf)). We give a direct proof for the stated mass formulation, including stability against real-valued deviations and polynomial bit complexity.
1. A characterization of blocking deviations
Fix any feasible allocation. For each cohort \((A,U)\), define its remaining budget and its maximum replaceable payment by
\(r_{A,U}=1-\sum_{d\in U}\rho_d,\qquad h_{A,U}=\max\bigl(\{r_{A,U}\}\cup\{\rho_d:d\in U\}\bigr).\)
For an unelected candidate \(c\) and a real price \(q\in(0,1]\), define
\(M_c(q)=\sum_{\substack{A,U:\ c\in A\\h_{A,U}\ge q}}x_{A,U}.\)
We claim that the allocation is BSP exactly when
\(qM_c(q)\le p\quad\text{for every }c\in C\setminus W\text{ and every real }q\in(0,1].\)
First, suppose this inequality fails for some \(c,q\). Every cohort counted in \(M_c(q)\) can buy \(c\):
Let all these cohorts participate in full. Their total payment to \(c\) is \(qM_c(q)>p\), so they form a blocking deviation.
Conversely, suppose an arbitrary blocking deviation exists. Choose a candidate \(c_*\in W'\) of minimum deviation price, and write \(q=q_{c_*}\). Since every deviation candidate receives strictly more than \(p>0\), all deviation prices are positive.
Consider a positive submass purchasing \(c_*\). Write \(k=|V|\) and \(\ell=|R|\). Then \(k\ge1\), and the utility requirement implies \(k\ge\ell\). Because every new candidate costs at least \(q\),
\(kq\le\sum_{d\in V}q_d.\)
If \(k=\ell\), the equal-utility payment condition gives
\(kq\le\sum_{d\in V}q_d\le\sum_{d\in R}\rho_d\le\ell h_{A,U}=kh_{A,U}.\)
If \(k>\ell\), the budget condition instead gives
\(kq\le\sum_{d\in V}q_d\le r_{A,U}+\sum_{d\in R}\rho_d\le(\ell+1)h_{A,U}\le kh_{A,U}.\)
Thus every submass purchasing \(c_*\) comes from a cohort satisfying \(h_{A,U}\ge q\). The submass constraints imply that its total purchasing mass is at most \(M_{c_*}(q)\). Consequently,
\(qM_{c_*}(q)\ge q\sum_{A,U,R,V:\ c_*\in V}y_{A,U,R,V}>p.\)
This proves the characterization, including for real prices and real submasses.
2. Computing a largest demanding group
Our algorithm maintains one bundle \(U_A\) and one remaining budget \(r_A\) for each approval type \(A\). Hence all members of a type always make identical purchases.
For an unelected candidate \(c\), call a collection of submasses \(s_A\in[0,\mu_A]\) a *demanding group* if its total mass \(M=\sum_A s_A\) is positive and
\(s_A>0\ \Longrightarrow\ c\in A\text{ and }r_A\ge p/M.\)
Such a group can fund \(c\) exactly by charging each participant \(p/M\).
A largest demanding group can always be chosen as a union of whole approval types. To see this, take any demanding group of mass \(M\) and put
\(H=\{A\in T:c\in A,\ r_A\ge p/M\},\qquad M_H=\sum_{A\in H}\mu_A.\)
Every participating type belongs to \(H\), so \(M_H\ge M\). Moreover, every type in \(H\) satisfies
\(r_A\ge p/M\ge p/M_H.\)
Thus taking every member of every type in \(H\) gives a demanding group of mass at least \(M\).
This observation also provides an efficient computation. Sort the types approving \(c\) as \(A_1,\ldots,A_s\), with
\(r_{A_1}\ge\cdots\ge r_{A_s},\qquad M_j=\sum_{i=1}^{j}\mu_{A_i}.\)
The entire prefix through \(A_j\) is demanding exactly when
\(r_{A_j}M_j\ge p.\)
The set \(H\) constructed above is one of these prefixes, including all types tied at its threshold. Therefore the largest feasible prefix has mass at least that of every demanding group, even one using arbitrary real submasses.
3. The algorithm and feasibility
Initialize \(W=\varnothing\), \(U_A=\varnothing\), and \(r_A=1\) for every \(A\in T\). Repeat the following steps:
Each iteration elects a new candidate, so there are at most \(m\) iterations.
The demanding-group condition guarantees \(r_A\ge\rho_c\) for every purchasing type. Thus remaining budgets stay nonnegative, and
\(r_A=1-\sum_{d\in U_A}\rho_d\)
holds throughout. Furthermore, \(0<\rho_c\le1\), since the purchasing types have remaining budgets at most \(1\).
At termination, output
\(x_{A,U_A}=\mu_A\)
for every type, with all other allocation masses zero. For each elected candidate, its purchasing types have exactly the mass \(M\) used when it was elected. Therefore its total payment is \(\rho_cM=p\). All feasibility conditions follow. Prices of unelected candidates may be set to zero if the output format requires them.
4. Proof of stability
For the final allocation, abbreviate
\(h_A=\max\bigl(\{r_A\}\cup\{\rho_d:d\in U_A\}\bigr).\)
By Section 1, it suffices to rule out an unelected candidate \(c\) and a real \(q\in(0,1]\) such that
\(q\sum_{\substack{A:\ c\in A\\h_A\ge q}}\mu_A>p.\)
Suppose such \(c,q\) exist. Let
\(S=\{A:c\in A,\ h_A\ge q\},\qquad M=\sum_{A\in S}\mu_A.\)
Then \(M>0\) and \(p/M<q\).
If no elected candidate has price at least \(q\), every type in \(S\) must have final remaining budget at least \(q\): all its purchased-candidate prices are strictly below \(q\). Hence \(S\) is a demanding group for \(c\) at termination, contradicting the stopping condition.
Otherwise, let \(t\) be the first iteration that elects a candidate at price at least \(q\). We show that every type in \(S\) had remaining budget at least \(q\) immediately before iteration \(t\).
If its final remaining budget is at least \(q\), this follows because remaining budgets only decrease. Otherwise, membership in \(S\) implies that it purchased some candidate \(d\) with \(\rho_d\ge q\). Candidate \(d\) was elected at iteration \(t\) or later. Immediately before purchasing \(d\), the type had remaining budget at least \(\rho_d\ge q\); therefore it also had remaining budget at least \(q\) before iteration \(t\).
Thus, before iteration \(t\), the whole group \(S\) could fund the still-unelected candidate \(c\) at price \(p/M<q\). Section 2 shows that the maximum demanding-group mass available then was at least \(M\). The greedy choice therefore charged
\(\rho_t\le p/M<q,\)
contradicting the definition of \(t\).
No violating \(c,q\) exist. The allocation is consequently BSP against all permitted real-valued deviations.
5. Exact arithmetic and polynomial running time
Write the input masses as \(\mu_A=n_A/d_A\), and write \(p=a/b\), using positive integer numerators and denominators. Define
\(D=\prod_{A\in T}d_A,\qquad w_A=D\mu_A.\)
The integers \(w_A\) are positive and satisfy \(\sum_Aw_A=D\). Since the denominator encodings are part of the input, \(D\) has \(O(L)\) bits.
Every selected group has mass \(S/D\), where \(S\) is an integer satisfying \(1\le S\le D\). Its price is therefore
\(\rho=\frac{aD}{bS},\)
whose numerator and denominator have \(O(L)\) bits.
After \(k\) selections with integer group weights \(S_1,\ldots,S_k\), every remaining budget can be represented with denominator
\(b\prod_{i=1}^{k}S_i.\)
Its numerator lies between zero and that denominator. Hence remaining budgets have \(O((m+1)L)\)-bit representations. Exact sorting, prefix feasibility checks, and budget updates consequently use only polynomial-length integer arithmetic.
Each iteration performs at most \(m\) sorts of at most \(\tau\) types and scans their prefixes. Including the final stopping check, the number of arithmetic operations and comparisons is
\(O\!\left(m^2\tau\log(\tau+1)\right).\)
Their bit costs are polynomial in \(m,L\). The output contains at most \(m\) prices and exactly \(\tau\) nonzero masses, each attached to a bundle of at most \(m\) candidates.
Thus the algorithm has polynomial bit running time and polynomial output length. It always returns a BSP allocation; the “no BSP allocation exists” outcome is unnecessary for this formulation.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned search problem. The argument is correct under its explicit interpretation of binary rationals as binary-encoded integer numerators and denominators. I found no major or minor issues requiring repair.
The construction addresses the stated formulation: committee size is unrestricted, voters are represented by approval-type masses, and blocking deviations may use real prices and real submasses. It outputs rational prices and exactly one nonzero allocation mass per approval type.
The cited [Theorem 7 and Appendix A.10](https://comsoc-community.org/assets/proceedings/comsoc-2021/PetersEtAl-2.pdf) concern the motivating discrete-voter construction. The prover supplies a direct argument for the mass formulation rather than assuming that the cited theorem automatically extends to it. There is therefore no unverified theorem application.
For a positive cohort, feasibility gives \(r_{A,U}\geq0\). If \(h_{A,U}\geq q\), the finite maximum defining \(h_{A,U}\) ensures that either \(r_{A,U}\geq q\), or some purchased candidate satisfies \(\rho_d\geq q\).
Both participation choices described in the proof satisfy the task:
In particular, because \(c\notin W\), it is not already in the purchased bundle. These choices respect approval restrictions and cohort submass bounds. With \(W'=\{c\}\), total revenue is exactly \(qM_c(q)>p\). Zero-mass cohorts contribute nothing and need no participation choice.
This direction is valid, including at equality in the affordability conditions.
Every deviation price is positive: a zero price cannot produce revenue strictly exceeding \(p>0\). Since \(W'\) is finite and nonempty, a minimum-price candidate \(c_*\) exists.
For a positive submass purchasing \(c_*\), the proof correctly uses \(k=|V|\geq1\) and the utility condition \(k\geq\ell=|R|\). The two cases exhaust the permitted utility outcomes.
In the equal-utility case, the payment requirement gives
\(kq\leq\sum_{d\in V}q_d\leq\sum_{d\in R}\rho_d\leq kh_{A,U}\).
In the strictly increased utility case, the budget requirement gives
\(kq\leq r_{A,U}+\sum_{d\in R}\rho_d\leq(\ell+1)h_{A,U}\leq kh_{A,U}\).
The final inequality is justified by the integer relation \(k>\ell\).
Dividing by \(k>0\) establishes \(h_{A,U}\geq q\). Summing the submass constraints bounds the total mass purchasing \(c_*\) by \(M_{c_*}(q)\), even when a cohort splits among several participation choices. Its strictly excessive revenue therefore yields \(qM_{c_*}(q)>p\).
The characterization is proved for all permitted deviations; it does not assume rational deviation prices or submasses.
The whole-type enlargement argument is correct. Every participating type belongs to the defined set \(H\), so \(M_H\geq M>0\). Consequently, every type in \(H\) can afford \(p/M_H\), and taking its full mass remains feasible.
After sorting approving types by remaining budget, a prefix is demanding exactly when its least remaining budget satisfies \(r_{A_j}M_j\geq p\). The threshold set \(H\) is a prefix containing all types tied at its threshold. Thus every demanding group, including one using real fractional submasses, is dominated in mass by a feasible prefix.
The algorithm scans all prefixes. It does not incorrectly assume that prefix feasibility is monotone. Arbitrary ordering within budget ties does not invalidate the argument, since the prefix containing the entire threshold tie remains among those scanned.
The claimed maximum-mass group is therefore computable from the support without enumerating individuals or subsets of types.
Each iteration elects a previously unelected candidate, giving at most \(m\) iterations. The selected prefix guarantees that every purchasing type can afford the assigned price. Remaining budgets stay nonnegative, and the stated remaining-budget identity is preserved.
The bounds \(0<\rho_c\leq1\) follow from \(p>0\), positive group mass, and affordability by types whose remaining budgets are at most \(1\).
Later iterations only add purchases of other candidates. They do not change which types purchased an earlier candidate. Its final purchasing mass therefore remains exactly the mass used to set its price, establishing \(\rho_cM=p\).
The output masses sum to \(\mu_A\) for each type, and the resulting bundles satisfy both approval and budget constraints. Assigning zero prices to unelected candidates, if required, is permitted.
The contradiction argument correctly uses the blocking characterization. A violating pair \(c,q\) defines a positive-mass group \(S\) with \(p/M<q\).
If every elected price is below \(q\), membership in \(S\) forces final remaining budget at least \(q\). The group is consequently demanding at termination, contradicting the stopping condition.
Otherwise, the first iteration \(t\) with elected price at least \(q\) is well defined. For every type in \(S\), the asserted pre-iteration budget bound is justified:
Candidate \(c\) remains unelected throughout because it is absent from the final committee. Thus \(S\) was an available demanding group for \(c\) immediately before iteration \(t\). The maximum-mass property proved in Section 2 implies that the greedy group selected then had mass at least \(M\), and hence price at most \(p/M<q\). This contradicts the definition of \(t\).
The argument neither assumes monotonicity of elected prices nor restricts deviations to single candidates. Stability against arbitrary permitted deviations follows from the established characterization.
The denominator product \(D\) has \(O(L)\) bits because its logarithm is bounded by the total input denominator encoding length. Each \(w_A=D\mu_A\) is an integer, and normalization gives \(\sum_Aw_A=D\).
Every selected group weight satisfies \(1\leq S\leq D\). Therefore the displayed price \(aD/(bS)\) has \(O(L)\)-bit numerator and denominator.
The proposed remaining-budget denominator \(b\prod_{i=1}^{k}S_i\) is a valid common denominator for the prices selected through iteration \(k\). Nonnegative remaining budgets at most \(1\) justify the numerator bound. Both numerator and denominator consequently have \(O((m+1)L)\) bits.
Exact comparisons, prefix checks, and updates therefore operate on polynomial-length integers. The claimed arithmetic-operation count \(O(m^2\tau\log(\tau+1))\) accounts for all candidate sorts and scans, including termination. Recording the bundles and output masses also requires only polynomial space and output length.
The algorithm uses the listed support size \(\tau\); it does not expand the population or enumerate all possible approval types.
The argument accommodates empty approval types, candidates with no approvers, empty purchased bundles, and termination with an empty committee. When all candidates are elected, there is no admissible nonempty deviation committee. Equality in affordability is allowed, whereas blocking requires strictly excessive revenue; the proof consistently preserves this distinction.
No additional lemma, computation, or clarification is needed to verify the stated conclusion. The algorithm establishes polynomial-time solvability and existence for every valid input under the explicitly stated rational encoding.
⟨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.