d4-conf-sigecom-2013-0006

The strongest computational mirror is Theorem 4, proved in the paper. It says that, given \(\epsilon>0\), black-box access to an arbitrary algorithm \(\mathcal A\) and the known independent value distributions, one can construct a BIC mechanism that recovers cost in expectation and has expected social cost at most \(O(\min\{\log h,\log n\})\,\mathbb E[SC(\mathcal A)]+\epsilon\). Its running time is polynomial in \(1/\epsilon\), \(n\), and the running time of \(\mathcal A\). The paper does not give a conventional NP-hardness theorem; its computational anchor is this polynomial-time mechanism transformation.

For its continuous mirror, take a large population divided into a small number of cohorts \(g\). Members of each cohort share the same public service-cost and valuation-distribution parameters. Their private values come from a known finite support \(V_g\subseteq[1,h]\). The society is the rational mass distribution \(\mu_{g,v}\) over complete types \((g,v)\), with support size \(\tau\). Think of a large district seeking a shared service: people in each cohort have the same connection conditions, while the provider’s cost depends on how much of each cohort it serves. This makes service by mass natural. The individual values remain private; the mass distribution describes the population’s type law.

The instance for the continuous problem consists of that mass distribution, a monotone cost function \(C\) on served-mass vectors, and a black-box baseline allocation rule \(\mathcal A\), including access to its allocation and cost on queried profiles. A solution is a measurable randomized direct mechanism: for each cohort and reported value it specifies a service probability \(q_g(v)\) and an expected payment \(p_g(v)\). It must satisfy BIC and individual rationality, recover expected service cost, and achieve expected social cost at most \(O(\log h)\,SC(\mathcal A)+\epsilon\). The \(O(\log n)\) branch has no finite population-size parameter in this model; the value-range branch is the relevant one. The question I would hand to a prover is whether this guarantee can be achieved with complexity polynomial in \(1/\epsilon\), \(\tau\), \(L\), and the oracle running time, where \(L\) is the input bit length.

I expect this problem to be tractable, in the sense of the programme’s Class A. The paper’s threshold construction is a plausible route: truncate the interim allocation curves at successive value thresholds, compute the corresponding BIC payments, and use the first threshold whose expected payments cover expected cost. In the finite-support version these operations become sums over types. This is still the paper’s problem: choosing whom to serve, charging them, meeting BIC, recovering service cost, and controlling social cost. The mass-dependent cost is a co-modification for a homogeneous shared-service regime, not a change of objective.

A second, especially credible anchor is Theorem 6, also proved here. In its public-excludable-good instance, \(n\) agents have values \(v_i=a_i/(4n)\), where the \(a_i\) are independent, equal-revenue draws: zero with probability \(1/h\), and otherwise distributed with density \(1/a^2\) on \([1,h]\). Serving any nonempty set costs \(1\). The theorem says every BIC mechanism that recovers cost in expectation has expected social cost at least \(\Omega(\log h-\sqrt{h/n})\).

Here is a finite-support continuous-population version of that lower-bound question. Let \(h=2^k\), and let a unit-mass population have types \(a=0,1,2,\ldots,2^{k-1}\), with \(\mu(0)=2^{-k}\) and \(\mu(2^j)=2^{-(j+1)}\) for \(0\le j<k\). Give type \(a\) value \(a/4\) in aggregate-welfare units: this is the original value scaled by the population size, with values and payments scaled together so incentives are preserved. A shared good costs \(1\) whenever positive mass is served, and nothing otherwise. The problem is to find a BIC, individually rational allocation and payment rule minimizing expected social cost subject to expected cost recovery.

The equal-revenue law caps expected BIC revenue at \(1/4\) per unit of population mass. Cost recovery therefore implies that positive mass is served with probability at most \(1/4\). The total value of the population is \(k/8\), so on the event of no service—whose probability is at least \(3/4\)—the entire \(k/8\) is lost. Thus expected social cost is at least \(3k/32=\Omega(\log h)\). For \(k\ge8\), serving everyone has social cost \(1\), which is optimal without the incentive and cost-recovery requirements. This is the Class B-style outcome: the logarithmic obstruction survives at high multiplicity. It is an incentive and approximation lower bound, not an NP-hardness claim.

Theorem 4 is my lead computational anchor; Theorem 6 makes the population regime unusually convincing. In both, the number of agents can be enormous relative to the number of distinct types, and the public-good case is already about a shared service with a cost determined by aggregate participation. The paper’s use of random value distributions is not itself the continuization: the mirror makes the population’s type masses the object being modeled.

The soft spot is the atomless-agent limit. An individual has zero effect on aggregate service mass, so the mirror must preserve incentives through each agent’s allocation and payment schedule, rather than through their impact on the population profile. More concretely, Theorem 4’s polynomial dependence on \(n\) does not establish a polynomial algorithm in \(\tau\) and \(L\); that compression is part of the proposed research question. Theorem 6 is less exposed to this objection: its i.i.d. large-population setting and pooled fixed cost already motivate the limit, and the lower-bound argument becomes cleaner when aggregate type masses are fixed. This case covers the paper’s BIC expected-cost-recovery results, not its ex-post truthful and no-bossiness results or arbitrary costs that depend on named individuals.