Answer: Polynomial-time solvable: \(\mathrm{P}\), with running time \((\tau m L)^{O(1)}\) bit operations.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDetermining if there exists a constructive manipulation of a round robin competition is polynomial if the normalized scoring model is of the form S = {(i, n −i) | 0 ≤i ≤n} and NP-complete, otherwise.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_t\) over finitely many opponent types, a finite score set \(S\), balanced baseline matchup profiles, and a distinguished target's baseline profile against each type, determine whether mass transfers \(x_{tu}(r,s)\) among type-pair games and \(z_t(r,s)\) in target-versus-type games obeying the paper's per-game manipulation restrictions admit a balanced realization in which the target's limiting score per opponent is at least the common per-capita score of every opponent type.
A society is given by its support: \(\tau\geq1\) opponent types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. Each type has a coalition-membership flag, as does a distinguished target of zero mass. Let \(S\subseteq\mathbb Q_{\geq0}^2\) be a nonempty explicitly listed scoring model closed under coordinate reversal; write \(m=|S|\), \(r^*=(r_2,r_1)\), and let \(L\) be the total input bit length.
For every ordered type pair, the input gives nonnegative rational baseline game masses \(B_{tu}(r)\), satisfying \(\sum_{r\in S}B_{tu}(r)=\mu_t\mu_u\) and \(B_{ut}(r^*)=B_{tu}(r)\), including \(t=u\). Target-versus-type baseline masses \(D_t(r)\), oriented with the target first, satisfy \(\sum_rD_t(r)=\mu_t\).
A transition from baseline outcome \(r\) to outcome \(s\in S\) is allowed as follows: with neither endpoint in the coalition, only \(s=r\); with both endpoints in the coalition, any \(s\); with only the first endpoint in the coalition, \(s_1\leq r_1\) and \(s_2\geq r_2\); with only the second, reverse these inequalities. Unchanged outcomes are always allowed.
Choose nonnegative real transfer masses \(x_{tu}(r,s)\) and \(z_t(r,s)\), zero on forbidden transitions, with \(\sum_sx_{tu}(r,s)=B_{tu}(r)\), \(x_{ut}(r^*,s^*)=x_{tu}(r,s)\), and \(\sum_sz_t(r,s)=D_t(r)\). Define \(Q_{tu}(s)=\sum_rx_{tu}(r,s)\) and \(H_t(s)=\sum_rz_t(r,s)\).
A realization consists of disjoint atomless intervals \(I_t\) of lengths \(\mu_t\), measurable baseline and final outcomes for each opponent pair, reversed when its endpoints are exchanged, and measurable baseline and final outcomes for each target game. Their joint outcome masses on \(I_t\times I_u\) and \(I_t\) must respectively equal \(x_{tu}(r,s)\) and \(z_t(r,s)\); self-games on the measure-zero diagonal are omitted.
Balanced means that, for almost every opponent in \(I_t\), its baseline and final outcome masses against \(I_u\) equal \(B_{tu}(r)/\mu_t\) and \(Q_{tu}(s)/\mu_t\), respectively. Inputs are promised to admit a balanced baseline realization; its microscopic arrangement is not fixed.
The target's limiting score per opponent is \(a_0=\sum_{t,s}s_1H_t(s)\); every member of type \(t\) has limiting score \(a_t=\mu_t^{-1}\sum_{u,s}s_1Q_{tu}(s)\). The single target game contributes zero to an opponent's limiting score. Ties count as winning, so feasibility requires \(a_0\geq a_t\) for every supported type.
Is deciding whether such transfers admit a balanced realization with \(a_0\geq a_t\) for all \(t\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\).
Discrete constructive round-robin manipulation is NP-complete for general scoring models, while Copeland and chess scoring admit polynomial-time algorithms ([Russell–Walsh](https://www.cse.unsw.edu.au/~twalsh/rwadt09.pdf)). No result settling this exact continuous problem was identified in the search.
The decision problem is in \(\mathrm P\) for every explicitly listed scoring model satisfying the stated hypotheses. Its running time is \((\tau m L)^{O(1)}\) bit operations.
The essential point is that every admissible transfer table has a balanced realization. Thus balance imposes no additional constraints beyond the finite linear equations in the question. The proof includes games within a single type.
Write \(C=S\times S\). A label \(c=(r,s)\in C\) specifies a game's baseline and final outcomes. Define its reversal by \(c^*=(r^*,s^*)\).
Call a transfer table admissible if it satisfies nonnegativity, the forbidden-transition restrictions, the baseline marginal equations, and reversal symmetry. No winning inequalities are required in this definition.
Lemma. Every admissible transfer table \(x,z\) has a measurable realization such that, for every type \(t\), almost every player \(v\in I_t\), every type \(u\), and every label \((r,s)\), the mass of players in \(I_u\) giving that joint label against \(v\) is
\[ \frac{x_{tu}(r,s)}{\mu_t}. \]
In particular, the realization is balanced in both its baseline and final outcomes.
Choose disjoint half-open intervals \(I_t\) of lengths \(\mu_t\). Identify each interval with \([0,1)\) by an affine coordinate \(\theta_t\). Under this identification, physical Lebesgue measure on \(I_t\) is \(\mu_t\) times Lebesgue measure on \([0,1)\).
Exchanging endpoints preserves admissibility after reversing both outcomes. Indeed, the cases with neither or both endpoints in the coalition are invariant under reversal, while the two cases with exactly one coalition endpoint are exchanged.
Fix \(t<u\), and define the probability distribution
\[ p_{tu}(r,s)=\frac{x_{tu}(r,s)}{\mu_t\mu_u}. \]
Its entries sum to one because the transfer marginal equations give
\[ \sum_{r,s}x_{tu}(r,s)=\sum_r B_{tu}(r)=\mu_t\mu_u. \]
Partition \([0,1)\) measurably into intervals labeled by \((r,s)\), with lengths \(p_{tu}(r,s)\). Zero-length intervals can be omitted. Let \(F_{tu}\) be the resulting label function.
For players with coordinates \(a\in[0,1)\) in type \(t\) and \(b\in[0,1)\) in type \(u\), assign the label
\[ F_{tu}\bigl((b-a)\bmod 1\bigr). \]
For the opposite ordering of the same players, assign its reversed label.
For fixed \(a\), the map \(b\mapsto(b-a)\bmod1\) preserves Lebesgue measure. Consequently, the physical mass of partners in \(I_u\) with label \((r,s)\) is
\[ \mu_u p_{tu}(r,s)=\frac{x_{tu}(r,s)}{\mu_t}. \]
For fixed \(b\), the map \(a\mapsto(b-a)\bmod1\) also preserves Lebesgue measure. The corresponding reverse-oriented section therefore has mass
\[ \mu_t p_{tu}(r,s) =\frac{x_{tu}(r,s)}{\mu_u} =\frac{x_{ut}(r^*,s^*)}{\mu_u}. \]
Integrating the sections gives exactly the prescribed joint masses on both ordered blocks.
Fix \(t\), and put
\[ p_t(c)=\frac{x_{tt}(c)}{\mu_t^2}. \]
Then \(\sum_c p_t(c)=1\), and reversal symmetry gives \(p_t(c)=p_t(c^*)\).
Partition the labels into orbits of the involution \(c\mapsto c^*\). An orbit is either a singleton or a pair.
Construct a measurable label function \(F_t\) first on \((0,\tfrac12)\):
These lengths sum to one half, since
\[ \sum_{\text{two-element orbit representatives }c}p_t(c) +\frac12\sum_{c=c^*}p_t(c) =\frac12\sum_{c\in C}p_t(c) =\frac12. \]
Extend the function to \((\tfrac12,1)\) by requiring
\[ F_t(d)=F_t(1-d)^*. \]
Interval endpoints can be assigned any admissible label, with their reflected endpoints assigned the reversed label. This preserves the displayed identity and does not affect any label's measure.
A two-element orbit then contributes measure \(p_t(c)\) to each of its labels. A singleton contributes measure \(p_t(c)/2\) in each half. Thus every label \(c\) has total measure \(p_t(c)\).
For distinct players with coordinates \(a,b\), provided \((b-a)\bmod1\ne\tfrac12\), assign the label
\[ F_t\bigl((b-a)\bmod1\bigr). \]
Reversal holds because exchanging the players changes a nonzero circle difference \(d\) into \(1-d\).
There remains the exceptional case of antipodal players, whose circle difference is \(\tfrac12\). Choose any \(r\in S\), and let \(c_0=(r,r)\). This unchanged transition is always admissible. For an antipodal pair, assign \(c_0\) when \(a<b\), and \(c_0^*\) when \(a>b\). Reversal now holds for these pairs as well. The diagonal is omitted as stipulated.
The antipodal set has two-dimensional measure zero, and its section at any fixed player contains only one partner. Hence this assignment changes neither joint masses nor section masses.
For every fixed player, circle translation preserves measure. Its physical mass of partners with label \(c\) is therefore
\[ \mu_t p_t(c)=\frac{x_{tt}(c)}{\mu_t}. \]
This proves the required assertion for self-type blocks.
For each type \(t\), partition \(I_t\) into measurable intervals labeled by \((r,s)\), with lengths \(z_t(r,s)\). Such a partition exists because
\[ \sum_{r,s}z_t(r,s)=\sum_r D_t(r)=\mu_t. \]
Assign the target game's baseline and final outcomes according to these labels, oriented with the target first.
All constructed functions are measurable. Positive-measure labels are admissible, and any exceptional assignments use admissible unchanged transitions.
Finally, summing the opponent section masses over final outcomes gives the baseline section mass
\[ \sum_s\frac{x_{tu}(r,s)}{\mu_t} =\frac{B_{tu}(r)}{\mu_t}, \]
while summing over baseline outcomes gives the final section mass
\[ \sum_r\frac{x_{tu}(r,s)}{\mu_t} =\frac{Q_{tu}(s)}{\mu_t}. \]
Thus the realization is balanced. This completes the proof of the lemma.
Use variables \(x_{tu}(r,s)\) and \(z_t(r,s)\), and impose the following rational linear constraints:
\[ \sum_s x_{tu}(r,s)=B_{tu}(r). \]
\[ x_{ut}(r^*,s^*)=x_{tu}(r,s). \]
\[ \sum_s z_t(r,s)=D_t(r). \]
\[ \mu_t\sum_{v=1}^{\tau}\sum_{r,s\in S}s_1z_v(r,s) \ \geq\ \sum_{u=1}^{\tau}\sum_{r,s\in S}s_1x_{tu}(r,s). \]
The last constraint is exactly \(a_0\geq a_t\). To see this, substitute the definitions of \(H_v\) and \(Q_{tu}\), then multiply the desired score comparison by the strictly positive mass \(\mu_t\). This multiplication preserves the inequality.
Equivalence. The original instance is feasible if and only if this linear program is feasible.
For necessity, any feasible realization supplies transfers satisfying constraints 1–5, and its winning score comparisons give constraint 6.
For sufficiency, a feasible LP solution is an admissible transfer table. The lemma constructs its balanced realization. Its target score is the left-hand score expression, and every opponent of type \(t\), except possibly on a null set, has score
\[ \frac1{\mu_t}\sum_{u,r,s}s_1x_{tu}(r,s). \]
Constraint 6 therefore ensures that the target ties or beats every supported type, exactly as required.
Let
\[ N=(\tau^2+\tau)m^2. \]
The formulation has exactly \(N\) variables before eliminating forbidden transitions, and \(O(N)\) linear constraints. This includes nonnegativity, forbidden-transition equations, marginal equations, reversal equations, and the \(\tau\) winning inequalities.
Reversal indices and allowed transitions can be computed using \(O(\tau^2m^2)\) rational comparisons and arithmetic operations. Every coefficient and right-hand side has \(O(L)\) bits: coefficients are input rationals, signs, or products \(\mu_t s_1\), whose encoding lengths grow only by a constant factor.
Thus:
Applying that theorem gives total decision time
\[ \operatorname{poly}(\tau^2m^2,L) =(\tau m L)^{O(1)} \]
bit operations. This is a bit-polynomial bound; no strongly polynomial bound is claimed.
When feasible, exact LP algorithms can also return rational transfers of polynomial encoding length. The realization above then has a polynomial-size description using rational interval endpoints and circle-difference formulas.
The construction uses the stated freedom to choose the microscopic baseline arrangement. It realizes even the joint baseline/final transfer proportions uniformly in every opponent section, which is stronger than the requested balance.
In fact, applying the lemma to unchanged transfers \(x_{tu}(r,r)=B_{tu}(r)\) shows that the balanced-baseline promise already follows from the stated mass and reversal conditions.
Although individual game outcomes remain elements of the finite set \(S\), atomless partner sets permit arbitrary transfer proportions. The realization lemma proves that these proportions are implementable simultaneously and symmetrically, so the LP is an exact formulation of this continuous problem.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time solvability of the stated continuous problem. The realization lemma is sound, including games within one type. I found one minor wording issue in the LP sufficiency argument; it does not affect the conclusion.
The label set \(C=S\times S\) is finite, and coordinate reversal induces an involution on it because \(S\) is closed under reversal.
Positivity of every supported mass \(\mu_t\) justifies every division by \(\mu_t\) or \(\mu_t\mu_u\). The marginal constraints imply
\(\sum_{r,s}x_{tu}(r,s)=\mu_t\mu_u\), so the proposed normalized label distributions are indeed probability distributions.
Reversing both outcomes preserves allowed transitions with the endpoints exchanged. This holds in all four coalition-membership cases.
For fixed \(a\), translation modulo one preserves Lebesgue measure in \(b\). For fixed \(b\), the map from \(a\) to \((b-a)\bmod 1\) also preserves Lebesgue measure.
The physical section masses are consequently \(\mu_u p_{tu}(r,s)=x_{tu}(r,s)/\mu_t\) in the first orientation and \(\mu_t p_{tu}(r,s)=x_{tu}(r,s)/\mu_u\) in the opposite orientation. Reversal symmetry identifies the latter with the required reverse-oriented mass.
Integrating these sections over the first endpoint gives exactly the prescribed joint masses. Assigning reverse labels in the opposite ordering guarantees pointwise reversal.
Reversal symmetry gives \(p_t(c)=p_t(c^*)\). Therefore the allocated lengths on the first half of the circle sum to exactly one half.
For a two-element orbit, its representative appears on the first half with measure \(p_t(c)\), and its reverse appears on the reflected half with that same measure. For a singleton orbit, reflection supplies the second half of its prescribed measure. Thus every label has precisely the required total measure.
For nonzero, non-antipodal circle differences, exchanging endpoints changes the difference from \(d\) to \(1-d\), so the stated reflection identity guarantees reversal.
The antipodal difference cannot be handled by assigning a single label solely as a function of that difference unless the label is fixed by reversal. The prover explicitly avoids this obstruction by using endpoint order for antipodal pairs.
The selected label \(c_0=(r,r)\) is an unchanged transition, hence admissible. Its reversed label is also an admissible unchanged transition, and it belongs to \(C\).
The antipodal set has product measure zero and contains only one partner in each section. Omitting the diagonal likewise removes only one partner from each section. Neither operation changes the required masses.
Internal interval endpoints can be assigned in reflected pairs as described. These finite exceptional sets also have zero section measure. There is no unhandled fixed point of reflection among the non-antipodal differences actually used.
The target-label interval lengths sum to \(\mu_t\), as required. Forbidden labels have zero transfer mass, so only allowed transitions need positive-length intervals.
The finite interval partitions, circle-difference functions, reflected assignments, and endpoint-order exception are measurable.
Summing the established joint section masses over final outcomes produces \(B_{tu}(r)/\mu_t\); summing over baseline outcomes produces \(Q_{tu}(s)/\mu_t\). This proves precisely the required baseline and final balance, and in fact establishes the stronger joint-label balance claimed.
Because there are finitely many types and labels, the almost-everywhere requirements can hold simultaneously. No issue arises from intersecting exceptional sets.
Nonnegativity, forbidden transitions, baseline marginals, opponent reversal, and target marginals are all included. Constraint 2 applies to both families of variables, using the appropriate endpoint coalition flags.
The winning inequality is correctly scaled:
\(\mu_t a_0\geq\mu_t a_t\).
Expanding the definitions gives exactly constraint 6, and positivity of \(\mu_t\) makes it equivalent to \(a_0\geq a_t\). Non-strict inequalities correctly implement ties as wins.
Necessity follows directly from the required transfer conditions and score comparisons. Sufficiency follows from the realization lemma and the winning inequalities. The freedom to choose the microscopic baseline arrangement is essential and is explicitly acknowledged.
There is one minor wording issue concerning the target score, detailed below.
The variable count \(N=(\tau^2+\tau)m^2\) is exact before eliminating forbidden variables. Each listed constraint family contributes at most \(O(N)\) constraints.
Reversal indices and allowed transitions can be computed within the stated \(O(\tau^2m^2)\) rational-operation bound. Input comparisons and products have polynomial bit cost.
Products \(\mu_t s_1\) have \(O(L)\)-bit encodings. The winning inequalities introduce no products of variables. The sparse construction bound and the dense encoding bound \(O(N^2L)\) are therefore valid.
The invoked theorem is the standard exact polynomial-time feasibility theorem for finite rational linear systems; equalities and lower-dimensional feasible sets are permitted. This is the relevant theorem, rather than a feasibility procedure requiring nonempty interior. The polynomial-time feasibility statement is also recorded in [MIT’s ellipsoid-method lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Its hypotheses are satisfied here: the LP is finite, explicitly encoded, and rational. Since the supported types and scoring outcomes are explicitly listed, their counts are bounded by the input length. Consequently, the claimed \((\tau m L)^{O(1)}\) bit-operation bound establishes membership in \(\mathrm P\).
Polynomial-size rational feasible transfers and the resulting rational interval descriptions are consistent with exact rational LP algorithms and the stated construction.
The balanced-baseline promise is indeed redundant under the given mass and reversal assumptions: the unchanged-transfer specialization falls within the lemma already proved.
The proof covers \(\tau=1\), \(m=1\), zero baseline entries, zero transfer entries, singleton reversal orbits, and either coalition status of the target. No substantive edge case is missing.
Minor — Section 2, sufficiency: “Its target score is the left-hand score expression” is imprecise. The left-hand side of constraint 6 is \(\mu_t a_0\), rather than \(a_0\).
Required clarification: Identify the target score expression separately from its scaling by \(\mu_t\). The preceding derivation already supplies the correct relationship, so this is an editorial correction and requires no additional mathematics.
No major issue, missing lemma, or counterexample was found.
⟨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.