Answer: —
Theorem 4.2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor binary valuations, there is no algorithm which is EF1-over-rounds and also chooses a maximum weight matching for each time step, even for non-dynamic valuations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite sets of valuation types \(P,Q\), rational masses summing to one on each side, and static binary values \(v_p(q),v_q(p)\in\{0,1\}\), decide whether there is an infinite schedule of rounds with individual EF1 after every round and maximum welfare in every round. Represent agents by state classes \((p,h)\), where \(h\in\mathbb{N}^{Q}\) records their cumulative counts of matches with each type; each round couples the current state-class masses, gives every mass unit one integral match, and updates histories. The projected type flow \(x(p,q)\) in each round must maximize \(W(x)=\sum_{p,q}x(p,q)(v_p(q)+v_q(p))/2\) among flows with the given type masses; require \(v_p(g-h)\le1\) for every pair of same-side state classes \((p,h),(r,g)\), with the corresponding inequalities on \(Q\).
Let \(P,Q\) be nonempty finite type sets with positive binary-rational masses \(\alpha_p,\beta_q\), each side summing to \(1\), and static, possibly asymmetric values \(v_p(q),v_q(p)\in\{0,1\}\). Each society is given by its positive-mass support; \(\tau=|P|+|Q|\) is the total support size, not the number of possible types. Set \(m=\max\{|P|,|Q|\}\), and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Initially, type \(p\) has mass \(\alpha_p\) at history \(0\in\mathbb N_{\ge0}^{Q}\), and type \(q\) has mass \(\beta_q\) at history \(0\in\mathbb N_{\ge0}^{P}\). Histories count cumulative matches, and valuations are additive.
A round chooses nonnegative real coupling masses \(y_{(p,h),(q,k)}\) whose marginals equal the current state-class masses. Each coupled portion moves to histories \(h+e_q\) and \(k+e_p\), where \(e_q,e_p\) are coordinate unit vectors: masses may split, but every individual receives exactly one integral match, and previous matches are irrevocable.
The projected flow \(x_{pq}=\sum_{h,k}y_{(p,h),(q,k)}\) must maximize \(W(x)=\frac12\sum_{p,q}x_{pq}(v_p(q)+v_q(p))\) over all nonnegative flows with row sums \(\alpha\) and column sums \(\beta\); every maximizing flow is allowed.
After every round, individual EF1 requires \(\sum_q v_p(q)(g_q-h_q)\le1\) for every ordered pair of positive-mass classes \((p,h),(r,g)\) on the first side, including \(p=r\), and \(\sum_p v_q(p)(\ell_p-k_p)\le1\) for every ordered pair \((q,k),(s,\ell)\) on the second side.
Is deciding whether an infinite schedule satisfying these EF1 and per-round maximum-welfare requirements exists solvable in polynomial time, or is it NP-hard?
For finite agents, static asymmetric binary instances can admit no such infinite schedule; this is an impossibility result, not a hardness classification. For symmetric binary valuations, a schedule exists and is computable in polynomial time per round. [Source](https://arxiv.org/pdf/2009.09336).
No result settling this precise mass-based decision problem was located in the literature search.
The general complexity classification remains unresolved here. I prove three further results:
None of these results establishes a polynomial-time algorithm or $\mathrm{NP}$-hardness for the general infinite-schedule problem.
Write
$$
a=|P|,\qquad b=|Q|,\qquad \tau=a+b,\qquad m=\max\{a,b\}.
$$
Let $\mathcal T$ be the transportation polytope with row sums $\alpha$ and column sums $\beta$, and let
$$
W^*=\max_{F\in\mathcal T}
\frac12\sum_{p,q}F_{pq}\bigl(v_p(q)+v_q(p)\bigr).
$$
For $F\in\mathcal T$, define
$$
\rho_{p,q}=\frac{F_{pq}}{\alpha_p},
\qquad
\sigma_{q,p}=\frac{F_{pq}}{\beta_q}.
$$
Consider the following feasibility condition, denoted $\mathcal E$:
$$
F\in\mathcal T,\qquad W(F)=W^*,
$$
$$
\sum_q v_p(q)\rho_{p,q}
\ge
\sum_q v_p(q)\rho_{r,q}
\qquad(p,r\in P),
$$
$$
\sum_p v_q(p)\sigma_{q,p}
\ge
\sum_p v_q(p)\sigma_{s,p}
\qquad(q,s\in Q).
$$
Proposition 1. An infinite admissible schedule implies feasibility of $\mathcal E$.
Proof. Let $x^j$ be the projected flow in round $j$, and put
$$
F^{(t)}=\frac1t\sum_{j=1}^t x^j.
$$
Each $F^{(t)}$ belongs to $\mathcal T$ and has welfare $W^*$.
Let $\mu^t_{p,h}$ denote the mass at first-side class $(p,h)$ after round $t$. Define its type-normalized mean history by
$$
H_p(t)=\frac1{\alpha_p}\sum_h\mu^t_{p,h}h.
$$
Conservation of cumulative matches gives
$$
H_p(t)_q=t\frac{F^{(t)}_{pq}}{\alpha_p}.
$$
For fixed $p,r$, average individual EF1 over the normalized history distributions of these two types. Every pair receiving positive weight satisfies EF1, so
$$
\sum_qv_p(q)\bigl(H_r(t)_q-H_p(t)_q\bigr)\le1.
$$
Thus
$$
\sum_qv_p(q)
\left(
\frac{F^{(t)}_{rq}}{\alpha_r}
-
\frac{F^{(t)}_{pq}}{\alpha_p}
\right)
\le\frac1t.
$$
The corresponding column inequality follows by the same calculation on the second side.
The transportation polytope is compact. A subsequence of $F^{(t)}$ therefore converges to some $F\in\mathcal T$. Passing to the limit preserves optimal welfare and yields all inequalities defining $\mathcal E$. $\square$
Computing $W^*$ and testing $\mathcal E$ takes
$$
\operatorname{poly}(m,\tau,L)
$$
bit operations by rational linear programming. There are $ab\le m^2$ variables and $O(\tau^2)$ constraints. All coefficients have encoding length polynomial in $L$, including the reciprocals of the positive masses.
The next result reduces the number of individual trajectories needed to describe a finite schedule.
A first-side match word of length $T$ is a sequence
$$
w=(w_1,\ldots,w_T)\in Q^T.
$$
Its history after round $t$ is
$$
h_w(t)=\sum_{j=1}^t e_{w_j}.
$$
A second-side word is defined analogously as an element of $P^T$.
Lemma 2. A finite schedule can be represented by weighted match words for each type. Conversely, weighted words define a schedule whenever:
The converse preserves the prescribed prefix-history distributions.
Proof. For the forward direction, consider a schedule and its first-side outgoing masses. At round $j$, let $A^j_{p,h,q}$ be the mass of class $(p,h)$ assigned to type $q$. At a class of positive mass $\mu^{j-1}_{p,h}$, use transition probability
$$
\frac{A^j_{p,h,q}}{\mu^{j-1}_{p,h}}.
$$
Starting from history zero, these transitions define a probability distribution over length-$T$ words. Multiplying by $\alpha_p$ gives word masses. Induction on rounds shows that their prefix-history masses agree with the given schedule. Apply the same construction on the second side.
For the converse, define $A^j_{p,h,q}$ from the first-side words whose history before round $j$ is $h$ and whose next symbol is $q$. Define $B^j_{q,k,p}$ similarly. By hypothesis,
$$
x^j_{pq}:=\sum_hA^j_{p,h,q}
=\sum_kB^j_{q,k,p}.
$$
For $x^j_{pq}>0$, set
$$
y^j_{(p,h),(q,k)}
=
\frac{A^j_{p,h,q}B^j_{q,k,p}}{x^j_{pq}}.
$$
If $x^j_{pq}=0$, set these coupling entries to zero. Nonnegativity then forces all corresponding $A$ and $B$ entries to vanish.
Summing this coupling over either side gives the prescribed outgoing masses. Its history transitions consequently give exactly the intended prefix-history distributions. $\square$
Theorem 3. If an admissible schedule exists through round $T$, one exists using at most
$$
K_P=a\bigl(1+T(b-1)\bigr)
$$
first-side words and at most
$$
K_Q=b\bigl(1+T(a-1)\bigr)
$$
second-side words. In particular, their total number satisfies
$$
K:=K_P+K_Q
=\tau+T(2ab-\tau)
\le\tau+2Tm^2.
$$
Their weights can be chosen rational with total encoding length polynomial in $T,m,\tau,L$.
Proof. Begin with the word representation of a feasible schedule.
Fix a first-side type $p$. For each of its words $w$, form the vector consisting of:
For each fixed $j$, the indicators sum to the initial coordinate. Hence these vectors have rank at most
$$
1+T(b-1).
$$
Suppose more than this many words have positive weights $\lambda_w$. Their vectors are linearly dependent: there is a nonzero vector $z$ such that the weighted-vector sum with coefficients $z_w$ is zero. In particular,
$$
\sum_wz_w=0,
$$
so $z$ has both positive and negative entries.
Let
$$
\theta=\min_{z_w>0}\frac{\lambda_w}{z_w}.
$$
Replacing $\lambda_w$ by $\lambda_w-\theta z_w$ preserves nonnegativity, total type mass, and every per-round opponent-type marginal. At least one positive weight becomes zero. Repeating this operation leaves at most $1+T(b-1)$ words for type $p$.
Apply this argument to every type on both sides. The projected flow in every round remains unchanged. Every retained word came from the original schedule, so every retained prefix history belongs to its original positive-mass support. Removing histories cannot introduce an EF1 violation. Lemma 2 reconstructs an admissible schedule.
It remains to justify rational weights. Fix the selected words and impose the following linear constraints on their weights:
These constraints have rational coefficients, and the sparsified real weights prove feasibility. The feasible set is bounded because each weight is at most its type mass. It therefore has a rational extreme point.
For completeness, the encoding bound follows from the usual determinant bound for a basic feasible solution. There are at most $K$ variables; the constraint coefficients belong to a fixed finite rational set; and the right-hand sides have encoding length polynomial in $m,\tau,L$. Clearing denominators and applying Cramer's rule gives coordinate bit lengths polynomial in $K,m,\tau,L$, hence polynomial in $T,m,\tau,L$. Zero-weight words may be deleted. $\square$
Corollary 4. Finite-horizon feasibility belongs to $\mathrm{NP}$ when $T$ is written in unary.
A certificate lists the words from Theorem 3 and their rational weights. A verifier checks type masses, per-round type-pair agreement, optimal welfare, and all ordered prefix-history EF1 comparisons.
There are at most $K$ words. All EF1 comparisons can be checked in
$$
\operatorname{poly}(T,m,\tau,L)
$$
time, including comparisons between words of the same type. Computing $W^*$ also takes polynomial time.
This does not assert membership in $\mathrm{NP}$ for a binary-encoded horizon: the certificate bound is polynomial in the numerical value of $T$.
There is also an exact deterministic algorithm. There are at most
$$
a b^T+b a^T\le\tau m^T
$$
candidate typed words. Enumerate collections of at most $K$ words, discard collections with an EF1-forbidden prefix pair, and solve the weight LP for each remaining collection. Its running time is bounded by
$$
2^{O\left((\tau+Tm^2)
\left(\log(\tau+1)+T\log(m+1)\right)\right)}
\operatorname{poly}(T,m,\tau,L).
$$
This avoids enumerating all possible history supports separately.
Proposition 5. An infinite admissible schedule exists if and only if every finite horizon is feasible.
Proof. Only sufficiency needs proof. Choose feasible schedules of horizons tending to infinity. At each fixed round there are finitely many possible histories, and every coupling coordinate lies in $[0,1]$. Diagonal subsequence extraction gives limits for all coupling coordinates.
Every fixed-round marginal, transition, and welfare equation involves finitely many coordinates, so it passes to the limit. For a forbidden pair of histories, EF1 requires the product of their class masses to be zero. This is a closed condition and also passes to the limit. The limiting couplings form an infinite admissible schedule. $\square$
Consequently, successive finite-horizon tests eventually detect every NO instance. Neither this argument nor the sparse-certificate theorem supplies a horizon bound sufficient to decide the general infinite problem.
Suppose there are partitions $\mathcal B_Q$ of $Q$ and $\mathcal B_P$ of $P$ with the following properties:
Singleton partitions recover the elementary valuations from the notes. Larger blocks allow additional non-elementary liked sets.
Theorem 6. Under these hypotheses, an infinite admissible schedule exists exactly when $\mathcal E$ is feasible. Decision therefore takes
$$
\operatorname{poly}(m,\tau,L)
$$
time. Moreover, every YES instance in this subclass admits a finite repeating word construction.
We first prove the required rounding fact.
Lemma 7. Let $R=(R_1,\ldots,R_c)$ be a probability vector and $T$ a finite horizon. There is a distribution over words in $\{1,\ldots,c\}^T$ such that:
$$ \lfloor tR_i\rfloor\le N_i(t)\le\lceil tR_i\rceil. $$
Proof. Construct a flow network with one position vertex supplying one unit for each $t$. Connect it to category vertices $c_{i,t}$ by arcs with bounds $[0,1]$.
For each category, connect its consecutive category vertices. The arc leaving $c_{i,t}$ carries the cumulative assignment to category $i$ through time $t$; give it bounds
$$
[\lfloor tR_i\rfloor,\lceil tR_i\rceil].
$$
The final category arcs enter a sink demanding $T$ units.
Sending $R_i$ from every position to category $i$, with cumulative chain flows $tR_i$, is feasible.
All supplies and bounds are integers. Every vertex of this bounded flow polytope is integral: otherwise, the undirected graph of noninteger-flow arcs has no leaf, since conservation at a leaf would force its sole noninteger incident flow to be integral. It therefore contains a cycle. Each cycle arc is strictly inside its integer bounds, permitting sufficiently small opposite cycle perturbations. This contradicts extremality.
Decompose the specified fractional flow into integral vertices. Each integral vertex selects exactly one category at every position and obeys all prefix bounds. The decomposition preserves every position-to-category arc value, giving the claimed marginals. $\square$
Fix a rational $F\in\mathcal E$. Choose a positive integer $D$ such that every
$$
D\rho_{p,q}\quad\text{and}\quad D\sigma_{q,p}
$$
is integral.
For each $p$ and each block $B\in\mathcal B_Q$, set
$$
R_{p,B}=\sum_{q\in B}\rho_{p,q}.
$$
Apply Lemma 7 to these block probabilities for horizon $D$.
Refine each occurrence of block $B$ into a type $q\in B$ with conditional probability
$$
\frac{\rho_{p,q}}{R_{p,B}},
$$
when $R_{p,B}>0$. A zero-probability block never occurs. The resulting type words have marginal $\rho_{p,q}$ at every position, and retain the block-prefix quotas. Multiply their probabilities by $\alpha_p$.
Perform the analogous construction on the second side, using $\mathcal B_P$ and $\sigma$. The prescribed mass for type pair $(p,q)$ at every position is $F_{pq}$ on both sides. Lemma 2 couples the words, and every round has optimal welfare.
Let $S_p$ be the liked set of evaluator $p$. For every word belonging to type $r$, its utility after a prefix of length $t$ lies between
$$
\left\lfloor t\sum_{q\in S_p}\rho_{r,q}\right\rfloor
\quad\text{and}\quad
\left\lceil t\sum_{q\in S_p}\rho_{r,q}\right\rceil.
$$
For a block this is the quota bound. For a block complement it follows by subtracting the block count from $t$. Empty and full liked sets satisfy it directly.
The inequalities in $\mathcal E$ imply
$$
\sum_{q\in S_p}\rho_{p,q}
\ge
\sum_{q\in S_p}\rho_{r,q}.
$$
Therefore, for any supported own history $h$ and comparison history $g$,
$$
v_p(g)-v_p(h)
\le
\left\lceil t\sum_{q\in S_p}\rho_{r,q}\right\rceil
-
\left\lfloor t\sum_{q\in S_p}\rho_{p,q}\right\rfloor
\le1.
$$
The last inequality uses $\lceil A\rceil-\lfloor B\rfloor\le1$ whenever $A\le B$. The second-side proof uses $\sigma$ in the same way. Thus this period satisfies EF1.
At time $D$, every word of type $r$ has exactly
$$
D\sum_{q\in S_p}\rho_{r,q}
$$
matches valued by evaluator $p$. This is independent of the selected word: all block totals are integral and fixed.
Assign each word cohort its same word in every period. At time $nD+t$, where $0\le t<D$, the utility difference between a type-$r$ comparison history and a type-$p$ own history is
$$
nD\left(
\sum_{q\in S_p}\rho_{r,q}
-
\sum_{q\in S_p}\rho_{p,q}
\right)
+
\bigl(\text{comparison-prefix utility}
-\text{own-prefix utility}\bigr).
$$
The first term is nonpositive by $\mathcal E$, and the second is at most one by the preceding prefix calculation. This proves EF1 across every period, including within-type comparisons. The second side satisfies the identical conclusion.
At each phase, the word cohorts prescribe type-pair masses $F_{pq}$. Coupling those cohorts by the product construction in Lemma 2, and aggregating cohorts with equal actual histories, gives valid couplings in the stated model. All matches remain integral for each individual, and all previous matches remain in its history.
This proves sufficiency and the repeating-witness assertion. Necessity is Proposition 1. $\square$
A rational feasible $F$ can be chosen with encoding length polynomial in $m,\tau,L$. Taking a common denominator gives
$$
D\le2^{\operatorname{poly}(m,\tau,L)}.
$$
Theorem 3 can sparsify the period while preserving its per-position type-pair marginals. Thus a repeating witness has description length at most
$$
2^{\operatorname{poly}(m,\tau,L)}.
$$
This is a witness-size bound, not a claim of polynomial-time schedule generation for this larger subclass.
The following construction replaces the exponentially many subset types in the notes by a four-wise independent family.
Theorem 8. For every power of two $d\ge1024$, there is an explicitly supported instance with
$$
|P|=2d^2,\qquad |Q|=d,
$$
positive dyadic masses, and feasible $\mathcal E$, but no EF1 state obtainable after $d/2$ rounds.
Let $d=2^k$, and let $K$ be a field of $d$ elements. Its additive group is a $k$-dimensional vector space over $\mathbb F_2$. Define
$$
V=\mathbb F_2\oplus K\oplus K,
\qquad
c_x=(1,x,x^3)\in V
\quad(x\in K).
$$
Any set of at most four distinct vectors $c_x$ is linearly independent over $\mathbb F_2$. To verify this, a dependence over $\mathbb F_2$ would be a nonempty subset summing to zero.
$$
a^3+b^3+c^3+(a+b+c)^3
=(a+b)(a+c)(b+c).
$$
All three factors are nonzero, contradicting a zero sum in the third coordinate.
Let $V^*$ be the set of $\mathbb F_2$-linear functionals on $V$, and define
$$
\varepsilon_u(x)=(-1)^{u(c_x)}
\qquad(u\in V^*).
$$
There are $|V^*|=2d^2$ functionals.
For uniform $u$, any at most four signs are independent and uniform: linear independence of the corresponding $c_x$ makes the evaluation map onto the relevant bit vectors surjective, with equal-sized fibers.
Let $u_0$ read the first coordinate of $V$. Then
$$
\varepsilon_{u+u_0}(x)=-\varepsilon_u(x)
$$
for every $x$. Hence the distribution of the entire sign vector is invariant under global sign reversal.
Set
$$
Q=K,\qquad P=\{p_u:u\in V^*\},
$$
with masses
$$
\beta_x=\frac1d,\qquad \alpha_{p_u}=\frac1{2d^2}.
$$
Define
$$
S_u=\{x\in K:\varepsilon_u(x)=1\},
$$
$$
v_{p_u}(x)=\mathbf1\{x\in S_u\},
\qquad
v_x(p_u)=1-v_{p_u}(x).
$$
Every match contributes exactly one to combined utility, so every transportation flow has welfare $1/2$. The independent flow
$$
F_{p_u,x}=\alpha_{p_u}\beta_x
$$
satisfies $\mathcal E$, since all normalized rows are identical and all normalized columns are identical.
The construction uses the actual positive-mass support. Here
$$
m=2d^2,\qquad \tau=2d^2+d.
$$
The valuation table has $O(d^3)$ entries, and the masses require $O(d^2\log d)$ bits. Thus its explicit input length is polynomial in $d$. If identical valuation types are identified, their masses can be merged; all subsequent weighted calculations remain unchanged.
Suppose an EF1 state is obtainable at
$$
t=d/2.
$$
For each $u$, let
$$
M_u=\max_h h(S_u),
$$
where the maximum ranges over all positive-mass first-side histories, regardless of their owning types.
The total first-side mean of coordinate $x$ is $t\beta_x=t/d$. Therefore
$$
M_u\ge\frac{t|S_u|}{d}.
$$
EF1 requires every history owned by $p_u$ to have utility at least $M_u-1$. Hence total first-side utility satisfies
$$
U_P\ge\mathbb E_u M_u-1.
$$
For evaluator $x$ on the second side, its utility for the population-average history is
$$
t\sum_u\alpha_{p_u}v_x(p_u)=t/2,
$$
because $\varepsilon_u(x)$ is uniform. Averaging its EF1 comparisons over that population shows that every own history has utility at least $t/2-1$. Consequently,
$$
U_Q\ge t/2-1.
$$
Choose any positive-mass first-side history $h$. It has integer coordinates summing to $t=d/2$. Put
$$
a_x=h_x-\frac12.
$$
Then
$$
\sum_xa_x=0,\qquad |a_x|\ge\frac12.
$$
For uniform $u$, define
$$
Z=h(S_u)-\frac{t|S_u|}{d}
=\frac12\sum_xa_x\varepsilon_u(x).
$$
Global sign reversal makes $Z$ symmetric about zero. Four-wise independence gives
$$
\mathbb EZ^2
=\frac14\sum_xa_x^2
\ge\frac d{16},
$$
and
$$
\mathbb EZ^4
=
\frac1{16}
\left(
3\left(\sum_xa_x^2\right)^2
-2\sum_xa_x^4
\right)
\le3(\mathbb EZ^2)^2.
$$
Hölder's inequality, applied to
$|Z|^2=|Z|^{2/3}|Z|^{4/3}$ with exponents $3/2$ and $3$, yields
$$
\mathbb EZ^2
\le
(\mathbb E|Z|)^{2/3}(\mathbb EZ^4)^{1/3}.
$$
Therefore
$$
\mathbb E|Z|
\ge
\frac{(\mathbb EZ^2)^{3/2}}{(\mathbb EZ^4)^{1/2}}
\ge\sqrt{\frac d{48}}.
$$
Writing $Z_+=\max\{Z,0\}$, symmetry gives
$$
\mathbb EZ_+=\frac12\mathbb E|Z|
\ge\sqrt{\frac d{192}}.
$$
Both $M_u\ge h(S_u)$ and $M_u\ge t|S_u|/d$ hold. Thus
$$
M_u-\frac{t|S_u|}{d}\ge Z_+.
$$
Since $\mathbb E_u|S_u|=d/2$, averaging gives
$$
\mathbb E_uM_u
\ge t/2+\sqrt{\frac d{192}}.
$$
Combining the two utility lower bounds,
$$
U_P+U_Q
\ge
t+\sqrt{\frac d{192}}-2
>t,
$$
where the strict inequality follows from $d\ge1024$.
But every cumulative match contributes exactly one to combined utility, and total match mass in each round is one. Hence necessarily
$$
U_P+U_Q=t.
$$
This contradiction proves the theorem. $\square$
The obstruction holds even without imposing maximum welfare, because every projected flow is already optimal. Its polynomial support size strengthens the counterexample, but it does not constitute a hardness reduction: no computational problem has been encoded with a proved YES/NO equivalence.
The averaged optimal-flow LP is necessary, polynomial-time testable, and sufficient for the partition subclass above. It is insufficient in general, even for polynomial-support families of complementary asymmetric valuations.
Finite-horizon feasibility now has polynomial-size certificates for unary horizons. The missing step remains an argument connecting infinite existence to a bounded, effectively checkable witness—or a reduction that directly controls infinite schedules. I have proved neither.
⟨structured verdict parsed — rendered above⟩
The output establishes valid partial results, but it does not settle the general infinite-schedule decision problem. I found no mathematical error or substantive gap in the results proved. The appropriate classification is partial, consistent with the prover’s own claim.
Every projected round flow belongs to the transportation polytope and has welfare $W^*$. Their average $F^{(t)}$ therefore has these properties as well.
The identity
$$
H_p(t)_q=\frac{tF^{(t)}_{pq}}{\alpha_p}
$$
correctly follows from conservation of cumulative matches. Averaging EF1 over the normalized distributions of two types gives the stated inequality with error $1/t$. Positive masses justify all divisions, and within-type comparisons cause no difficulty.
Compactness supplies a convergent subsequence with round indices tending to infinity. All transportation, welfare, and normalized envy constraints are continuous in $F$, so the limit satisfies $\mathcal E$.
The polynomial-time LP claim is also justified: there are $ab$ variables, polynomially many constraints, and rational coefficients of polynomial encoding length. Computing $W^*$ first supplies the rational right-hand side for the optimal-welfare constraint.
The forward construction in Lemma 2 reproduces the schedule’s history distributions by induction. Histories that merge do not invalidate the construction: the stated transition probabilities reproduce the outgoing masses from each merged class.
In the converse construction, summing
$$
\frac{A^j_{p,h,q}B^j_{q,k,p}}{x^j_{pq}}
$$
over $k$ gives $A^j_{p,h,q}$, and summing over $h$ gives $B^j_{q,k,p}$. When $x^j_{pq}=0$, nonnegativity forces the corresponding outgoing masses to vanish. Thus all marginal and transition requirements hold.
The rank bound in Theorem 3 is valid. At each position, the sum of the symbol-indicator coordinates equals the initial coordinate, giving rank at most $1+T(b-1)$ on the first side. The dependence vector has both signs because its coordinates sum to zero. The chosen weight adjustment preserves nonnegativity and all required marginals while eliminating at least one word.
Sparsification preserves EF1 because every retained prefix history belonged to the original positive-mass support. Subsequent coupling reconstructs precisely the distributions prescribed by the retained words.
The rational-weight argument is sound. The selected-word LP is nonempty, rational, and bounded. A rational extreme point has polynomial coordinate encoding length by the determinant bound, since both the number of variables and the input coefficient lengths are polynomial in $T,m,\tau,L$. Deleting zero-weight words preserves feasibility.
With unary $T$, both the number of retained words and their lengths are polynomial in the input parameters. Rational arithmetic verifies type masses, matching type-pair marginals, and welfare. Checking every ordered pair of supported word prefixes includes all required comparisons, including comparisons within a type. Consequently, the $\mathrm{NP}$ membership claim is justified.
The deterministic enumeration bound is consistent with the number of candidate words and the support-size bound. Enumerating collections of at most $K$ candidates gives an exponential factor of the displayed order, followed by polynomial-time LP feasibility checks.
The prover correctly limits these statements to finite horizons. They do not establish $\mathrm{NP}$ membership for the infinite problem or for binary-encoded horizons.
At each fixed round, only finitely many integral histories are possible. Coupling coordinates are bounded, so diagonal subsequence extraction applies to schedules with horizons tending to infinity.
The marginal, transition, and welfare equations pass to the limit because each fixed-round equation has finitely many coordinates. For a fixed EF1-forbidden pair, requiring the product of its two class masses to equal zero exactly expresses that the two classes cannot both have positive mass. This condition is closed.
Thus feasibility of every finite horizon implies an infinite admissible schedule. The claimed procedure for eventually detecting every NO instance follows. As the prover explicitly acknowledges, no stopping bound for YES instances is obtained.
Lemma 7 specifies a bounded flow polytope with integer supplies and bounds. Its integrality argument is valid: a nonempty graph of noninteger arcs cannot have a leaf, and an undirected cycle supports a sufficiently small conservation-preserving perturbation in both directions. Integer bounds ensure that noninteger arc values lie strictly inside their bounds. Hence a nonintegral feasible flow cannot be an extreme point.
Decomposition into integral vertices preserves each position-to-category marginal and produces the claimed prefix quotas.
Refinement from blocks to individual types preserves those quotas and supplies the required type marginals. The two sides prescribe $F_{pq}$ at every position, so Lemma 2 applies and welfare is optimal.
For block complements, subtracting the block count from the integral prefix length yields the claimed floor and ceiling bounds. The numerical inequality used for EF1 is valid:
$$
A\le B
\quad\Longrightarrow\quad
\lceil A\rceil-\lfloor B\rfloor\le1.
$$
At the period boundary, every relevant block total is integral and identical across words of a given type. Therefore every evaluator’s valued total is identical across those words. The displayed decomposition of envy into completed-period and prefix contributions is correct: the former is nonpositive by $\mathcal E$, and the latter is at most one.
Aggregating word cohorts with identical actual histories yields valid couplings in the stated model. The construction repeats match words; it does not require cumulative histories themselves to repeat.
The denominator and witness-size bounds are justified by polynomial encoding lengths and Theorem 3. The theorem gives a polynomial-time decision procedure under its partition hypotheses, without asserting polynomial-time schedule generation.
The asserted independence of up to four distinct vectors $c_x$ holds. Odd subsets are excluded by the first coordinate, pairs by distinct second coordinates, and four-element subsets by the stated characteristic-two identity. Linear independence makes the evaluation map surjective, giving four-wise independent uniform signs. Adding $u_0$ reverses all signs.
The instance has positive dyadic masses summing to one on each side. Complementary valuations make every match’s combined value equal to one, so every transportation flow is welfare optimal. The independent flow has identical normalized rows and identical normalized columns, which verifies $\mathcal E$.
The utility bounds correctly apply individual EF1 to all positive-mass histories. In particular, the population-average history gives a lower bound on $M_u$, while comparison with a maximizing history forces every own history of type $p_u$ to have utility at least $M_u-1$.
At $t=d/2$, each coordinate of the selected history is integral, so
$$
\left|h_x-\frac12\right|\ge\frac12.
$$
The displayed second- and fourth-moment calculations follow from four-wise independence. The Hölder exponents and rearrangement are correct, and sign symmetry gives the stated bound on $\mathbb E Z_+$.
The final constant is sufficient:
$$
\sqrt{\frac{1024}{192}}
=\sqrt{\frac{16}{3}}>2.
$$
Thus the two EF1 utility lower bounds contradict the exact identity $U_P+U_Q=t$.
The support and input-size estimates are polynomial in $d$. This establishes insufficiency of $\mathcal E$, including for polynomial-support instances, but supplies no hardness reduction.
The prover accurately distinguishes its valid results from the unresolved target. None of the finite-horizon certificate, compactness, subclass, or obstruction results establishes either a polynomial-time algorithm or $\mathrm{NP}$-hardness for the general infinite-schedule problem.
No repair is needed for the arguments presented. Completing the assigned task requires new mathematics of the kind the prover identifies: a general polynomial-time decision procedure or a hardness reduction with a proved equivalence concerning infinite admissible schedules. A finite-horizon obstruction alone does not provide that equivalence.
⟨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.