Answer: A deterministic ordinal \(2\)-approximation exists and runs in time polynomial in \(m=\tau\), \(L\), and \(\log(b+1)\).
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any ABC System on graph $G$, where $c = n$ and $\mathcal{A}$ = all subgraphs of $G$, Ordinal Greedy always constructs a solution within a factor of 2 of the optimal solution. This bound is tight.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu\), an integer degree bound \(b\), and ordinal rankings of partner types, output a symmetric link-mass matrix \(x\) using only those rankings. Require \(x_{tu}\ge0\), \(x_{tu}=x_{ut}\), \(x_{tt}\le\mu_t/2\), and \(2x_{tt}+\sum_{u\ne t}x_{tu}\le b\mu_t\) for every \(t\). For every symmetric nonnegative type-level utility matrix \(w\) consistent with the rankings, require \(W_w(x)\ge\frac12\max_{y\text{ feasible}}W_w(y)\), where \(W_w(x)=\sum_{t<u}w_{tu}x_{tu}+\sum_t w_{tt}x_{tt}\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(m=\tau\) is the number of partner types; \(\tau\) denotes support size, not the number of possible rankings. Let \(L\) be the total input bit length.
The input also gives a binary integer \(b\geq1\) and, for each \(t\), a strict ranking \(\succ_t\) of all types in \(T\), including \(t\). A consistent utility matrix is any symmetric \(w\in\mathbb{R}_{\geq0}^{T\times T}\) satisfying \(u\succ_t v\Rightarrow w_{tu}\geq w_{tv}\); utilities need not be normalized or metric.
A feasible link-mass matrix satisfies \(x_{tu}=x_{ut}\geq0\), \(x_{tt}\leq\mu_t/2\), and \(2x_{tt}+\sum_{u\ne t}x_{tu}\leq b\mu_t\) for every \(t\). Diagonal entries represent links between distinct individuals of the same type. These are the entire feasibility constraints.
Define \(W_w(x)=\sum_{t<u}w_{tu}x_{tu}+\sum_t w_{tt}x_{tt}\), using any fixed ordering of \(T\). The required output is a rational feasible matrix \(x\), chosen from the masses, degree bound, and rankings alone, satisfying \(W_w(x)\geq\tfrac12\max_{y\text{ feasible}}W_w(y)\) simultaneously for every consistent \(w\).
Does a deterministic ordinal algorithm achieve this \(2\)-approximation for every input in time polynomial in \(m,\tau,L\), and \(\log(b+1)\), or is such a guarantee impossible or computationally intractable?
For finite agents with symmetric nonnegative utilities, Ordinal Greedy gives a polynomial-time \(2\)-approximation for maximum-weight \(b\)-matching; its approximation bound is tight ([source](https://arxiv.org/html/1711.10588)).
Fractional matching welfare optimization under ordinal or cardinal stability has been studied, but imposes different requirements ([source](https://www.ijcai.org/proceedings/2021/13)). No result settling the exact mass formulation above was located.
Yes. A deterministic ordinal algorithm computes a rational feasible matrix satisfying the required simultaneous \(2\)-approximation in time polynomial in \(\tau=m\), \(L\), and \(\log(b+1)\).
The finite-agent [Ordinal Greedy theorem](https://arxiv.org/html/1711.10588) establishes a related guarantee. The proof below independently handles the stated mass constraints, including diagonal links, and uses no population expansion.
Let \(E=\{\{t,u\}:t,u\in T\}\), including diagonal edges \(\{t,t\}\). We identify a symmetric matrix with its coordinates indexed by \(E\). Write \(w_e=w_{tu}\) for \(e=\{t,u\}\).
Construct a directed comparison graph \(H\) whose vertices are the edges in \(E\). For every type \(t\) and every pair \(u\succ_t v\), add the arc
\[ \{t,u\}\longrightarrow\{t,v\}. \]
Every consistent utility matrix satisfies \(w_e\geq w_f\) along each arc \(e\longrightarrow f\), and therefore along every directed path.
Consequently, all edges in a strongly connected component of \(H\) have equal weight under every consistent utility matrix: paths in both directions imply both inequalities.
Contract the strongly connected components. The resulting graph is acyclic. Choose a topological order of its components, listing each component’s edges consecutively. Resolve every choice deterministically using the input ordering of types. Denote the resulting edge order by \(e_1,\ldots,e_N\), where \(N=\tau(\tau+1)/2\).
Ordering lemma. If two distinct edges \(e,f\) share a type and \(e\) precedes \(f\), then \(w_e\geq w_f\) for every consistent \(w\).
Proof. The shared type’s strict ranking supplies an arc in one direction between \(e\) and \(f\). If they lie in the same strongly connected component, their weights are equal. Otherwise, an arc \(f\longrightarrow e\) would force \(f\)’s component to precede \(e\)’s component, contrary to the chosen order. Hence the arc is \(e\longrightarrow f\), which implies \(w_e\geq w_f\). \(\square\)
This lemma concerns incident edges; the algorithm does not require comparisons between disjoint edges.
For a nonnegative edge vector \(v\), define its degree usage at \(t\) by
\[ d_t(v)=2v_{tt}+\sum_{u\ne t}v_{tu}, \]
and put \(c_t=b\mu_t\).
Initialize \(x=0\). Process the edges in the order constructed above. Before processing an edge, let \(r_t=c_t-d_t(x)\) be the remaining degree capacity.
For an off-diagonal edge \(e=\{t,u\}\), increase its coordinate by
\[ \delta=\min\{r_t,r_u\}. \]
For a diagonal edge \(e=\{t,t\}\), increase its coordinate by
\[ \delta=\min\{r_t/2,\ \mu_t/2-x_{tt}\}. \]
Thus each coordinate receives the largest feasible increase at its processing step. Every increase preserves nonnegativity, all degree bounds, and all diagonal bounds. The final matrix is therefore feasible.
The entire algorithm depends only on masses, rankings, \(b\), and deterministic tie-breaking.
For an edge \(e\), let \(A_{te}\) denote its coefficient in \(d_t\). Thus an off-diagonal edge has coefficient \(1\) at each endpoint, while a diagonal edge has coefficient \(2\) at its single endpoint. In either case,
\[ \sum_{t\in T}A_{te}=2. \]
Fix any consistent utility matrix \(w\). Suppose that, immediately before processing \(e\), a nonnegative benchmark vector \(z\) satisfies:
Let \(\delta\) be the algorithm’s increase on \(e\), and set \(a=z_e\).
Because \(x+z\) is feasible, \(x+a\mathbf 1_e\) is feasible: deleting other nonnegative benchmark coordinates cannot violate an upper bound. Since \(\delta\) is the largest feasible increase on \(e\), we have \(a\leq\delta\).
Set
\[ x'=x+\delta\mathbf 1_e, \qquad \widehat z=z-a\mathbf 1_e. \]
In particular, \(\widehat z_e=0\). Relative to \(x+z\), the degree usage of \(x'+\widehat z\) increases at type \(t\) by \(A_{te}(\delta-a)\). Its degree excess therefore satisfies
\[ D_t:=\max\{0,d_t(x'+\widehat z)-c_t\} \leq A_{te}(\delta-a). \]
Only endpoints of \(e\) can have positive excess.
We now restore the degree bounds by deleting benchmark mass. Process the endpoints of \(e\) one at a time. If the current benchmark is \(\widetilde z\), the current excess at \(t\) is
\[ D=\max\{0,d_t(x'+\widetilde z)-c_t\}. \]
Since \(x'\) itself is feasible, \(D\leq d_t(\widetilde z)\). Thus enough incident benchmark mass exists to remove exactly \(D\) units of degree usage. This can be done by reducing incident coordinates, splitting the last reduction if necessary.
Every positive incidence coefficient is either \(1\) or \(2\). Hence removing \(D\) units of degree usage deletes at most \(D\) units of edge mass. Deletions cannot increase any other degree usage, so the total additional edge mass deleted is at most
\[ \sum_t D_t \leq \sum_t A_{te}(\delta-a) =2(\delta-a). \]
Let \(z'\) be the resulting benchmark. Then \(x'+z'\) is feasible. Indeed, the degree bounds have been restored; the diagonal bound on \(e\), if applicable, holds because \(x'\) is feasible and \(z'_e=0\); all other diagonal coordinates of \(x'+z'\) have only decreased relative to \(x+z\).
Also, \(z'\) vanishes on every processed edge, including \(e\).
To bound the welfare lost, observe that every additional deleted coordinate \(f\) is incident to an endpoint of \(e\). By the assumed invariant, a positive such coordinate belongs to an unprocessed edge. The ordering lemma therefore gives \(w_f\leq w_e\). Including the initial deletion of \(a\) units on \(e\), we obtain
\[ W_w(z)-W_w(z') \leq w_e\bigl(a+2(\delta-a)\bigr) \leq 2w_e\delta. \]
This proves the exchange lemma. In particular, a diagonal increase of \(\delta\) may require deleting up to \(2\delta\) units of off-diagonal benchmark mass, and that cost is already covered by the bound.
The feasible region is nonempty because it contains zero. It is closed and bounded: every off-diagonal coordinate satisfies \(y_{tu}\leq b\mu_t\), and every diagonal coordinate satisfies \(y_{tt}\leq\mu_t/2\). Thus every fixed \(w\) has an optimal feasible solution \(y\).
Initialize the benchmark with \(z=y\). Initially \(x+z=y\) is feasible, and there are no processed edges. Apply the exchange lemma at every algorithmic step.
After the final step, every benchmark coordinate is zero. Summing the welfare losses gives
\[ W_w(y) \leq 2\sum_{i=1}^{N}w_{e_i}\delta_i =2W_w(x). \]
Therefore,
\[ W_w(x)\geq \tfrac12\max_{y\text{ feasible}}W_w(y). \]
The utility matrix \(w\) was arbitrary, while the algorithm’s output \(x\) was determined without consulting it. Consequently, this single output satisfies the inequality simultaneously for every consistent \(w\).
The comparison graph has \(\tau(\tau+1)/2\) vertices and at most \(\tau\binom{\tau}{2}\) arcs. Constructing it, finding its strongly connected components, and ordering them require polynomial time. The greedy phase processes exactly \(\tau(\tau+1)/2\) edges; its iteration count is independent of \(b\).
For the bit complexity, write each input mass as \(\mu_t=p_t/q_t\), and let \(D=\prod_t q_t\). The bit length of \(D\) is at most the total bit length of the input denominators, hence is \(O(L)\).
Initially, all capacities and diagonal bounds have denominators dividing \(2D\). The algorithm uses addition, subtraction, comparison, and division by \(2\). Division by \(2\) occurs only when processing a diagonal edge, so it occurs at most \(\tau\) times. Inductively, every generated rational has denominator dividing
\[ Q=2^{\tau+1}D. \]
All coordinate values and remaining degree capacities lie between \(0\) and \(b\). Their numerators therefore have bit length \(O(L+\tau+\log(b+1))\). Exact arithmetic and comparisons consequently take polynomial time, and the output has polynomial bit length.
Thus the required deterministic ordinal \(2\)-approximation exists in precisely the requested encoding model.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The algorithm addresses the exact mass formulation, and its approximation and polynomial-time guarantees are rigorous. I found no major or minor mathematical issues.
Every arc represents an inequality required by consistency. Following a directed path preserves that inequality, so edges in a strongly connected component have equal weights for every consistent utility matrix.
Two distinct edges sharing a type correspond to two distinct partners in that type’s strict ranking, including when one edge is diagonal. Thus there is a direct comparison arc between them. If they belong to different components, the topological order respects that arc; if they belong to the same component, their weights are equal. Consequently, an earlier edge has weight at least that of any later incident edge.
The argument correctly avoids assuming a global ordering by weight: weights of disjoint edges need not be comparable.
An off-diagonal coordinate consumes one unit of degree capacity at each endpoint and has no separate upper bound. Its largest feasible increase is therefore \(\delta=\min\{r_t,r_u\}\).
A diagonal coordinate consumes two units of degree capacity and is also bounded by \(\mu_t/2\). Its largest feasible increase is therefore \(\delta=\min\{r_t/2,\mu_t/2-x_{tt}\}\).
Residual capacities and residual diagonal bounds are nonnegative because the current vector is feasible. Each update preserves all constraints. Processing every edge exactly once also ensures that its coordinate is zero before its update.
From feasibility of \(x+z\), deleting all benchmark coordinates except \(z_e=a\) leaves \(x+a\mathbf 1_e\) feasible. Maximality of the greedy increase gives \(0\leq a\leq\delta\).
Replacing this benchmark mass with the algorithm’s increase changes degree usage at type \(t\) by exactly \(A_{te}(\delta-a)\). Since the original combined vector was feasible, its resulting excess satisfies
\[
D_t\leq A_{te}(\delta-a).
\]
Only endpoints of the processed edge can acquire excess. The coefficient sum is two for both off-diagonal and diagonal edges, so the calculation includes diagonals correctly.
At an endpoint with current excess \(D\), feasibility of \(x'\) implies \(D\leq d_t(\widetilde z)\). There is therefore enough incident benchmark degree usage to remove exactly that excess. Fractional coordinates allow the last reduction to be split as stated.
Every positive incidence coefficient is at least one, so removing \(D\) units of degree usage deletes at most \(D\) units of edge mass. Sequential deletions can only decrease excess at other endpoints. Hence each endpoint’s excess when processed is at most its initial \(D_t\), and total additional deleted mass is at most
\[
\sum_t D_t\leq 2(\delta-a).
\]
The diagonal bounds also remain valid. On the processed diagonal, the benchmark coordinate has been removed and the algorithm’s coordinate is feasible. Every other diagonal coordinate has only decreased relative to the initially feasible combined vector. No additional feasibility constraint from the task is omitted.
Previously processed benchmark coordinates are zero. After removing \(z_e\), every positive coordinate subsequently deleted is therefore on a later edge incident to an endpoint of \(e\). The ordering lemma gives \(w_f\leq w_e\) for every such coordinate.
Including the initial deletion on \(e\), the loss is bounded by
\[
W_w(z)-W_w(z')
\leq w_e\bigl(a+2(\delta-a)\bigr)
=w_e(2\delta-a)
\leq 2w_e\delta.
\]
The final inequality uses precisely the stated nonnegativity of weights and benchmark mass. It remains valid for zero weights and zero greedy increases.
The feasible region is nonempty, closed, and bounded in finite dimension. The coordinate bounds stated in the proof suffice for boundedness. Thus the continuous linear objective attains its maximum for every fixed consistent real utility matrix.
Starting with an optimal benchmark satisfies both exchange invariants. Each exchange preserves combined feasibility and makes the benchmark zero on every processed edge. After all edges have been processed, the benchmark is zero. Telescoping the losses yields
\[
W_w(y)\leq 2\sum_i w_{e_i}\delta_i=2W_w(x).
\]
Although the benchmark and its deletions may depend on \(w\), the algorithm’s output does not. Fixing an arbitrary consistent \(w\) for the analysis therefore proves the inequality for the same output simultaneously over all consistent matrices. There is no quantifier gap.
The graph has \(\tau(\tau+1)/2\) vertices and at most \(\tau\binom{\tau}{2}\) arcs. Its construction, strongly connected component decomposition, and topological ordering take polynomial time. Deterministic choices can use the specified input ordering.
The denominator product \(D\) has bit length bounded by the total denominator encoding length. Initial capacities and diagonal bounds have denominators dividing \(2D\). Addition, subtraction, and selection by minimum introduce no new denominator factors; halving can introduce only a factor of two. There are at most \(\tau\) diagonal halvings. Thus the common denominator bound \(Q=2^{\tau+1}D\) is valid.
Since \(\mu_t\leq1\), coordinate values and residual capacities are bounded by \(b\). Their numerators consequently have the claimed polynomial bit length. Exact rational arithmetic, comparisons, and output encoding are polynomial in \(\tau\), \(L\), and \(\log(b+1)\). The algorithm performs no iteration proportional to the numerical value of \(b\).
The cited source states the related factor-two guarantee for maximum-weight finite \(b\)-matching. [Ordinal Greedy source](https://arxiv.org/html/1711.10588). The submitted argument independently proves the mass result, so it does not require transferring that theorem to fractional masses or diagonal links.
The single-type case, diagonal saturation, unused degree capacity, zero utility matrices, and ranking cycles are all covered by the written argument. No repair or additional clarification is needed.
⟨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.