d4-conf-sigecom-1999-0016

The strongest mirror is the paper’s winner determination problem for single-minded bidders, anchored on Theorem 2, proved in the paper using a reduction and an inapproximability result of Håstad. The theorem says that, given one single-minded bid \(\langle s_i,v_i\rangle\) per bidder, maximizing the total value of a conflict-free allocation is NP-hard when the number of goods \(k\) and bidders \(n\) grow in a polynomially related way. It also says that a polynomial-time algorithm guaranteeing an allocation worth at least \(k^{-1/2+\epsilon}\) times the optimum would imply \(\mathrm{NP}=\mathrm{ZPP}\). In the paper’s reduction, graph edges become goods and vertices become bids for their incident edges, so selecting compatible bids encodes an independent set.

Here is a continuous version I would put to a prover. Call it Mass Single-Minded Winner Determination. An instance has a finite goods set \(G\), a list \(T\) of \(\tau\) supported bidder types, and a per-capita supply \(q_g\) for each \(g\in G\). Each type \(t\in T\) is a single-minded pair \((S_t,v_t)\), where \(S_t\subseteq G\) and \(v_t\) is the value of receiving that entire bundle. The society has rational type masses \(\mu_t\geq 0\), summing to one. The supplies, masses, and values are binary rationals.

Choose a mass \(x_t\) of each type to serve, with \(0\leq x_t\leq\mu_t\) and \(\sum_{t:g\in S_t}x_t\leq q_g\) for every good \(g\), to maximize \(\sum_t v_t x_t\). A solution is the vector \(x\). Every individual served still gets their whole requested bundle; fractional quantities occur only in the mass of a type served. The question is whether an optimal allocation can be computed in time polynomial in \(|G|,\tau\), and the input bit length. This is a linear program with \(\tau\) variables and \(|G|+ \tau\) constraints, so the expected answer is tractable.

The regime I have in mind is a large market for repeated, standardized service or license units: many small buyers, but relatively few combinations of regions or services they want and few distinct values for those combinations. With \(N\) buyers, type \(t\) represents about \(N\mu_t\) buyers, and good \(g\) has about \(Nq_g\) units available. Thus both the population and supplies grow together, while the number of types stays modest. That makes the mass decision a plausible high-multiplicity account of winner determination. The paper itself points toward multi-unit combinatorial auctions as further work, which makes this co-modification of supply especially recognizable as an extension of its problem.

The mirror covers Theorem 2’s welfare-maximizing allocation among single-minded bidders, not the paper’s mechanism-design results. The original authors could reasonably recognize the objective and bundle conflicts: the mirror retains each bidder’s all-or-nothing demand and value, while grouping indistinguishable bidders and scaling supplies to the market. Useful next questions are whether this LP admits rounding guarantees for finite markets, how the answer changes when some types have low multiplicity, and whether a truthful payment scheme survives in the mass model.

The weak point is that Theorem 2’s hardness is driven by the combinatorics of bundles and goods, not solely by a large population. The mirror becomes tractable partly because many identical bidders can be rationed as a group and supplies scale with the market. That is a meaningful continuous multi-unit winner determination problem, but it is less faithful to a one-off auction with a fixed stock of distinct goods. I would still defend it as a strong mirror for the repeated-market regime, while being explicit that it does not show population continuization alone dissolves Theorem 2’s hardness.