| paper | d4-conf-sigecom-2012-0070 |
| 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: Exactly solvable in deterministic \((m\tau+L)^{O(1)}\) bit time; hence welfare at least \(\mathrm{OPT}/r^{1-\epsilon}\) is achievable for every fixed \(0<\epsilon<1\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4.2
statement extracted from the paper’s text layer
Given goods \(M\), types \(t\) with rational masses \(\mu_t\), hypergraph-\(r\) valuations \(v_t(S)=\sum_{j\in S}w_{tj}+\sum_{e\in E_t:e\subseteq S}w_{te}\), and rational per-capita supplies \(q_j\), choose masses \(y_{t,S}\) assigned to integral bundles \(S\subseteq M\). Maximize \(\sum_t\sum_{S\subseteq M} y_{t,S}v_t(S)\), subject to \(\sum_S y_{t,S}\le\mu_t\) for each type and \(\sum_{t,S:j\in S}y_{t,S}\le q_j\) for each good; unassigned mass is allowed.
A continuous-population configuration LP: each type’s mass is divided among integral bundles, while goods have per-capita capacities. The objective is per-capita welfare, and bundle pricing maximizes \(v_t(S)-\sum_{j\in S}p_j\), which Proposition 5.1 supports in polynomial time.
The mirror covers Theorem 4.2’s welfare-maximization problem; it does not cover the excluded-minor truthful mechanisms or the truthful-in-expectation approximation mechanism.
The strongest mirror I see is a large, repeated combinatorial market. For example, a telecom rollout may allocate many copies of standardized capacity packages to a much larger cohort of firms. Firms with the same footprint, technology, and valuation schedule share a type; the number of firms \(N\) is large while the number of distinct types \(\tau\) is much smaller. Each package copy remains indivisible, and a firm still receives an integral bundle. As the cohort grows, supply grows with it, so each package category has a fixed supply per participant. This is the co-modification that makes a continuous population meaningful here.
My sole anchor is Theorem 4.2, cited from [28] rather than proved in this paper. It says that, unless \(P=NP\), welfare maximization for hypergraph-\(r\) valuations has no \(r/2^{O(\sqrt{\log r})}\)-approximation algorithm. The lower bound applies even to single-minded valuations, where each bidder wants one bundle of at most \(r\) goods. This is the paper’s hardness boundary for its underlying welfare problem.
Here is the corresponding continuous question, which I would hand to a prover as the lead mirror. A type \(t\) is a complete hypergraph valuation over the paper’s goods \(M\): \(v_t(S)=\sum_{j\in S}w_{tj}+\sum_{e\in E_t:e\subseteq S}w_{te}\), with nonnegative weights and \(|e|\le r\). An instance gives the \(\tau\) types, their rational population masses \(\mu_t\) with \(\sum_t\mu_t=1\), and a rational per-capita supply \(q_j\) for each good \(j\). The decision variable \(y_{t,S}\) is the mass of type \(t\) assigned the integral bundle \(S\). Find a feasible assignment maximizing per-capita welfare \(\sum_t\sum_{S\subseteq M} y_{t,S}v_t(S)\), subject to \(\sum_S y_{t,S}\le\mu_t\) for every type and \(\sum_{t,S:j\in S}y_{t,S}\le q_j\) for every good. Unassigned mass is allowed. The solution is the full set of masses \(y_{t,S}\).
This is recognizably the paper’s welfare-maximization problem: same bidder valuations, same bundle values, same item capacities, and the same objective. The continuous feature is that indistinguishable bidders of a type can be divided across bundles in aggregate; no individual receives a fractional bundle. There is also a direct high-multiplicity bridge. For a discrete instance with \(n_t\) bidders of type \(t\) and one copy of each good, set \(\mu_t=n_t/n\) and \(q_j=1/n\). Every discrete allocation gives a feasible continuous assignment with the same welfare per capita. Replicating every bidder and every good copy \(k\) times leaves these per-capita quantities unchanged. Since the continuous LP has a rational optimum, sufficiently large replications can realize that assignment exactly. Thus the mirror describes the limit of repeated markets with identical valuation types and proportionally scaled supply.
I expect this continuous problem to be tractable. It is an LP with \(\tau 2^m\) potential type-bundle variables. Its pricing problem asks, for each type, to maximize \(v_t(S)-\sum_{j\in S}p_j\) over bundles \(S\). The paper’s Proposition 5.1 shows that these demand queries are polynomial-time for hypergraph valuations: the objective is supermodular, so it can be maximized through submodular minimization. That gives an ellipsoid-and-separation route to the exact rational LP optimum, with running time polynomial in \(m\), \(\tau\), the explicit hypergraph descriptions, and the input bit length. In this mirror, Theorem 4.2’s discrete inapproximability does not transfer: the continuous problem admits an exact optimization algorithm.
The scope is deliberately narrow: it mirrors Theorem 4.2’s welfare-maximization hardness, not the paper’s truthfulness guarantees or its excluded-minor mechanism. It raises a useful follow-up: how does the continuous optimum compare with finite replicated markets at practical replication sizes, and how do the required rounding bounds depend on \(m\), \(r\), and \(\tau\)?
The weakest point is the supply regime. The paper’s stated auction has one copy of each good, and a fixed stock of scarce goods need not grow with its bidder population. Scaling supply is essential to keep positive mass receiving bundles in an atomless population, but it makes this a repeated-market or per-capita-supply version of the paper’s problem. I think authors working on high-multiplicity allocation would recognize that as a serious continuous analogue; it should not be presented as the limit of every one-shot auction.
The strongest objection is the supply scaling. In the paper’s one-shot auction, \(M\) contains one copy of each good. If the bidder population grows while that inventory stays fixed, per-capita supply is \(q_j=1/n\to 0\), so the proposed limit gives almost all mass the empty bundle. Keeping \(q_j>0\) requires inventory to grow with the population. That describes recurring markets for standardized package classes, and the hypergraph valuation remains faithful only under a specified rule for how each buyer can consume those repeated packages. The proponent’s bridge establishes a limit for that scaled market; it does not establish one for every fixed-stock auction.
This caveat does not defeat the best version of the mirror. Many firms with repeated valuation schedules competing for recurring supplies of standardized capacity packages are a credible high-multiplicity regime. A type can capture the complete valuation, and mass can be split among integral bundles. The per-capita supply change is an admitted co-modification of the population model.
Theorem 4.2 is a named computational lower bound for the same welfare objective. In the continuous version, its discrete allocation problem becomes an LP over type-bundle masses. The paper’s Proposition 5.1 supplies polynomial demand queries for hypergraph valuations, giving a separation route for that LP. That could make the continuous question easy to answer, but ease of the answer does not disqualify the mirror.
So the negative case can narrow the application to repeated markets; it cannot rule out a worthwhile mirror in every scenario. I cannot honestly defeat this anchor. The case against it is weak.
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.