d4-conf-sagt-2012-0020

The strongest mirror I would defend is a replicated-cell version of the paper’s sparse-graph blocking-set problem. Imagine many branches or campuses running the same small bargaining network \(H=(U,F)\): the same roles, the same unit-value deals, and the same sparse pattern of possible bargains in every cell. With \(N\) cells there are \(N|U|\) agents but only \(|U|=\tau\) role types. A type \(u\in U\) identifies a role and its bargaining opportunities; the cell index does not affect anyone’s preferences or costs.

In the continuum, let \(r\in[0,1]\) index cells and let \((r,u)\) be the agent in role \(u\) at cell \(r\). Give each role mass \(1/\tau\), so the total population mass is \(1\). For each \(uv\in F\), there is a unit-value bargaining opportunity between \((r,u)\) and \((r,v)\) at every \(r\). The matching capacity per unit mass is \(\nu(H)/\tau\), where \(\nu(H)\) is the maximum matching size in one cell. The allocation budget is system-wide, so payoffs can shift across cells; I do not impose a separate budget on each cell.

Call this problem Replicated Continuous Blocking Set. Its input is a finite \(\omega\)-sparse template \(H\). A solution is a measurable payoff \(x_u(r)\ge 0\) for each role and a measurable set \(B_{uv}\subseteq[0,1]\) of copies of each edge that are removed. It must satisfy
\[ \frac{1}{\tau}\sum_{u\in U}\int_0^1 x_u(r)\,dr\le \frac{\nu(H)}{\tau}, \qquad x_u(r)+x_v(r)\ge 1 \quad\text{for almost every }r\notin B_{uv}. \]
The objective is to minimize
\[ \frac{1}{\tau}\sum_{uv\in F}\operatorname{Leb}(B_{uv}). \]
The computational task is to output a feasible solution whose objective is at most \(8\omega+2\) times the optimum.

My anchor is Theorem 2, proved in this paper. It says that for every \(\omega\)-sparse graph \(G=(V,E)\), an efficient algorithm finds a blocking set \(B\) of size at most \(8\omega+2\) times the minimum possible, where a blocking set has a nonnegative allocation \(x\) with \(\sum_{v\in V}x_v\le \nu(V)\) and \(x_u+x_v\ge 1\) on every edge outside \(B\). This is the paper’s named algorithmic result for blocking sets. The manuscript also mentions NP-hardness of finding a smallest blocking set, citing [3], but that claim is not a numbered result here, so I am not using it as an anchor.

The approximation guarantee has a concrete route into the mirror. For a deletion pattern \(B\subseteq F\), let
\[ q(B)=\min\left\{\sum_{u\in U}z_u: z_u\ge 0,\ z_u+z_v\ge 1\text{ for every }uv\in F\setminus B\right\}. \]
This is the minimum fractional vertex-cover value of the remaining cell. A continuum policy induces a distribution \(\pi\) over deletion patterns, and its optimum is exactly the finite configuration LP
\[ \min \sum_{B\subseteq F}\pi_B|B| \quad\text{subject to}\quad \sum_{B\subseteq F}\pi_Bq(B)\le \nu(H),\qquad \sum_{B\subseteq F}\pi_B=1,\qquad \pi_B\ge 0. \]
An optimal distribution needs at most two patterns. Each \(q(B)\) is half-integral and at most \(\tau\), so the mixing weight can be realized by some number \(N\le 2\tau\) of identical cells. The finite graph made of those \(N\) disjoint copies remains \(\omega\)-sparse and has matching number \(N\nu(H)\). Applying Theorem 2 to it gives a solution that, viewed as a piecewise-constant policy over the continuum of cells, has the same approximation factor. Trying each \(N\le 2\tau\) avoids needing to know the optimal mixture in advance. Thus I expect this approximation problem to be tractable, a Class A result.

The mirror preserves the paper’s central question: how much bargaining mass must be removed before a network can support an allocation within its matching-value budget? It continuizes the population, while retaining the network roles, the matching resource, and the edge-removal decision. The repeated-cell scenario is also a genuine high-multiplicity regime: population size grows with the number of cells, while the role set stays fixed.

The weak point is the regime’s narrowness. It models many copies of one sparse network, not one large connected network with irregular or long-range ties. The approximation result therefore supports a credible mirror of Theorem 2, but says little about whether continuous populations dissolve the hardness of the exact problem. Natural follow-up questions are whether the same guarantee extends to finitely many cell templates, whether the exact configuration LP has an efficient pricing algorithm, and whether a comparable population model works for general sparse graphings.