Answer: A deterministic polynomial-time \((1-1/e)\)-approximation exists; it achieves the stronger guarantee \(1-(1-1/K)^K\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm~GM is an $(1 - 1/e)$-approximation algorithm for the Monroe'e election problem for arbitrary positional scoring functions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) alternatives, committee size \(K\), a positional scoring vector \(\alpha\), and \(\tau\) complete rankings with positive rational masses \(\mu_t\) summing to \(1\), compute a \(K\)-alternative committee \(W\) and a feasible assignment \(x_{t,a}\ge 0\) satisfying \(\sum_{a\in W}x_{t,a}=\mu_t\) for every type \(t\) and \(\sum_t x_{t,a}=1/K\) for every \(a\in W\), whose score \(\sum_t\sum_{a\in W}x_{t,a}\alpha(\operatorname{pos}_t(a))\) is at least \((1-1/e)\) times the optimum.
Let \(A\) contain \(m\geq 1\) alternatives, and let \(1\leq K\leq m\) be an integer. The input scoring vector consists of binary integers \(\alpha_1\geq\cdots\geq\alpha_m=0\).
A society is given by its support: a list of \(\tau\) distinct strict complete rankings, each with positive binary rational mass \(\mu_t\), 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; state running times in \(m,\tau,K,L\).
Write \(\operatorname{pos}_t(a)\) for the position of \(a\) in ranking \(t\), with position \(1\) best. A feasible solution consists of a set \(W\subseteq A\), \(|W|=K\), and divisible assignments \(x_{t,a}\geq0\) satisfying \(\sum_{a\in W}x_{t,a}=\mu_t\) for every type and \(\sum_t x_{t,a}=1/K\) for every selected alternative.
Its score is \(S(W,x)=\sum_t\sum_{a\in W}x_{t,a}\alpha_{\operatorname{pos}_t(a)}\). Let \(\mathrm{OPT}\) be the maximum score over all feasible committees and real assignments. Any committee meeting the requested guarantee is acceptable, without tie-breaking.
Does this problem admit an algorithm running in time polynomial in \(m,\tau,K,L\) that returns a feasible committee and rational assignment with \(S(W,x)\geq(1-1/e)\mathrm{OPT}\), or is achieving this approximation guarantee NP-hard?
Discrete Monroe has a polynomial-time \((1-1/e)\)-approximation for arbitrary positional scoring vectors ([Skowron, Faliszewski, and Slinko](https://aamas.csc.liv.ac.uk/Proceedings/aamas2013/docs/p399.pdf)); the extended treatment assumes the committee size divides the number of voters ([extended version](https://arxiv.org/pdf/1312.4026)).
No result settling this guarantee for the exact model above with binary rational masses was located in the literature search.
Result. The problem admits a deterministic polynomial-time algorithm. In fact, it returns a feasible rational assignment with score at least
\(\displaystyle \left[1-\left(1-\frac1K\right)^K\right]\mathrm{OPT}\ \geq\ (1-1/e)\mathrm{OPT}.\)
The algorithm uses the greedy selection idea of Algorithm GM in the [extended treatment](https://arxiv.org/pdf/1312.4026), but computes assignments directly on the listed types. The proof below establishes both the guarantee and polynomial running time for binary rational masses.
1. Partial-assignment value.
Write \(w_{t,a}=\alpha_{\operatorname{pos}_t(a)}\). The scoring-vector assumptions imply \(w_{t,a}\geq0\).
For every \(S\subseteq A\), define
\(\displaystyle f(S)=\max_y\sum_{t=1}^{\tau}\sum_{a\in S}w_{t,a}y_{t,a},\)
subject to
\(\displaystyle y_{t,a}\geq0,\qquad \sum_{a\in S}y_{t,a}\leq\mu_t,\qquad \sum_{t=1}^{\tau}y_{t,a}\leq\frac1K.\)
Thus \(f\) permits unassigned mass and unused candidate capacity. This definition applies to all subsets, including those larger than \(K\). Its feasible region is nonempty and compact, so its maximum exists. Also, \(f(\varnothing)=0\), and enlarging \(S\) preserves every previously feasible assignment. Hence \(f\) is monotone.
For \(|S|=K\), we claim that \(f(S)\) equals the optimum under the required equality constraints.
To prove this, take an optimal partial assignment \(y\) and define residuals
\(\displaystyle r_t=\mu_t-\sum_{a\in S}y_{t,a},\qquad d_a=\frac1K-\sum_t y_{t,a}.\)
They are nonnegative, and
\(\displaystyle \sum_t r_t=1-\sum_{t,a}y_{t,a}=\sum_{a\in S}d_a.\)
Whenever this common residual total is positive, choose a type and candidate with positive residuals and increase their assignment by \(\min\{r_t,d_a\}\). Each step eliminates at least one positive residual. After at most \(\tau+K\) steps, all equalities hold.
Because all scores are nonnegative, completion cannot decrease the score. Conversely, every complete assignment is feasible for the partial problem. The completed assignment therefore has score exactly \(f(S)\). In particular,
\(\displaystyle \mathrm{OPT}=\max_{|S|=K}f(S).\)
2. Exact computation on the compressed input.
Write each input mass as \(\mu_t=p_t/d_t\), with positive integers \(p_t,d_t\), and set
\(\displaystyle N=K\prod_{t=1}^{\tau}d_t,\qquad b_t=N\mu_t,\qquad q=N/K.\)
All \(b_t\) and \(q\) are integers, and \(\sum_t b_t=N\). Crucially,
\(\displaystyle \log N=O(L+\log(K+1)).\)
The integer \(N\) may be exponentially large, but its binary representation has polynomial length.
For a given \(S\), construct a directed network with source \(s\), sink \(h\), one vertex per type, and one vertex per candidate in \(S\). Its arcs, capacities, and costs are:
| Arc | Capacity | Cost |
|---|---:|---:|
| \(s\to t\) | \(b_t\) | \(0\) |
| \(t\to a\), for \(a\in S\) | \(b_t\) | \(-w_{t,a}\) |
| \(a\to h\) | \(q\) | \(0\) |
| \(h\to s\) | \(N\) | \(0\) |
A feasible circulation induces the partial assignment \(y_{t,a}=z_{t,a}/N\), where \(z_{t,a}\) is its flow on \(t\to a\). Conversely, a feasible partial assignment induces a circulation by setting these flows to \(Ny_{t,a}\), setting the other forward flows to the corresponding sums, and returning the total flow on \(h\to s\). The return-arc capacity is respected because total assigned mass is at most one.
Consequently,
\(\displaystyle \min\{\text{circulation cost}\}=-Nf(S).\)
We use the standard minimum-cost circulation theorem: a finite network with integer capacities and costs can be optimized exactly in time polynomial in its network encoding length, and an integral optimal circulation can be returned. Polynomial-time optimization is provided, for example, by [Orlin’s minimum-cost flow algorithm](https://pubsonline.informs.org/doi/pdf/10.1287/opre.41.2.338). Here all capacities and costs are integers, the zero circulation is feasible, and finite capacities make the feasible region bounded.
For completeness, the integrality assertion also follows directly. In a nonintegral feasible circulation with integer capacities, consider the arcs whose flows are noninteger. No vertex can be incident to exactly one such arc: conservation would then equate a noninteger quantity with an integer. Thus, if any such arcs exist, their underlying undirected multigraph contains a cycle. Perturb flow around that cycle, using signs that preserve conservation. Choose one of the two directions whose cost change is nonpositive, and continue until a cycle arc reaches its next integer value. All perturbed flows remain within their adjacent integer bounds, so feasibility is preserved, no integral arc becomes nonintegral, and at least one additional arc becomes integral. Starting from an optimum, the cost cannot strictly improve, so this procedure preserves optimality and eventually yields an integral optimum.
Thus the oracle returns both \(f(S)\) exactly and an optimal rational partial assignment whose coordinates have denominator \(N\).
3. Submodularity: a matching lemma.
We first prove a finite matching statement.
Let a weighted bipartite graph have fixed left vertex set and right vertex set \(R\). For \(B\subseteq R\), let \(H(B)\) be the maximum weight of a matching using only right vertices in \(B\); unmatched vertices are allowed. Then
\(\displaystyle H(P)+H(Q)\geq H(P\cup Q)+H(P\cap Q)\)
for all \(P,Q\subseteq R\).
Proof. Choose optimal matchings \(M_U\) for \(P\cup Q\) and \(M_I\) for \(P\cap Q\). Superimpose them, retaining two copies of any common edge.
Every vertex has degree at most two, and at every degree-two vertex one incident edge comes from each matching. Hence each nontrivial component is a path or an even cycle, with the two original matching labels alternating.
A right vertex in \(P\setminus Q\) or \(Q\setminus P\), if incident to an edge, is a path endpoint whose edge belongs to \(M_U\). A component cannot contain two such endpoints. Indeed, they would both be right vertices, forcing an even path length; but an alternating path whose first and last edges both belong to \(M_U\) has odd length.
Now recolor edges alternately red and blue in every component. If a component contains an endpoint in \(P\setminus Q\), require its incident edge to be red. If it contains an endpoint in \(Q\setminus P\), require its incident edge to be blue. There is at most one such requirement per component, so the coloring exists.
The red edges form a matching using only right vertices in \(P\), and the blue edges form one using only right vertices in \(Q\). Together they retain every edge, with multiplicity, of \(M_U\) and \(M_I\). Their combined weight is therefore \(H(P\cup Q)+H(P\cap Q)\), proving the inequality. \(\square\)
4. Submodularity for rational masses.
Use \(N,b_t,q\) from Section 2 to define a conceptual bipartite graph:
Let \(C(S)\) contain all right copies of candidates in \(S\). We claim
\(\displaystyle H(C(S))=Nf(S).\)
A matching gives integer assignment counts satisfying row bounds \(b_t\) and column bounds \(q\), so dividing these counts by \(N\) gives a feasible partial assignment.
Conversely, Section 2 supplies an optimal partial assignment whose scaled counts are integers. These counts can be realized by a matching: allocate distinct left copies within each type and distinct right copies within each candidate according to the counts. The row and column bounds ensure enough copies exist. The resulting matching has weight \(Nf(S)\). This proves the claim.
The candidate-copy groups are disjoint, so
\(\displaystyle C(S\cup T)=C(S)\cup C(T),\qquad C(S\cap T)=C(S)\cap C(T).\)
Applying the matching lemma and dividing by \(N\) yields
\(\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T).\)
Thus \(f\) is submodular. In particular, for \(S\subseteq T\) and \(a\notin T\), applying this inequality to \(S\cup\{a\}\) and \(T\) gives diminishing returns:
\(\displaystyle f(S\cup\{a\})-f(S)\geq f(T\cup\{a\})-f(T).\)
The expanded graph is used only for this proof; the algorithm never constructs it.
5. Greedy algorithm and approximation proof.
Start with \(S_0=\varnothing\). For \(i=0,\ldots,K-1\), choose any
\(\displaystyle a_i\in\operatorname*{arg\,max}_{a\in A\setminus S_i}f(S_i\cup\{a\}),\)
and set \(S_{i+1}=S_i\cup\{a_i\}\). Every comparison uses the exact oracle from Section 2.
Let \(O\) be an optimal size-\(K\) committee and let
\(\displaystyle \Delta_i=f(S_{i+1})-f(S_i).\)
Monotonicity gives \(f(O)\leq f(S_i\cup O)\). Add the candidates of \(O\setminus S_i\) one at a time. Diminishing returns bounds each successive gain by its gain when added directly to \(S_i\). Greedy selection bounds that gain by \(\Delta_i\). Therefore
\(\displaystyle \mathrm{OPT}\leq f(S_i\cup O)\leq f(S_i)+\sum_{a\in O\setminus S_i}\bigl(f(S_i\cup\{a\})-f(S_i)\bigr)\leq f(S_i)+K\Delta_i.\)
Rearranging,
\(\displaystyle \mathrm{OPT}-f(S_{i+1})\leq\left(1-\frac1K\right)\bigl(\mathrm{OPT}-f(S_i)\bigr).\)
Starting from \(f(S_0)=0\) and applying this recurrence \(K\) times gives
\(\displaystyle f(S_K)\geq\left[1-\left(1-\frac1K\right)^K\right]\mathrm{OPT}.\)
For \(K=1\), this is exact optimization. For \(K>1\), the inequality \(\log(1-u)\leq-u\), applied at \(u=1/K\), gives
\(\displaystyle \left(1-\frac1K\right)^K\leq e^{-1}.\)
Finally, return \(W=S_K\), compute its optimal partial assignment, and complete it as in Section 1. Its score equals \(f(S_K)\), so it satisfies the requested guarantee.
6. Running time and output size.
There are at most \(Km\) oracle calls, plus at most one final assignment computation. Every queried set has size at most \(K\). Its flow network has at most
\(\displaystyle V=\tau+K+2,\qquad E=\tau K+\tau+K+1\)
vertices and arcs, respectively. Each capacity and cost has \(O(L+\log(K+1))\) bits. Hence an exact oracle call takes
\(\displaystyle \operatorname{poly}\!\left(\tau K,L+\log(K+1)\right)\)
bit operations, with a fixed polynomial independent of the input.
Including preprocessing, exact comparisons, and output construction, the total running time is
\(\displaystyle O(m\tau L)+\operatorname{poly}(L)+O(Km+1)\operatorname{poly}\!\left(\tau K,L+\log(K+1)\right),\)
which is polynomial in \(m,\tau,K,L\). There is no dependence on the numerical magnitude of \(N\).
The final completion can be performed with integer residual counts before division by \(N\). Consequently, every output coordinate remains a multiple of \(1/N\), with numerator at most \(N\). The rational assignment therefore has total encoding length \(O(\tau K(L+\log(K+1)))\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The argument establishes a deterministic polynomial-time algorithm for the specified binary rational input model, with approximation ratio \(1-(1-1/K)^K\). I found no major or minor mathematical gaps.
The definition of \(f(S)\) is well posed for every \(S\subseteq A\), including the empty set and sets larger than \(K\). Its feasible region is nonempty, closed, and bounded. Nonnegativity of the weights follows from \(\alpha_1\geq\cdots\geq\alpha_m=0\).
The claims \(f(\varnothing)=0\) and monotonicity are correct: adding candidates preserves an existing assignment by assigning zero to the added candidates.
For \(|S|=K\), the residual identity is correct:
\[
\sum_t r_t=1-\sum_{t,a}y_{t,a}=\sum_{a\in S}d_a.
\]
The last equality uses exactly \(|S|/K=1\).
The completion procedure preserves all upper bounds and eliminates at least one positive residual at each step. Equal residual totals ensure that a positive residual on either side has a positive counterpart. Thus the stated bound of at most \(\tau+K\) steps is valid.
Completion cannot decrease the score because every weight is nonnegative. It also cannot increase the score beyond \(f(S)\), because the completed assignment remains feasible for the partial problem. Consequently, the completed score equals \(f(S)\), and the identification
\[
\mathrm{OPT}=\max_{|S|=K}f(S)
\]
is justified.
Assessment: Correct, with no missing feasibility or optimality step.
The scaling quantities \(N\), \(b_t\), and \(q\) are integers with the stated properties. In particular, multiplication of the input denominators increases binary length additively, so
\[
\log N=O(L+\log(K+1))
\]
is valid. Reduction of the input fractions to lowest terms is unnecessary.
The circulation correspondence is correct in both directions:
The type-to-candidate capacity \(b_t\) introduces no additional restriction: each individual assignment is already bounded by the corresponding type’s total mass.
Only type-to-candidate arcs contribute to cost, giving exactly
\[
\min\{\text{circulation cost}\}=-Nf(S).
\]
The stated minimum-cost circulation theorem applies: the network has integer capacities and costs, zero circulation is feasible, and all capacities are finite. Negative costs cause no unboundedness here. The cited [Orlin paper](https://pubsonline.informs.org/doi/abs/10.1287/opre.41.2.338) supplies polynomial-time optimization for capacitated minimum-cost flow, consistent with the theorem invoked.
The additional integrality argument is sound. Conservation excludes a vertex incident to exactly one noninteger-flow arc. The resulting undirected multigraph therefore contains a cycle whenever any noninteger arcs remain. The described signed perturbation preserves conservation, and stopping at the first adjacent integer boundary preserves capacity bounds. It makes at least one additional arc integral without changing any previously integral arc. Starting from an optimum, a nonpositive cost change must actually preserve the optimal cost.
This establishes an integral optimal circulation and hence an optimal partial assignment with coordinates that are multiples of \(1/N\).
Assessment: Correct theorem application, correspondence, and integrality argument.
The matching lemma is proved correctly.
Retaining two copies of a common edge is necessary and handled explicitly. The superimposed multigraph has maximum degree two, and labels alternate at every degree-two vertex. Its nontrivial components are consequently paths or even cycles; duplicated common edges form valid two-edge cycles.
An incident right vertex outside \(P\cap Q\) cannot have an edge from \(M_I\). It is therefore a path endpoint whose edge belongs to \(M_U\).
The argument excluding two such endpoints in one component is valid. Two right endpoints require an even number of edges, whereas an alternating path beginning and ending with \(M_U\) edges requires an odd number.
The coloring requirements are therefore compatible. Alternating colors produce two matchings, and the endpoint requirements put every used exclusive right vertex into its permitted matching. Right vertices in the intersection permit either color. Preservation of all edges with multiplicity gives the claimed combined weight.
Unmatched vertices are allowed throughout, as required by the lemma’s statement.
Assessment: Correct; the parity argument and duplicated-edge case do not conceal a gap.
The expanded graph is finite, although potentially exponentially large. Its use is confined to the proof, so its size does not invalidate the algorithm’s running time.
Both directions of
\[
H(C(S))=Nf(S)
\]
are justified as written. A matching yields feasible assignment counts. Conversely, the integral optimum from Section 2 provides counts that can be realized by allocating distinct copies within each type and each candidate. Completeness of the corresponding copy-to-copy edges ensures that these allocations give a matching with the specified weights.
Disjoint candidate-copy groups preserve unions and intersections exactly. Applying the matching lemma therefore establishes submodularity of \(f\) on all subsets of \(A\).
The stated diminishing-returns inequality follows from precisely the two sets identified in the output, with the required hypotheses \(S\subseteq T\) and \(a\notin T\).
Assessment: Correct. There is no computational reliance on constructing the expanded graph.
At every iteration, an unselected candidate exists because \(i<K\leq m\). Maximizing the displayed value is equivalent to maximizing marginal gain, since \(f(S_i)\) is common to all choices.
The comparison against an optimal committee is valid:
The resulting recurrence and its \(K\)-fold application give the claimed ratio. The logarithmic inequality is applied only for \(K>1\), where its argument lies in its valid domain. The separate treatment of \(K=1\) correctly gives exact optimization.
Returning the completed optimal partial assignment preserves the established score, by Section 1.
The argument also covers \(K=m\), \(m=1\), and an identically zero scoring vector. No step divides by \(\mathrm{OPT}\), so \(\mathrm{OPT}=0\) presents no exception.
Assessment: Correct approximation proof and edge-case coverage.
The oracle-call bound and network-size bounds are correct. Capacities and costs have polynomial binary length, and the integer circulation cost also has polynomial binary length. Exact comparisons therefore do not introduce a numerical-magnitude dependence.
The stated oracle bound is polynomial in the network encoding length. Its abbreviated dependence on \(\tau K\) is sufficient because \(\tau,K\geq1\), so the vertex and arc counts are both bounded polynomially in \(\tau K\).
The total running-time expression is a valid polynomial bound in \(m,\tau,K,L\). It does not require enumerating the \(N\) conceptual copies.
The final completion uses integer residual counts, preserving denominator \(N\). Each assignment numerator is at most \(N\), so the stated output-length bound is valid.
The instruction to choose any maximizer permits deterministic selection in input order. Since every maximizing choice satisfies the proof and the task requires no tie-breaking, this creates no substantive ambiguity.
Assessment: Correct polynomial bit complexity and rational output guarantee.
No repair or additional lemma is needed. The output establishes the algorithmic alternative requested by USER_TASK; it does not merely transfer a result from an explicitly expanded discrete electorate.
⟨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.