| paper | d4-conf-sigecom-2012-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A randomized algorithm running in polynomial time in \(m,\tau,L\) always returns a feasible allocation \(\nu\) with \(\mathbb{E}[W(\nu)]\geq\mathrm{OPT}/(16\rho_H)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), an unweighted conflict graph \(H\) on \(T\), \(k\) channels, and symmetric valuation curves \(b_t(i)\), find a feasible mass allocation \(\nu_{t,S}\geq 0\) with \(\sum_{S\subseteq[k]}\nu_{t,S}=\mu_t\). For each channel \(j\), the types with \(\sum_{S\ni j}\nu_{t,S}>0\) must form an independent set of \(H\). Is there a randomized algorithm polynomial in \(\tau=|T|\), \(k\), and the input bit length that returns such an allocation with expected welfare \(\sum_{t\in T}\sum_{S\subseteq[k]}\nu_{t,S}b_t(|S|)\geq \mathrm{OPT}/(16\rho_H)\), where \(\rho_H\) is the inductive independence number of \(H\)?
Use \(H\) as the graph of type conflicts and assign type \(t\) the valuation \(\mu_t b_t(i)\). Although the model permits splitting mass among integral bundles, an optimum can give all of each type's mass its highest-value bundle: this weakly raises welfare and only removes active channels. Thus Theorem 1 on \(H\) yields the stated guarantee for the mass allocation.
The wireless example requires exact shared conflict profiles and within-type compatibility, which may describe only a narrow class of deployments; this limits its reach but not the stated model.
fatal: False
The mirror covers Theorem 1's welfare approximation for symmetric valuations on unweighted conflict graphs. It leaves the weighted-graph and MRS results, and the paper's truthful-mechanism guarantees, aside.
My strongest case is a narrow mirror of the paper’s unweighted, symmetric-valuation allocation result.
Theorem 1, proved in this paper in §3.1, says that for unweighted conflict graphs and symmetric valuations, the paper’s algorithm returns a feasible allocation whose expected social welfare is at least \(b^\ast/(16\rho)\). Here \(b^\ast\) is the optimal welfare and \(\rho\) is the graph’s inductive independence number. This is an approximation result, not a hardness result. The paper cites lower bounds from earlier work, but has no numbered hardness theorem of its own to anchor instead.
Consider a large wireless deployment with repeated request classes: for example, many devices in standardized service and interference zones. A type \(t\) records the complete information the allocation problem uses: its per-user valuation curve \(b_t(i)\) for receiving \(i\) channels, and its conflict relations with every other type. Let \(T\) be the finite set of types, with rational masses \(\mu_t>0\) summing to \(1\), and let \(H\) be their conflict graph. Assume members of one type are mutually compatible, while an edge in \(H\) means every member of one type conflicts with every member of the other. The intended regime has \(N\gg\tau=|T|\): many requests, but relatively few complete valuation-and-conflict profiles.
I would call the mirror Type-Mass Symmetric Spectrum Allocation. Given \(T\), \(\mu\), \(H\), \(k\) channels, and the valuation curves \(b_t\), find a feasible allocation of the population maximizing per-capita welfare. An allocation is a table of masses \(\nu_{t,S}\geq0\), where \(\nu_{t,S}\) is the mass of type \(t\) receiving the *integral* bundle \(S\subseteq[k]\), and \(\sum_{S\subseteq[k]}\nu_{t,S}=\mu_t\). For each channel \(j\), the types with positive mass receiving \(j\) must form an independent set of \(H\). Welfare is
\[
W(\nu)=\sum_{t\in T}\sum_{S\subseteq[k]}\nu_{t,S}b_t(|S|).
\]
The computational question is whether a randomized algorithm, polynomial in \(\tau\), \(k\), and the input bit length, can return a feasible allocation with expected welfare at least \(\mathrm{OPT}/(16\rho_H)\), where \(\rho_H\) is the paper’s inductive independence parameter applied to the type graph. The output can be a sparse table: for each type, a polynomial-size list of bundles and their masses.
This is a genuine population mirror of the paper’s underlying channel-allocation problem. If a finite society has \(n_t\) identical users of each type, its allocation table has masses in increments of \(1/N\), where \(N=\sum_t n_t\); clearing denominators recovers that finite instance. The continuum allows finer divisions of a type among bundles. Each portion of mass still receives a whole bundle, and feasibility still enforces the conflict graph channel by channel. The paper’s LP also has a natural aggregate form, with variables \(y_{t,i}\) for mass of type \(t\) receiving \(i\) channels, giving a compact relaxation in roughly \(\tau k\) variables. That makes an \(O(\rho_H)\) approximation a credible Class A target.
The weakest point is the block structure. An arbitrary conflict graph need not admit a small set of types with identical valuation and conflict profiles; refining types to capture every individual neighborhood could make \(\tau\) approach \(N\). More seriously, Theorem 1 does not itself establish the proposed mass guarantee: the inductive independence parameter on a finite clone graph can grow with clone multiplicities. The case depends on proving that the LP and its rounding analysis can use the type-level parameter \(\rho_H\) after aggregation. I expect the approximation question to be tractable under the stated regime, while exact optimization may retain the combinatorics of choosing compatible types. This mirror covers only Theorem 1’s unweighted, symmetric welfare-allocation result; it makes no claim about truthfulness, weighted conflict graphs, or the paper’s MRS results.
I would not green the proposed theorem transfer as stated. The type level parameter \(\rho_H\) does not control the paper’s LP or rounding on the corresponding finite bidder graph. For example, replace each endpoint of a single conflict edge by \(q\) mutually compatible clones, with every clone on one side conflicting with every clone on the other. The type graph still has constant inductive independence number, but in any ordering, the last clone on one side has all \(q\) clones on the other side earlier; those clones form an independent set. Thus the clone graph’s parameter is \(\Omega(q)\). The paper’s LP constraints count those clones, so aggregating them into a \(\tau k\)-variable LP and substituting \(\rho_H\) needs a new justification. The claimed \(1/(16\rho_H)\) guarantee does not follow from Theorem 1.
That problem is sharper in the proposed mass model: any positive mass of a type using a channel activates that type’s conflict with every adjacent type, however small the mass. Splitting a type across bundles can distribute welfare, but does not smooth the channel conflicts. A repaired mirror could study this support-based feasibility problem on a type graph, perhaps with a new relaxation and parameter. That is a coherent continuous question, but it is a new theorem rather than an aggregation of the paper’s analysis.
The wireless story also needs more support. Exact types must share both valuation curves and complete conflict profiles, while members of a type must be mutually compatible. In the cited physical interference settings, grouping requests by broad service zones usually gives approximate profiles, not identical ones; exact co-location may make requests conflict with one another. The paper’s truthful mechanisms add another gap: an individual in an atomless population has zero mass, so their report cannot play the same strategic role as a bidder’s report in the finite auction. The proponent avoids that issue by anchoring only the welfare algorithm, but then the mirror omits a central feature of the paper.
Still, I cannot honestly make the universal negative case. Theorem 1 is a named computational approximation result, and a society made of repeated, mutually compatible request classes with exact shared conflict profiles is a well-defined mass allocation model. Its study could be worthwhile even if the paper’s guarantee does not carry over. My objections weaken this particular mirror’s application story and claimed parameterization; they do not establish that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.