d4-conf-sagt-2012-0020 (d4-conf-sagt-2012-0020)

Given a finite \(\omega\)-sparse template \(H=(U,F)\), with \(\tau=|U|\) and maximum matching size \(\nu(H)\), consider a continuum of copies indexed by \(r\in[0,1]\), with one agent of each role \(u\in U\) in each copy and bargaining edges between roles in \(F\) within each copy. Find measurable payoffs \(x_u(r)\ge 0\) and measurable edge-deletion sets \(B_{uv}\subseteq[0,1]\) such that \(\frac{1}{\tau}\sum_{u\in U}\int_0^1 x_u(r)\,dr\le \frac{\nu(H)}{\tau}\) and \(x_u(r)+x_v(r)\ge 1\) for almost every \(r\notin B_{uv}\), while minimizing \(\frac{1}{\tau}\sum_{uv\in F}\operatorname{Leb}(B_{uv})\). Give an algorithm whose objective is at most \(8\omega+2\) times the optimum.

Input is a finite simple undirected graph \(H=(U,F)\), with \(\tau=|U|\ge 1\), \(m=|F|\), and a binary rational \(\omega\ge 1\), promised to satisfy \(|F(H[S])|\le\omega|S|\) for every \(S\subseteq U\). Let \(\nu(H)\) be its maximum matching size.
A society is given by its support: the list of its \(\tau\) types with positive binary rational masses; \(\tau\) is the support size, not the number of possible types. Here the types are the roles \(u\in U\), each of mass \(1/\tau\), so total mass is one. Let \(L\) be the total input bit length.
Agents are indexed by \((u,r)\), with \(r\in[0,1]\); an edge \(uv\in F\) connects only \((u,r)\) and \((v,r)\), and has unit value.
A feasible solution consists of nonnegative Lebesgue-measurable payoffs \(x_u(r)\) and measurable deletion sets \(B_{uv}\subseteq[0,1]\), satisfying \(\frac1\tau\sum_{u\in U}\int_0^1x_u(r)\,dr\le\frac{\nu(H)}\tau\) and \(x_u(r)+x_v(r)\ge1\) for almost every \(r\notin B_{uv}\), for every \(uv\in F\). The budget is imposed only on the integral across copies.
Its cost is \(C(B)=\frac1\tau\sum_{uv\in F}\operatorname{Leb}(B_{uv})\); define \(\mathrm{OPT}\) as the infimum over all measurable feasible solutions. Computational solutions are represented by a finite common interval partition with rational endpoints, rational constant payoffs, and constant deletion membership on each interval.

Does this problem admit an algorithm, polynomial in \(m,\tau,L\), that returns a feasible solution with \(C(B)\le(8\omega+2)\mathrm{OPT}\), or is achieving this approximation guarantee NP-hard?

For the discrete problem, a blocking set \(B\subseteq F\) permits nonnegative payoffs with \(\sum_u x_u\le\nu(H)\) and \(x_u+x_v\ge1\) on every undeleted edge; a polynomial-time \((8\omega+2)\)-approximation is known on \(\omega\)-sparse graphs ([source](https://cs.uwaterloo.ca/~klarson/papers/nwbg-sagt.pdf)).
No result settling this precise continuum approximation question was located in the literature search.

1. Result

The problem admits a polynomial-time \((8\omega+2)\)-approximation. A solution constant across all copies suffices. The key is that the cited discrete algorithm has a guarantee relative to a linear relaxation, whose optimum also lower-bounds the continuum optimum.

2. A lower bound for every measurable solution

Write \(k=\nu(H)\). Define the following finite linear program, with optimum \(\lambda(H,k)\):

\[ \begin{aligned} \text{minimize}\quad & \sum_{uv\in F}z_{uv}\\ \text{subject to}\quad & y_u+y_v+z_{uv}\ge 1 &&(uv\in F),\\ & \sum_{u\in U}y_u\le k,\\ & y_u\ge 0,\quad z_{uv}\ge 0. \end{aligned} \]

Consider any feasible measurable solution \((x,B)\). Set
\(y_u=\int_0^1x_u(r)\,dr\) and
\(z_{uv}=\operatorname{Leb}(B_{uv})\).
Each integral is finite because the payoffs are nonnegative and their total integral is at most \(k\).

For each edge \(uv\), feasibility and nonnegativity imply
\(x_u(r)+x_v(r)+\mathbf{1}_{B_{uv}}(r)\ge 1\)
almost everywhere: outside the deletion set this is the required constraint, and inside it the indicator already equals one. Integrating gives
\(y_u+y_v+z_{uv}\ge 1\).
The integral budget gives \(\sum_u y_u\le k\).

Thus \((y,z)\) is feasible for the linear program, and
\(\lambda(H,k)\le\sum_{uv}z_{uv}=\tau C(B)\).
Since this holds for every feasible measurable solution, taking the infimum yields

\[ \frac{\lambda(H,k)}{\tau}\le\mathrm{OPT}. \]

This argument uses only the integral budget; it imposes no budget on individual copies.

3. The precise discrete guarantee used

The stronger guarantee established by the cited paper is:

For an \(\omega\)-sparse graph \(G=(V,E)\), with \(\omega\ge 1\), and a positive integer budget \(k\), its polynomial-time algorithm returns a set \(D\subseteq E\) and nonnegative payoffs \(a\) satisfying \(\sum_v a_v\le k\), \(a_u+a_v\ge 1\) for every \(uv\in E\setminus D\), and
\(|D|\le(8\omega+2)\lambda(G,k)\).

Here \(\lambda(G,k)\) is exactly the relaxation defined above. This is the LP-relative bound from Lemma 6 and the paper’s concluding double-cover argument: the bipartite rounding factor is \(2\omega'+1\), while the construction uses \(\omega'=2\omega\) and increases the LP optimum by at most a factor of two. [Könemann–Larson–Steiner, *Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances*](https://cs.uwaterloo.ca/~klarson/papers/nwbg-sagt.pdf).

All hypotheses hold for our instance when \(m>0\): the promised sparsity condition is the paper’s definition, \(\omega\ge 1\), and \(k=\nu(H)\) is a positive integer. Importantly, we use the LP-relative guarantee stated above, which is stronger than a comparison with the discrete optimum alone.

4. Algorithm and approximation proof

If \(m=0\), return zero payoffs and no deletions. This is feasible and optimal.

Otherwise, compute \(k=\nu(H)\) and apply the discrete algorithm from Section 3 to obtain \(D\) and feasible payoffs \(a\). Define the continuum solution by
\(x_u(r)=a_u\) for every \(r\in[0,1]\), and set \(B_{uv}=[0,1]\) when \(uv\in D\), and \(B_{uv}=\varnothing\) otherwise.

Its total integral payoff is \(\sum_u a_u\le k\). Every undeleted edge satisfies its payoff constraint everywhere. Therefore the solution is feasible, and

\[ C(B)=\frac{|D|}{\tau} \le(8\omega+2)\frac{\lambda(H,k)}{\tau} \le(8\omega+2)\mathrm{OPT}. \]

5. Polynomial time and the required representation

Maximum matching and the cited rounding algorithm run in polynomial time. To obtain explicitly rational payoffs after computing \(D\), solve the finite feasibility linear program with constraints
\(0\le a_u\le 1\),
\(\sum_u a_u\le k\), and
\(a_u+a_v\ge 1\) for \(uv\in F\setminus D\).

This program is feasible: truncating any feasible nonnegative payoff at one preserves every edge constraint and cannot increase the budget. Its rational coefficients and dimensions have polynomial encoding length, so rational linear programming returns a feasible solution of polynomial bit length.

The output uses the single interval \([0,1]\), rational constant payoffs, and constant deletion membership. Its size and construction time are polynomial in \(m,\tau,L\). This completes the requested approximation guarantee.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct and rigorous. The cited paper supplies the stronger LP-relative guarantee needed here, and the measurable-solution argument transfers that guarantee to the continuum problem. No major or minor mathematical issues were found.

• The finite relaxation is well-defined.

The program has finitely many variables and rational coefficients. It is feasible and its objective is nonnegative. Its constraints agree with the relaxation used in the cited paper when all edges are eligible for deletion and the budget is \(k=\nu(H)\).

• Every feasible measurable solution yields a feasible LP solution.

The normalization is correct: multiplying the continuum budget by \(\tau\) gives
\[ \sum_{u\in U}\int_0^1x_u(r)\,dr\le k. \]
Nonnegativity and finiteness of this sum ensure that every individual payoff integral is finite. The deletion-set measures are also finite.

For each edge, the asserted inequality
\[ x_u(r)+x_v(r)+\mathbf{1}_{B_{uv}}(r)\ge1 \]
holds almost everywhere. Outside the deletion set it follows from feasibility; inside the deletion set it follows from nonnegative payoffs. Integrating therefore gives the stated LP constraint. Exceptional null sets cause no difficulty because integration is performed separately for each edge.

• The lower bound on the continuum infimum is valid.

The argument establishes
\[ \lambda(H,k)\le\tau C(B) \]
for every measurable feasible solution. Taking the infimum consequently yields
\[ \frac{\lambda(H,k)}{\tau}\le\mathrm{OPT}. \]
Attainment of the continuum infimum is unnecessary. No pointwise budget has been assumed.

• The critical external guarantee is verified.

In the [cited paper](https://cs.uwaterloo.ca/~klarson/papers/nwbg-sagt.pdf), program (PB) on page 5 matches the stated relaxation with \(E_1=E\), \(E_2=\varnothing\), and budget \(k\). Lemma 6, under the section’s bipartite assumption, bounds the deletion count by \((2\omega'+1)\) times the LP optimum. The concluding construction doubles the budget, bounds the new sparsity parameter by \(2\omega\), and increases the LP optimum by at most a factor of two. Its final displayed bound is \(2(4\omega+1)\) times the original LP optimum, exactly \(8\omega+2\).

Thus the stronger guarantee is supported by the source, rather than inferred merely from its discrete approximation theorem. The prover checks the applicable hypotheses: promised sparsity, \(\omega\ge1\), and positive integer \(k\) when \(m>0\).

• The constant continuum solution is feasible.

Constant payoffs preserve the discrete budget after integration. Fully deleting precisely the edges in \(D\) leaves every remaining edge constraint satisfied everywhere. The cost normalization is correct:
\[ C(B)=\frac{|D|}{\tau}. \]
Both inequalities in the approximation chain are justified, so the claimed guarantee follows.

• Degenerate cases are covered.

When \(m=0\), zero payoffs and no deletions are feasible and optimal, including when \(\tau=1\). When \(m>0\), a matching of positive size exists, so the positive-budget hypothesis applies. The argument also covers \(\mathrm{OPT}=0\), because it uses inequalities rather than division by the optimum.

• Polynomial time and output representation are justified.

Maximum matching is computable in polynomial time. The cited rounding procedure is polynomial-time. The final feasibility LP has polynomial dimensions and rational coefficients of polynomial encoding length.

The truncation assertion is valid: replacing a nonnegative payoff exceeding one by one preserves every unit edge constraint and cannot increase the budget. Hence the final LP is feasible and yields rational payoffs of polynomial bit length. A single interval with endpoints zero and one meets the required representation, including constant deletion membership.

Feedback: No repair or additional clarification is required. The output resolves the assigned continuum approximation question.

⟨structured verdict parsed — rendered above⟩