Answer: Every input has largest achievable factor \(\alpha^*=1\). Payments attaining it can be computed exactly in time polynomial in \(m,\tau,L\) by solving the grand-coalition matching LP's dual.
Theorem 14 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe imputation $c$ is in the ${2 \over 3}$-approximate core of the general graph matching game.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and a graph of compatible type pairs with nonnegative rational surpluses \(w_e\), define \(P(q)\) for each coalition mass vector \(0\le q\le\mu\) as the maximum matching surplus. A matching mass \(x_e\) uses one unit of each endpoint type for a cross-type edge and two units of type \(t\) for a loop at \(t\). Find the largest \(\alpha\in[0,1]\) and nonnegative per-agent type payments \(c_t\) such that \(\sum_t\mu_t c_t\le P(\mu)\) and \(\sum_tq_tc_t\ge\alpha P(q)\) for every \(q\le\mu\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
An undirected compatibility graph on \(T\) has \(m\) edges, possibly including loops, with binary-rational surpluses \(w_e\ge0\). Let \(L\) be the total input bit length.
For every real coalition vector \(0\le q\le\mu\), define \(P(q)=\max\{\sum_e w_ex_e:x_e\ge0,\ \sum_{e=\{t,s\},\ s\ne t}x_e+2x_{\{t,t\}}\le q_t\ \text{for every }t\}\), with absent loop variables interpreted as zero. Unmatched mass generates no surplus; loops match two distinct individuals of the same type.
A nonnegative real payment vector \(c\) belongs to the \(\alpha\)-approximate core, for \(\alpha\in[0,1]\), when \(\sum_t\mu_tc_t\le P(\mu)\) and \(\sum_tq_tc_t\ge\alpha P(q)\) for every real \(0\le q\le\mu\). Payments are per individual and constant within each type.
What is the largest achievable approximate-core factor \(\alpha\) for each input, and can payments attaining that factor be computed in time polynomial in \(m,\tau,L\)?
For finite general graph matching games, a \(2/3\)-approximate-core allocation is computable in polynomial time, and the universal factor \(2/3\) is tight. [Vazirani](https://ics.uci.edu/~vazirani/AppCore.pdf)
For a related finite-type continuum roommate model with transferable utility, stable matching existence is established; this is an existence result rather than a binary-input complexity classification for the problem above. [Chiappori–Galichon–Salanié](https://www.ifo.de/DocDL/cesifo1_wp4676.pdf)
For every input, the largest achievable factor is \(\alpha^*=1\). Payments attaining it can be computed exactly, as rational numbers, in time polynomial in \(m,\tau,L\).
This holds for arbitrary compatibility graphs, including odd cycles and loops.
Let \(A\) be the \(\tau\times m\) incidence matrix: a nonloop edge has coefficient \(1\) at each endpoint, and a loop at \(t\) has coefficient \(2\) at \(t\). Thus
\(P(q)=\max\{w^\mathsf{T}x:x\ge0,\ Ax\le q\}\).
This maximum exists. Indeed, the feasible set contains \(0\), and every feasible \(x\) satisfies
\(2\sum_e x_e=\sum_t(Ax)_t\le\sum_tq_t\le1\).
Consequently, the feasible set is closed and bounded.
Lemma. For \(c\ge0\) and \(\alpha\in[0,1]\), the inequalities
\(q^\mathsf{T}c\ge\alpha P(q)\quad\text{for every }0\le q\le\mu\)
hold if and only if
\(c_t+c_s\ge\alpha w_{\{t,s\}}\quad\text{for every nonloop edge }\{t,s\}\),
and
\(2c_t\ge\alpha w_{\{t,t\}}\quad\text{for every loop }\{t,t\}\).
Proof of necessity. For a nonloop edge \(\{t,s\}\), take \(\delta=\min\{\mu_t,\mu_s\}>0\), and let \(q_t=q_s=\delta\), with all other coordinates zero. Matching mass \(\delta\) along this edge is feasible, so \(P(q)\ge\delta w_{\{t,s\}}\). The coalition inequality implies
\(\delta(c_t+c_s)\ge\alpha P(q)\ge\alpha\delta w_{\{t,s\}}\).
Dividing by \(\delta\) gives the required edge inequality.
For a loop at \(t\), take \(\delta=\mu_t/2>0\), let \(q_t=2\delta\), and set all other coordinates to zero. Matching mass \(\delta\) along the loop gives \(P(q)\ge\delta w_{\{t,t\}}\), hence
\(2\delta c_t\ge\alpha\delta w_{\{t,t\}}\).
Again, divide by \(\delta\). Positivity of every support mass justifies both divisions.
Proof of sufficiency. The edge inequalities say \(A^\mathsf{T}c\ge\alpha w\). For any coalition \(q\) and any feasible matching \(x\),
\(q^\mathsf{T}c\ge(Ax)^\mathsf{T}c=x^\mathsf{T}A^\mathsf{T}c\ge\alpha w^\mathsf{T}x\).
The first inequality uses \(Ax\le q\) and \(c\ge0\); the last uses \(x\ge0\). Maximizing over feasible \(x\) proves the coalition inequality. \(\square\)
Consider the grand-coalition primal and its dual:
\(\displaystyle P(\mu)=\max\{w^\mathsf{T}x:Ax\le\mu,\ x\ge0\}\),
\(\displaystyle D(\mu)=\min\{\mu^\mathsf{T}c:A^\mathsf{T}c\ge w,\ c\ge0\}\).
The primal is feasible and bounded, as proved above. The dual is feasible: setting every coordinate to \(W=\max(\{0\}\cup\{w_e:e\in E\})\) satisfies every edge and loop inequality.
The strong-duality theorem for finite linear programs therefore supplies an optimal dual vector \(c^*\) satisfying
\(\mu^\mathsf{T}c^*=D(\mu)=P(\mu)\).
Apply the lemma with \(\alpha=1\). Since \(A^\mathsf{T}c^*\ge w\) and \(c^*\ge0\),
\(q^\mathsf{T}c^*\ge P(q)\quad\text{for every }0\le q\le\mu\).
Thus \(c^*\) satisfies both the budget constraint and every coalition constraint. It belongs to the full core. Since the permitted factors satisfy \(\alpha\le1\), this proves \(\alpha^*=1\).
Moreover, the full-core payment vectors are exactly the optimal dual solutions: the lemma makes any full-core vector dual feasible, while weak duality and the budget constraint force
\(P(\mu)\le\mu^\mathsf{T}c\le P(\mu)\).
If there are no edges, or all surpluses vanish, \(c=0\) attains the same factor.
The algorithm is to solve the displayed dual LP and return an optimal vector.
It has \(\tau\) variables, \(m\) edge inequalities, and \(\tau\) nonnegativity constraints. Each edge inequality has at most two nonzero coefficients, all belonging to \(\{1,2\}\). The objective coefficients are the input masses, and the right-hand sides are the input surpluses. Even a dense encoding therefore has length polynomial in \(m,\tau,L\).
The standard polynomial-time theorem for rational linear programming computes an exact rational optimum for a feasible rational LP with finite optimum, with running time polynomial in its binary encoding length. Both hypotheses were checked above. Exact rational LP computation and its bit-complexity foundations are discussed in [Gleixner–Steffy](https://arxiv.org/pdf/1912.12820).
Hence the payment vector is computable in the requested polynomial time. No expansion into individual agents or enumeration of coalition vectors is needed.
In [Vazirani’s finite matching game](https://ics.uci.edu/~vazirani/AppCore.pdf), coalition values come from integral matchings. Here, the real matching LP itself defines coalition value, so its optimal dual payments fit the grand-coalition budget exactly.
For example, take three types of mass \(1/3\), forming a triangle with every edge surplus equal to \(1\). Setting every edge variable to \(1/6\) is feasible and yields \(P(\mu)=1/2\); the general bound \(2\sum_e x_e\le1\) proves optimality. Payments \(c_t=1/2\) satisfy every edge inequality and have total cost \(1/2\). Thus even the triangle admits the full core in this model.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly: every input has largest achievable factor \(\alpha^*=1\), and attaining payments can be computed exactly in polynomial time. No major or minor mathematical issues were found.
The incidence matrix correctly represents the stated constraints: each nonloop column has two entries equal to \(1\), and each loop column has one entry equal to \(2\). Consequently,
\[
2\sum_e x_e=\sum_t(Ax)_t.
\]
The displayed bound follows from \(Ax\le q\le\mu\) and \(\sum_t\mu_t=1\).
Feasibility, closedness, and boundedness are correctly established. Since the objective is continuous and the dimension is finite, the maximum exists. The argument also covers an empty edge set.
Assessment: Correct.
Nonloop necessity. The selected coalition lies within the coordinatewise bounds because \(\delta=\min\{\mu_t,\mu_s\}\). The matching supported only on the selected edge is feasible. Multiplication of \(P(q)\ge\delta w_{\{t,s\}}\) by \(\alpha\) preserves the inequality because \(\alpha\ge0\). Division by \(\delta\) is justified by positive support masses.
Loop necessity. Taking \(\delta=\mu_t/2\) makes the selected coalition admissible and permits loop matching mass \(\delta\), which consumes \(2\delta\) at that type. The factor \(2\) and the division are correct.
Other available edges or loops do not invalidate either argument: the proof uses only a feasible matching to obtain a lower bound on \(P(q)\).
Sufficiency. Every inequality in
\[
q^\mathsf{T}c\ge(Ax)^\mathsf{T}c
=x^\mathsf{T}A^\mathsf{T}c
\ge\alpha w^\mathsf{T}x
\]
has its required sign hypothesis explicitly supplied. Maximizing over feasible \(x\) proves the assertion for every real coalition vector, including \(q=0\).
Assessment: Correct, with the quantifiers and domain restrictions fully respected.
The displayed minimization problem is precisely the dual of the grand-coalition primal, with the correct inequality directions and nonnegativity restrictions.
The invoked finite-dimensional LP strong-duality theorem guarantees attained equal optimal values for a feasible primal with finite optimal value. Those hypotheses are established. The proposed constant dual vector is also feasible: every column of \(A\) has sum \(2\), so its edge constraint has left side \(2W\ge w_e\).
An optimal dual vector therefore satisfies nonnegativity, the full coalition inequalities by the lemma, and the budget constraint with equality. This proves attainment of \(\alpha=1\). The task restricts \(\alpha\) to \([0,1]\), so no additional upper-bound argument is needed.
The characterization of full-core payments as exactly the optimal dual solutions follows correctly from the lemma, weak duality, and the budget constraint.
Assessment: Correct.
The dual has the stated number of variables and constraints. Its matrix entries have constant encoding length, and its remaining numerical data are input rationals. Its binary encoding length is therefore polynomial in \(m,\tau,L\), even when represented densely.
The rational LP theorem is stated at the required level: a feasible rational LP with finite optimal value admits computation of an exact rational optimal solution in polynomial time in its binary encoding length. Here, feasibility is explicit, and the objective is bounded below by zero because \(\mu,c\ge0\); Section 2 also establishes an attained finite optimum.
The cited [Gleixner–Steffy paper, Section 1.3](https://arxiv.org/pdf/1912.12820) explicitly discusses exact polynomial-time algorithms for rational LPs. Thus the citation supports the computational claim. The prover does not confuse approximate numerical optimization with exact rational output.
Assessment: Correct. The algorithm returns a payment vector, rather than merely its objective value.
The zero-surplus and empty-edge cases are correctly handled by \(c=0\), with \(\alpha=1\) still allowed and attained. Isolated types and single-type inputs introduce no missing constraints or exceptions.
For the triangle example, each type uses mass \(1/6+1/6=1/3\), the objective is \(3(1/6)=1/2\), and the payment cost is \(3(1/3)(1/2)=1/2\). Every edge payment sum is \(1\). All calculations are correct.
The comparison with the finite matching game accurately identifies its integral matching valuation, as defined in [Vazirani’s paper](https://ics.uci.edu/~vazirani/AppCore.pdf). That comparison is explanatory; the proof of the continuous result is independent of it.
Assessment: Correct.
No repair or additional clarification is required.
⟨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.