Answer: For arbitrary supported societies, \(V(I)\) is the finite rational bottleneck-flow threshold characterized above and is exactly computable in \(m^\tau\operatorname{poly}(m,\tau,L)\) time. In particular, \(V(I_8)=5\), including under every specified uniform replication.
Theorem 4 — class: other
Given finite homogeneous agent types \(P\) and item types \(Q\), masses \(\mu,\nu\), and ordinal rankings \(\succ\), let a deterministic mechanism observe only \((\mu,\nu,\succ)\) and output a transport plan \(x\). With \(\Phi_\infty(x,d)=\operatorname{ess\,sup}_{x_{pq}>0} d(p,q)\), determine \(\inf_{\mathcal M}\sup_{d\in\mathcal D(\succ)} \frac{\Phi_\infty(\mathcal M(\mu,\nu,\succ),d)}{\min_y \Phi_\infty(y,d)}\), and decide whether every such mechanism has value at least \(7\) on the eight-type profile with masses \(1/8\), and hence on arbitrary replications of it.
Let \(I=(P,Q,\mu,\nu,\succ)\) have disjoint finite supports of homogeneous agent and item types, with \(\tau=|P|\), \(m=|Q|\), positive binary-rational masses, and \(\sum_p\mu_p=\sum_q\nu_q=1\). A society is given by its support: the list of its \(\tau\) positive-mass agent types and their masses; \(\tau\) is not the number of possible rankings. Running times are measured in \(m,\tau,L\), where \(L\) is the total input bit length.
Each \(\succ_p\) is a strict total ranking of \(Q\). Let \(\mathcal D(\succ)\) be all finite-valued nonnegative pseudometrics on \(P\cup Q\) satisfying \(q\succ_p r\Rightarrow d(p,q)\leq d(p,r)\); distinct types may be colocated, and rankings may resolve distance ties arbitrarily.
A feasible transport plan belongs to \(\mathcal X(\mu,\nu)=\{x\in\mathbb R_{\geq0}^{P\times Q}:\sum_qx_{pq}=\mu_p,\ \sum_px_{pq}=\nu_q\}\). Mass may split, all mass must be assigned, and a deterministic mechanism observes only \(I\) and returns one such plan.
Define \(\Phi_\infty(x,d)=\max\{d(p,q):x_{pq}>0\}\), \(\operatorname{OPT}(I,d)=\min_{y\in\mathcal X(\mu,\nu)}\Phi_\infty(y,d)\), and \(V(I)=\inf_{\mathcal M}\sup_{d\in\mathcal D(\succ)}\Phi_\infty(\mathcal M(I),d)/\operatorname{OPT}(I,d)\). Interpret \(0/0=1\) and a positive numerator divided by zero as \(+\infty\).
Define \(I_8\) with \(P=\{a_1,\ldots,a_8\}\), \(Q=\{b_1,\ldots,b_8\}\), and every mass \(1/8\). Its rankings come from tree distances: \(b_8\) has child \(b_4\), whose children are \(b_2,b_6\); their children are respectively \(b_1,b_3\) and \(b_5,b_7\); \(b_{2j-1}\) has leaves \(a_{2j-1},a_{2j}\) for \(1\leq j\leq4\). Edge lengths at successive depths from \(b_8\) are \(2,3,4,5\); rank items by increasing distance, breaking ties by increasing index. Replication means multiplying every agent and item mass by the same positive integer and then normalizing.
What is \(V(I)\) for arbitrary supported societies? In particular, does \(V(I_8)\geq7\) hold, including under every uniform replication, or can a deterministic transport mechanism attain a smaller worst-case ratio on this profile?
For discrete perfect matching, every deterministic ordinal mechanism has worst-case max-distortion at least \(7\), witnessed by eight agents and eight items; a deterministic mechanism also achieves \(O(n^{\log_2 3})\) max-distortion. [Hastings–Ramakrishnan](https://arxiv.org/html/2510.05460v1)
No result settling the specified mass-transport minimax problem was located in the literature search.
For the profile specified in the question,
\[
\boxed{V(I_8)=5.}
\]
Thus a deterministic transport mechanism attains a worst-case ratio strictly smaller than \(7\), including under every uniform replication.
For arbitrary supported societies, there is an exact finite characterization of \(V(I)\) by linear programs and a bottleneck transport problem. It yields an optimal deterministic mechanism in time \(m^\tau\operatorname{poly}(m,\tau,L)\). In particular, \(V(I)\) is always finite and rational.
For a bipartite graph \(E\subseteq P\times Q\), write
\[
N_E(A)=\{q\in Q:\text{some }p\in A\text{ satisfies }(p,q)\in E\},
\]
and let \(\mu(A)=\sum_{p\in A}\mu_p\), with analogous notation for \(\nu\).
A feasible transport plan supported on \(E\) exists if and only if
\[
\mu(A)\leq \nu(N_E(A))\qquad\text{for every }A\subseteq P. \tag{1}
\]
Indeed, necessity follows by summing the transported mass from \(A\). For sufficiency, construct a flow network with capacities \(\mu_p\) from the source to \(p\), capacities \(2\) on the edges of \(E\), and capacities \(\nu_q\) from \(q\) to the sink. A cut crossing an edge of \(E\) has capacity at least \(2\). Every other cut, whose source-side agent set is \(A\), has capacity at least
\[
1-\mu(A)+\nu(N_E(A)).
\]
Condition (1) therefore makes every cut have capacity at least \(1\). The max-flow min-cut theorem gives a flow of value \(1\), which is the required transport plan.
For \(d\in\mathcal D(\succ)\) and \(t\geq0\), define
\[
E_t(d)=\{(p,q):d(p,q)\leq t\}.
\]
Consequently,
\[
\operatorname{OPT}(I,d)\leq t
\quad\Longleftrightarrow\quad
E_t(d)\text{ supports a feasible transport plan}. \tag{2}
\]
The optimum is attained: feasibility changes only at the finitely many agent–item distances.
For each edge \((p,q)\), define its normalized worst-case distance
\[
W_{pq}
=
\sup\{d(p,q):d\in\mathcal D(\succ),\ \operatorname{OPT}(I,d)\leq1\}. \tag{3}
\]
Allow \(W_{pq}=+\infty\).
These quantities satisfy \(W_{pq}\geq1\). To see this, take the pseudometric with distance \(1\) between every two distinct types. It is consistent with every ranking and has optimum \(1\).
For every feasible plan \(x\),
\[
\sup_{d\in\mathcal D(\succ)}
\frac{\Phi_\infty(x,d)}{\operatorname{OPT}(I,d)}
=
\max_{x_{pq}>0}W_{pq}. \tag{4}
\]
To prove the upper bound, first suppose \(T=\operatorname{OPT}(I,d)>0\). Scaling \(d\) by \(1/T\) gives a consistent pseudometric with optimum \(1\), so
\[
\frac{\Phi_\infty(x,d)}{T}
\leq \max_{x_{pq}>0}W_{pq}.
\]
If \(T=0\) and all supported \(W_{pq}\) are finite, every supported distance must be zero. Otherwise, arbitrary scaling of \(d\) would make one such \(W_{pq}\) infinite. The ratio is then \(1\), which is also bounded by the right-hand side.
For the reverse bound, fix a supported edge and a metric appearing in (3) with \(d(p,q)>0\). If its optimum is positive, the plan’s ratio is at least \(d(p,q)\), because that optimum is at most \(1\). If its optimum is zero, the ratio is infinite. Taking suprema gives the reverse inequality, including when \(W_{pq}\) is infinite.
Now put
\[
E_\lambda=\{(p,q):W_{pq}\leq\lambda\}.
\]
Equation (4) and threshold feasibility give the exact formula
\[
\boxed{
V(I)=
\min\left\{\lambda\geq1:
\mu(A)\leq\nu(N_{E_\lambda}(A))
\text{ for every }A\subseteq P
\right\}.
} \tag{5}
\]
The minimum is finite, as proved in Section 3. Any feasible flow on \(E_{V(I)}\) attains \(V(I)\).
There is no additional restriction hidden in the infimum over mechanisms: at a fixed instance, any feasible plan can be selected by a deterministic mechanism, using an arbitrary fixed feasible rule on other instances.
Write the ranking of \(p\) as
\[
q_{p,1}\succ_p q_{p,2}\succ_p\cdots\succ_p q_{p,m}.
\]
For \(k\in\{1,\ldots,m\}^P\), define the prefix graph
\[
H_k=\{(p,q_{p,j}):j\leq k_p\}.
\]
Keep precisely those \(k\) for which \(H_k\) supports a feasible transport plan.
For each retained \(k\) and each edge \((p,q)\), solve the following linear program:
\[ d(p,q_{p,j})\leq d(p,q_{p,j+1}) \qquad\text{for every }p,\ j<m; \]
\[ d(p,q_{p,j})\leq1 \qquad\text{whenever }j\leq k_p. \]
Let \(U_{pq}(k)\) denote its optimum, with value \(+\infty\) if unbounded. Then
\[
W_{pq}=\max_{\substack{k\in\{1,\ldots,m\}^P\\H_k\text{ feasible}}}U_{pq}(k). \tag{6}
\]
For justification, every feasible point of one of these programs has optimum at most \(1\), because \(H_k\) is feasible. Conversely, if a consistent metric has optimum at most \(1\), each row of \(E_1(d)\) is a nonempty ranking prefix. Thus \(E_1(d)=H_k\) for a retained \(k\), and that metric satisfies the corresponding program’s constraints.
There are at most \(m^\tau\) prefix vectors. Each program has \(\binom{m+\tau}{2}\) distance variables and polynomially many constraints. Exact rational linear programming computes its optimum or detects unboundedness in polynomial time. After computing the weights, sort their finite values and use max-flow feasibility to find the first admissible threshold in (5).
The total running time is therefore
\[
m^\tau\operatorname{poly}(m,\tau,L).
\]
All finite weights are rational, so (5) also proves rationality of \(V(I)\).
For completeness, a simple deterministic mechanism establishes
\[
1\leq V(I)\leq3^{\tau-1}. \tag{7}
\]
This is a valid universal upper bound, without a claim of sharpness.
Order the agent types arbitrarily. Process them sequentially, assigning each its mass greedily to its highest-ranked items with remaining capacity.
Fix a consistent metric and let \(T=\operatorname{OPT}(I,d)\). Start with an optimal transport plan. Suppose the current residual plan \(z\) uses only edges of distance at most \(C\), and the next type is \(p\). Let \(g\) be its greedy row.
Call an item \(q\) a deficit item if \(g_q>z_{pq}\), and an item \(r\) a surplus item if \(z_{pr}>g_r\). Every deficit item precedes every surplus item in \(p\)’s ranking. Indeed, for a surplus item \(r\), the greedy row leaves some of its available capacity unused; hence it has already exhausted \(p\)’s mass by that position. Any item on which the greedy row increases its assignment must occur earlier.
Thus, for every deficit \(q\) and surplus \(r\),
\[
d(p,q)\leq d(p,r)\leq C.
\]
In each deficit column \(q\), take \(g_q-z_{pq}\) mass from the other agents’ original assignments. Enough mass is available because \(g_q\) does not exceed the remaining column capacity. Redistribute those donor amounts to the surplus columns, whose total released capacity equals the total deficit.
If agent \(s\)’s mass is moved from \(q\) to \(r\), its new distance satisfies
\[
d(s,r)
\leq d(s,q)+d(q,p)+d(p,r)
\leq3C.
\]
All edges of the newly fixed greedy row have distance at most \(C\): existing positive edges already satisfy this, and increased edges are deficit edges.
This produces a feasible residual plan with distances at most \(3C\). Repeating the argument fixes the first \(\tau-1\) rows; the final row is forced by the remaining capacities. The resulting plan has bottleneck at most \(3^{\tau-1}T\).
The same reasoning applies when \(T=0\), yielding bottleneck zero and ratio \(1\). This proves (7), and hence finiteness in (5).
Suppose there are \(n\) agent types and \(n\) item types, all of mass \(1/n\). The support of every feasible transport plan contains a perfect matching.
Indeed, for any agent set \(A\), feasibility implies
\[
\frac{|A|}{n}\leq\frac{|N(A)|}{n}.
\]
Hall’s theorem therefore supplies a perfect matching in the support.
For every metric, that matching’s bottleneck is no larger than the original plan’s bottleneck. Applying this to an optimal plan also shows that the transport optimum equals the perfect-matching optimum. Consequently,
\[
V(I)
=
\min_{\text{perfect matchings }M}
\sup_{d\in\mathcal D(\succ)}
\frac{\max_p d(p,M(p))}{\operatorname{OPT}(I,d)}. \tag{8}
\]
Thus splitting mass does not improve the value of a fixed equal-mass profile. The cited discrete lower bound is an existential statement over profiles; it does not by itself establish the same lower bound for the particular fixed rankings in this question. [Hastings–Ramakrishnan, Theorem 4 and Appendix C](https://arxiv.org/html/2510.05460v1#A3)
The specified tree and tie-breaking give the following lists.
| Agent types | Items, from best to worst |
|---|---|
| \(a_1,a_2\) | \(b_1,b_2,b_4,b_3,b_8,b_6,b_5,b_7\) |
| \(a_3,a_4\) | \(b_3,b_2,b_4,b_1,b_8,b_6,b_5,b_7\) |
| \(a_5,a_6\) | \(b_5,b_6,b_4,b_7,b_8,b_2,b_1,b_3\) |
| \(a_7,a_8\) | \(b_7,b_6,b_4,b_5,b_8,b_2,b_1,b_3\) |
For each row, the generating distances in this order are
\[
5,\ 9,\ 12,\ 13,\ 14,\ 15,\ 19,\ 19.
\]
In particular, all right-half agents rank \(b_1\) before \(b_3\). That fixed comparison will be used below.
Use the perfect matching
\[
\begin{aligned}
&a_1\mapsto b_8,\qquad a_2\mapsto b_1,\qquad
a_3\mapsto b_2,\qquad a_4\mapsto b_3,\\
&a_5\mapsto b_4,\qquad a_6\mapsto b_5,\qquad
a_7\mapsto b_6,\qquad a_8\mapsto b_7.
\end{aligned} \tag{9}
\]
Assign mass \(1/8\) on each of these edges.
Fix any consistent pseudometric. By Section 4, choose an optimal perfect matching \(M^\star\), and put
\[
T=\max_i d(a_i,M^\star(a_i)).
\]
Every agent prefers its favorite item to its assigned item in \(M^\star\). Therefore its favorite-item distance is at most \(T\).
Consider either pair sharing a favorite item \(f\), and let \(h\) be their common second-ranked item. At least one agent \(z\) in the pair is assigned an item other than \(f\). Consequently,
\[
d(z,h)\leq T,\qquad d(z,f)\leq T,
\]
so \(d(f,h)\leq2T\). For either agent \(p\) in that pair,
\[
d(p,h)\leq d(p,f)+d(f,h)\leq3T. \tag{10}
\]
Consider one half of four agents. Its three internal items are its two favorite leaves and their common parent \(h\). At least one agent \(z\) in that half is assigned outside these three items. The rankings imply
\[
d(z,b_4)\leq T,\qquad d(z,h)\leq T.
\]
For any agent \(p\) in the same half, (10) gives
\[
d(p,b_4)
\leq d(p,h)+d(h,z)+d(z,b_4)
\leq5T. \tag{11}
\]
Let \(r\) be the agent assigned \(b_8\) in \(M^\star\).
If \(r\) is in the left half, it ranks \(b_1\) before \(b_8\), whence
\[
d(b_1,b_8)\leq d(b_1,r)+d(r,b_8)\leq2T.
\]
It follows that \(d(a_1,b_8)\leq3T\).
Now suppose \(r\) is in the right half. It satisfies
\[
d(r,b_4)\leq T,\qquad d(r,b_1)\leq d(r,b_3). \tag{12}
\]
Among the four left-half agents, some agent \(z\) is assigned outside \(\{b_1,b_2,b_3\}\). Hence
\[
d(z,b_4)\leq T.
\]
Let \(f\in\{b_1,b_3\}\) be \(z\)’s favorite item. Then \(d(z,f)\leq T\), so
\[
d(r,f)\leq d(r,b_4)+d(b_4,z)+d(z,f)\leq3T.
\]
If \(f=b_1\), this directly bounds \(d(r,b_1)\). If \(f=b_3\), comparison (12) gives the same bound. Therefore
\[
d(b_1,b_8)\leq d(b_1,r)+d(r,b_8)\leq4T,
\]
and
\[
d(a_1,b_8)\leq d(a_1,b_1)+d(b_1,b_8)\leq5T. \tag{13}
\]
The edges of (9) are now bounded respectively by
\[
5T,\ T,\ 3T,\ T,\ 5T,\ T,\ 3T,\ T.
\]
Thus the mechanism has ratio at most \(5\). When \(T=0\), these inequalities give numerator zero, so the prescribed ratio is \(1\). We have proved
\[
V(I_8)\leq5. \tag{14}
\]
For every agent \(p=a_i\), construct a consistent tree pseudometric \(d^{(i)}\) with
\[
d^{(i)}(a_i,b_8)=5,
\qquad
\operatorname{OPT}(I_8,d^{(i)})=1. \tag{15}
\]
Let \(f\) be \(a_i\)’s favorite leaf item, \(g\) its sibling leaf item, and \(h\in\{b_2,b_6\}\) their common parent. Take three branches \(A,B,C\) emanating from a center \(o\), with the following placements:
| Branch or center | Placements |
|---|---|
| Center \(o\) | \(h\) and \(b_4\) |
| Branch \(A\) | The other agent sharing \(f\), at distance \(1\); \(f\), at distance \(2\); \(a_i\), at distance \(3\) |
| Branch \(B\) | Both agents sharing \(g\), at distance \(1\); \(g\), at distance \(2\) |
| Branch \(C\) | All four agents in the other half, at distance \(1\); its three internal items and \(b_8\), at distance \(2\) |
Use tree-path distance, restricted to the sixteen types. Colocations are permitted by the question.
In each agent’s prescribed ranking order, its distances are:
\[ 1,3,3,5,5,5,5,5; \]
\[ 1,1,1,3,3,3,3,3; \]
\[ 1,1,1,1,1,1,3,3. \]
Every sequence is nondecreasing. Thus \(d^{(i)}\in\mathcal D(\succ)\), including all the specified tie-breaking comparisons.
There is a perfect matching of bottleneck \(1\):
Every one of these distances is exactly \(1\). Conversely, \(a_i\)’s distance to every item is at least \(1\), so every feasible transport plan has bottleneck at least \(1\). Hence the optimum is exactly \(1\).
Finally, \(a_i\) and \(b_8\) lie on different branches at distances \(3\) and \(2\) from the center. Their distance is \(5\), proving (15).
Now take any feasible transport plan \(x\). Since \(b_8\) has positive demand, some \(i\) satisfies \(x_{a_i b_8}>0\). For the corresponding witness,
\[
\frac{\Phi_\infty(x,d^{(i)})}
{\operatorname{OPT}(I_8,d^{(i)})}
\geq5.
\]
Therefore \(V(I_8)\geq5\). Together with (14), this proves
\[
\boxed{V(I_8)=5.}
\]
Under the definition in the question, multiplying every mass by a positive integer \(k\) and then normalizing returns the original masses:
\[
\frac{k\mu_p}{k\sum_r\mu_r}=\mu_p,
\qquad
\frac{k\nu_q}{k\sum_s\nu_s}=\nu_q.
\]
The support and rankings also remain unchanged. Thus replication leaves \(I\), and therefore \(V(I)\), unchanged.
In particular, every specified uniform replication of \(I_8\) has value \(5\).
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed value \(V(I_8)=5\), the exact characterization for arbitrary supported societies, and invariance under the specified replication. I found no major issue. There is one minor wording error involving strict preference.
The running-time bound is valid as stated, but it is not polynomial in the full input parameters when \(\tau\) varies. The output establishes neither polynomial-time solvability nor hardness for the general problem.
Necessity of (1) follows from the row sums and column capacities.
For sufficiency, the proposed network has total source capacity \(1\). Any cut crossing an agent–item edge has capacity at least \(2\). Otherwise, if its source-side agents are \(A\), its source-side items must contain \(N_E(A)\), giving the stated lower bound
\(1-\mu(A)+\nu(N_E(A))\).
Thus every cut has capacity at least \(1\), and max-flow min-cut applies.
Equation (2) correctly relates transport feasibility to a distance threshold. Attainment of the optimum also follows: there are finitely many agent–item distances, and the complete graph supports a feasible transport plan.
The equilateral pseudometric used to show \(W_{pq}\geq1\) is admissible: weak distance inequalities permit every prescribed strict ranking.
For positive optimum, normalization by \(T=\operatorname{OPT}(I,d)\) preserves all pseudometric and ranking constraints. This gives the upper bound in (4).
The zero-optimum case is handled correctly. A positive supported distance in such a pseudometric could be scaled arbitrarily while retaining optimum zero, forcing the corresponding edge weight to be infinite. If all supported weights are finite, the numerator must therefore be zero, and the prescribed ratio is \(1\).
The reverse inequality correctly uses a supported edge and any admissible pseudometric with optimum at most \(1\). Restricting attention to positive edge distances loses nothing because \(W_{pq}\geq1\).
Formula (5) then follows from (4) and threshold feasibility. Section 3 supplies finiteness; the finitely many edge weights ensure that the first feasible finite threshold is attained. The observation about deterministic mechanisms at a fixed instance is also valid under the task’s definition.
Every retained prefix graph forces optimum at most \(1\). Conversely, if optimum is at most \(1\), every row of \(E_1(d)\) is a ranking prefix. Each prefix is nonempty because every agent has positive mass and threshold feasibility requires that mass to be assigned. Distance ties cause no difficulty: all items at distance at most \(1\) are included.
The linear constraints describe exactly the permitted finite-valued pseudometrics subject to the selected threshold constraints. Unboundedness represents arbitrarily large finite distances; it does not require an infinite-valued pseudometric.
There are at most \(m^\tau\) prefix vectors and \(\tau m\) objectives per retained vector. Each linear program has polynomially many variables and constraints with rational coefficients. The additional factor \(\tau m\), rational max-flow computations, and sorting fit inside the stated polynomial factor.
Finite rational linear-program optima give rational finite edge weights. Since the minimizing threshold is one of those weights, rationality of \(V(I)\) follows.
This establishes the stated exact algorithm, not a polynomial-time algorithm for unrestricted \(\tau\).
The greedy-row comparison is valid. A surplus item has unused available capacity after the greedy allocation, so the agent’s mass has already been exhausted by that position. Every deficit item therefore precedes every surplus item.
The donor mass exists because the greedy allocation never exceeds the residual column capacity. Total deficit equals total surplus because both rows have the same total mass. The described redistribution preserves all remaining row and column sums.
Every moved edge satisfies the displayed triangle-inequality bound \(3C\), and every edge in the fixed greedy row has distance at most \(C\). Iterating for the first \(\tau-1\) rows gives \(3^{\tau-1}T\). The final row is forced by the remaining capacities.
The argument also covers \(\tau=1\) and \(T=0\). Thus (7) supplies the finiteness needed earlier.
The support of a feasible equal-mass transport satisfies Hall’s condition. Both vertex classes have cardinality \(n\), so Hall’s theorem yields a perfect matching in that support.
This matching has bottleneck no larger than the transport plan for every pseudometric. Conversely, a perfect matching defines a feasible transport plan. These two observations justify equality of the metric-specific optima and equation (8).
The cited discrete theorem is indeed a worst-case statement over instances. It does not, by itself, impose the same lower bound on the particular profile in this task. This reading agrees with [Theorem 4 and Appendix C of the cited paper](https://arxiv.org/html/2510.05460v1#A3). The submitted bounds for \(I_8\) are proved independently of that citation.
Rechecking the generating tree gives the listed distance sequence
\(5,9,12,13,14,15,19,19\).
The four ranking rows and their index-based tie resolutions are correct. In particular, every right-half agent ranks \(b_1\) before \(b_3\).
The second-item argument correctly uses two agents competing for one favorite item. The third-item argument correctly uses four agents competing for three internal items. Their triangle bounds give \(3T\) and \(5T\), respectively.
Both cases for the optimal recipient of \(b_8\) are valid. In the right-half case, the comparison between \(b_1\) and \(b_3\) justifies the needed bound irrespective of which favorite belongs to the selected left-half agent.
Matching (9) uses each item exactly once. Its eight edge bounds are correctly stated, and the zero-optimum case is explicitly covered.
Minor issue: “Every agent prefers its favorite item to its assigned item in \(M^\star\)” is false when that agent is assigned its favorite. Only a weak comparison is needed.
Minimum clarification: State that the assigned item is either the favorite itself or ranked below it, so the favorite’s distance is at most \(T\).
The branch placements define finite nonnegative pseudometrics, including the permitted colocations.
Rechecking the distances in the prescribed ranking orders gives exactly the three sequences stated in the output. These checks apply to either half and either favorite within that half. All ranking inequalities, including the fixed tie-breaking comparisons, hold.
The proposed bottleneck-\(1\) matching uses eight distinct items, and every assigned distance is exactly \(1\). The distinguished agent has distance at least \(1\) to every item, so splitting cannot reduce the transport optimum below \(1\).
Its distance to \(b_8\) is exactly \(5\). Every feasible plan must assign positive mass to \(b_8\) from some agent, so selecting that agent’s witness establishes the lower bound for every feasible transport plan. Combined with the upper bound, this proves \(V(I_8)=5\).
Under the task’s explicit definition, multiplying all masses by the same positive integer and normalizing restores the original masses. Supports and rankings remain unchanged. Therefore every specified replication has the same value.
No additional mathematical lemma or construction is required to make the conclusions verifiable.
⟨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.