Answer: The bound \(\operatorname{PoA}\leq 1+2(m-1)\gamma_m^*\) holds for every stated nonatomic instance.
Theorem 5 — class: algorithmic
Given rational type masses and a symmetric binary affinity matrix, compute the worst welfare ratio between any feasible allocation and a two-sided exchange-stable mass allocation, or decide for rational \(R\) whether that ratio exceeds \(R\). In particular, determine whether the ratio is at most \(1+2(m-1)\gamma_m^*\), the analogue of Theorem 5’s bound.
A society is given by its support: the list of \(\tau\) types with positive masses \(p_a\), each a binary rational; \(\tau\) is the support size, not the number of possible types. Mass is nonatomic and need not sum to one. State any running times in \(m,\tau,L\), where \(L\) is the total input bit length.
There are \(m\geq2\) houses with rational quotas \(q_h\geq2\), satisfying \(\sum_hq_h=\sum_ap_a\), and common desirabilities \(D_h\in\mathbb Z_{\geq0}\). Assume either all quotas are equal or all desirabilities are equal. Houses have zero utility.
The affinity matrix \(A\in\{0,1\}^{\tau\times\tau}\) is symmetric; diagonal entries describe affinity between distinct individuals of the same type. A feasible allocation is a real matrix \(x_{ah}\geq0\) with \(\sum_hx_{ah}=p_a\) and \(\sum_ax_{ah}=q_h\); there are no vacancies.
A type \(a\) individual's utility in house \(h\) is \(u_{ah}(x)=D_h+\sum_bA_{ab}x_{bh}\). Define two-sided exchange stability by infinitesimal equal-mass exchanges: no \(a,b,h\neq g\) with \(x_{ah}>0\) and \(x_{bg}>0\) satisfy \(u_{ag}(x)\geq u_{ah}(x)\) and \(u_{bh}(x)\geq u_{bg}(x)\), with at least one strict inequality. Houses always consent; indifferent exchanges do not block.
Define \(E=\frac12\sum_{a,b}A_{ab}p_ap_b>0\), \(E_{\mathrm{in}}(x)=\frac12\sum_h\sum_{a,b}A_{ab}x_{ah}x_{bh}\), \(W(x)=\sum_hq_hD_h+2E_{\mathrm{in}}(x)\), and \(\gamma_m^*=\max_{x\text{ feasible}}E_{\mathrm{in}}(x)/E\).
Let \(\operatorname{PoA}=\max_{x\text{ feasible}}W(x)/\inf_{x\text{ stable}}W(x)\), interpreting a zero denominator as \(+\infty\).
Does \(\operatorname{PoA}\leq1+2(m-1)\gamma_m^*\) hold for every such mass instance, or can this bound be violated?
For discrete individuals, binary affinities, integer quotas at least two, and nonnegative integer common desirabilities, the same bound holds when quotas or desirabilities are equal; a family asymptotically attains it. [Bodine-Baron et al.](https://arxiv.org/pdf/1104.0052)
No result settling this precise nonatomic exchange model was located.
The bound holds for every instance in the question:
\(\operatorname{PoA}\leq 1+2(m-1)\gamma_m^*.\)
Here is a direct proof for the specified nonatomic exchange rule. The analogous discrete statement is [Theorem 5 of Bodine-Baron et al.](https://arxiv.org/pdf/1104.0052).
Write \(x_h=(x_{ah})_{a=1}^{\tau}\), and define
\(B=\sum_hq_hD_h,\qquad I_h(x)=\frac12x_h^{\mathsf T}Ax_h,\qquad I(x)=\sum_hI_h(x)=E_{\mathrm{in}}(x).\)
For distinct houses, define \(C_{hg}(x)=x_h^{\mathsf T}Ax_g\). Symmetry of \(A\) gives \(C_{hg}=C_{gh}\). Since \(\sum_hx_h=p\), expanding the quadratic form gives
\(E=I(x)+\sum_{h<g}C_{hg}(x).\)
All these affinity quantities are nonnegative. Consequently, \(I(x)\leq E\).
Let \(P=\sum_ap_a=\sum_hq_h>0\). The allocation \(x_{ah}=p_aq_h/P\) is feasible. The feasible set is closed and bounded in \(\mathbb R^{\tau m}\), hence compact. Therefore the continuous function \(I\) attains its maximum. Moreover, at the proportional allocation,
\(\displaystyle I(x)=E\sum_h\left(\frac{q_h}{P}\right)^2>0.\)
Thus, writing \(\gamma=\gamma_m^*\), we have \(0<\gamma\leq1\), and optimal welfare is
\(W_{\max}=B+2\gamma E.\)
We next prove that every maximizer of \(I\) is stable. Suppose an allocation \(x\) admits a blocking exchange between type \(a\) in house \(h\) and type \(b\) in house \(g\). Set
\(s=\bigl(u_{ag}(x)-u_{ah}(x)\bigr)+\bigl(u_{bh}(x)-u_{bg}(x)\bigr)>0.\)
The two types must differ: if \(a=b\), the two gains are negatives of each other and cannot both be nonnegative with one strict.
Let \(t=e_a-e_b\), where \(e_a,e_b\) are standard basis vectors. For sufficiently small \(\varepsilon>0\), the exchange
\(x_h(\varepsilon)=x_h-\varepsilon t,\qquad x_g(\varepsilon)=x_g+\varepsilon t\)
is feasible because \(x_{ah}>0\) and \(x_{bg}>0\). All other columns remain fixed. The desirability terms cancel in the sum of gains, so
\(s=t^{\mathsf T}A(x_g-x_h).\)
Using symmetry of \(A\), exact expansion gives
\(I(x(\varepsilon))-I(x)=\varepsilon s+\varepsilon^2t^{\mathsf T}At.\)
Since \(s>0\), this expression is positive for sufficiently small positive \(\varepsilon\). Hence a maximizer cannot admit a blocking exchange. In particular, stable allocations exist.
Fix a stable allocation \(x\) and distinct houses \(h,g\). We claim that
\(C_{hg}(x)\leq 2\bigl(I_h(x)+I_g(x)\bigr)+R_{hg},\)
where
\(R_{hg}=\max\{q_h(D_h-D_g),\,q_g(D_g-D_h)\}.\)
To prove this, consider two exhaustive cases.
Case 1. Every type present in house \(h\) weakly prefers staying there:
\(u_{ag}(x)\leq u_{ah}(x)\quad\text{whenever }x_{ah}>0.\)
Multiply each inequality by \(x_{ah}\) and sum over types. This yields
\(q_h(D_g-D_h)+C_{hg}(x)-2I_h(x)\leq0,\)
and therefore
\(C_{hg}(x)\leq2I_h(x)+q_h(D_h-D_g).\)
Case 2. Some type \(a\) present in house \(h\) strictly prefers house \(g\):
\(u_{ag}(x)>u_{ah}(x).\)
For every type \(b\) with \(x_{bg}>0\), stability forces
\(u_{bh}(x)<u_{bg}(x).\)
Indeed, a weak preference in the opposite direction would combine with type \(a\)'s strict gain to form a blocking exchange. Multiplying these inequalities by \(x_{bg}\) and summing gives
\(q_g(D_h-D_g)+C_{hg}(x)-2I_g(x)<0.\)
In particular,
\(C_{hg}(x)\leq2I_g(x)+q_g(D_g-D_h).\)
In either case, nonnegativity of \(I_h,I_g\) proves the claimed pairwise bound.
Each \(I_h\) occurs in exactly \(m-1\) unordered house pairs. Thus the decomposition of \(E\) and the pairwise bound imply
\(\displaystyle E\leq(2m-1)I(x)+\sum_{h<g}R_{hg}.\)
We now check the two allowed hypotheses.
Equal desirabilities. If \(D_h=D\) for all houses, then \(R_{hg}=0\). Since \(B\geq0\),
\(\displaystyle \sum_{h<g}R_{hg}=0\leq(m-1)B.\)
Equal quotas. If \(q_h=q\) for all houses, then \(R_{hg}=q|D_h-D_g|\). Nonnegativity of the desirabilities gives \(|D_h-D_g|\leq D_h+D_g\). Consequently,
\(\displaystyle \sum_{h<g}R_{hg}\leq q\sum_{h<g}(D_h+D_g)=(m-1)q\sum_hD_h=(m-1)B.\)
Therefore, under either hypothesis, every stable allocation satisfies
\(E\leq(2m-1)I(x)+(m-1)B.\)
Set \(K=1+2(m-1)\gamma\). For any stable allocation, the preceding inequality gives
\(\displaystyle W_{\max}=B+2\gamma E\leq K B+2(2m-1)\gamma I(x).\)
Because \(\gamma\leq1\),
\((2m-1)\gamma\leq1+2(m-1)\gamma=K.\)
Using \(I(x)\geq0\), we obtain
\(W_{\max}\leq K\bigl(B+2I(x)\bigr)=K W(x).\)
This holds for every stable allocation. Taking the infimum therefore gives
\(\displaystyle \inf_{x\text{ stable}}W(x)\geq\frac{W_{\max}}{K}>0.\)
The strict positivity follows from \(E>0\) and \(\gamma>0\). Thus the zero-denominator convention never arises under the stated hypotheses, and division proves
\(\displaystyle \operatorname{PoA}\leq K=1+2(m-1)\gamma_m^*.\)
No attainment of the infimum over stable allocations is needed.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated nonatomic question. The bound holds under either of the two permitted hypotheses. No major or minor gaps were found.
The definitions of \(I_h\), \(I\), and \(C_{hg}\) match the task. Expanding \(p=\sum_hx_h\) and using symmetry gives exactly
\[
E=I(x)+\sum_{h<g}C_{hg}(x).
\]
Every summand is nonnegative because the allocation and affinity entries are nonnegative. Thus \(I(x)\leq E\).
The proportional allocation satisfies both sets of marginal constraints. The feasible set is nonempty, closed, and bounded: each coordinate lies between zero and \(p_a\). The continuous quadratic function \(I\) therefore attains its maximum.
The computation at the proportional allocation is correct:
\[
I(x)=E\sum_h(q_h/P)^2>0.
\]
Consequently, \(0<\gamma\leq1\). Since the desirability contribution \(B\) is fixed by the house quotas, \(W_{\max}=B+2\gamma E\) follows.
The argument excludes exchanges with \(a=b\) correctly: their two utility differences are negatives of each other, so they cannot satisfy the blocking condition.
For distinct types, the proposed exchange preserves every row and column sum. Its only decreased coordinates are \(x_{ah}\) and \(x_{bg}\), both strictly positive. Thus it is feasible for sufficiently small positive \(\varepsilon\).
The common desirability terms cancel in the sum of the two gains, giving
\[
s=t^{\mathsf T}A(x_g-x_h)>0.
\]
The quadratic expansion is correct, including its coefficient:
\[
I(x(\varepsilon))-I(x)
=\varepsilon s+\varepsilon^2t^{\mathsf T}At.
\]
Although the quadratic coefficient can be negative, the positive linear coefficient guarantees an increase for sufficiently small positive \(\varepsilon\). Hence every maximizer is stable, and the set of stable allocations is nonempty.
This reasoning uses precisely the task’s infinitesimal exchange definition. It also accommodates diagonal affinities without modifying the utility formula.
The two cases are exhaustive: either every type present in \(h\) weakly prefers staying, or some present type strictly prefers \(g\).
In Case 1, multiplying by the masses in \(h\) yields the stated inequality:
\[
C_{hg}\leq2I_h+q_h(D_h-D_g).
\]
In Case 2, the strict gain of the selected type forces every type present in \(g\) to strictly prefer staying there. A weak preference for moving to \(h\) would already form a blocking exchange. This includes the possibility that the same type appears in both houses.
Because \(q_g>0\), at least one type is present in \(g\); summing the mass-weighted strict inequalities therefore remains strict. The resulting bound
\[
C_{hg}<2I_g+q_g(D_g-D_h)
\]
justifies the weaker inequality used in the proof.
In either case, the relevant desirability term is at most \(R_{hg}\), and the omitted internal-affinity term is nonnegative. Thus the claimed pairwise bound follows.
Each \(I_h\) appears in exactly \(m-1\) unordered pairs. Combining the pairwise bounds with the decomposition gives
\[
E\leq(2m-1)I+\sum_{h<g}R_{hg}.
\]
With equal desirabilities, every \(R_{hg}\) vanishes.
With equal quotas,
\[
R_{hg}=q|D_h-D_g|\leq q(D_h+D_g),
\]
where nonnegative desirabilities justify the inequality. Counting each desirability in \(m-1\) pairs gives
\[
\sum_{h<g}R_{hg}\leq(m-1)B.
\]
Thus the asserted inequality holds for every stable allocation under either hypothesis.
Multiplication by \(2\gamma>0\) and addition of \(B\) correctly produce
\[
W_{\max}\leq KB+2(2m-1)\gamma I.
\]
The coefficient comparison is valid because
\[
K-(2m-1)\gamma=1-\gamma\geq0.
\]
Since \(I\geq0\), this proves \(W_{\max}\leq KW(x)\) for every stable allocation.
The stable set is nonempty by Section 1, and this uniform inequality implies
\[
\inf_{x\text{ stable}}W(x)\geq W_{\max}/K>0.
\]
No attainment or closedness of the stable set is required. The division establishing the claimed price-of-anarchy bound is therefore justified.
The discrete comparison matches [Theorem 5 of Bodine-Baron et al.](https://arxiv.org/pdf/1104.0052). It is contextual rather than an invoked theorem in the nonatomic proof, so no transfer between the two models is assumed.
No repair or additional clarification is needed. The prover supplies no algorithm or running-time claim, so the task’s running-time convention introduces no missing obligation. The result is a welfare bound, not a computational-complexity classification.
⟨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.