d4-conf-sagt-2014-0002

The lead is a high-multiplicity version of the paper’s black-box truthfulness question for social welfare. My strongest secondary case is narrower: the paper’s per-agent ironing lower bound has a natural mass-coupling mirror. Neither anchor is an NP-hardness theorem; both are computational impossibility results proved in this paper.

Lead — Theorem 3.1, proved here. It states that there is a constant \(c>0\) such that, for every polynomial-time TIE black-box transformation \(\mathcal T\), some social-welfare feasibility constraint \(\mathcal F\) and algorithm \(\mathcal A\) satisfy
\[ \frac{\operatorname{approx}_{\mathcal F}(\mathcal A)} {\operatorname{approx}_{\mathcal F}(\mathcal T(\mathcal A))}\ge n^c. \]
In other words, no such transformation preserves worst-case approximation up to a subpolynomial loss on every instance.

I would mirror it as Mass-Society TIE Repair for Social Welfare. Consider a large cohort of interchangeable households with private values in a finite set \(\Theta\), represented by rational masses \(\mu_\theta\). Within each value class, agents share the same preferences, costs, and eligibility. The action is a service rate \(x_\theta\): a fraction \(x_\theta\) of that class receives an indivisible unit of service. Since the population is nonatomic, these rates describe whole bundles assigned to fractions of a class, not fractional bundles for individuals. Welfare is \(W_\mu(x)=\sum_{\theta\in\Theta}\mu_\theta\theta x_\theta\).

An instance includes a feasible correspondence \(\mathcal F(\mu)\) over these rate vectors and a black-box allocation algorithm \(\mathcal A\) that returns feasible allocations for reported society profiles. A transformation sees \(\mathcal A\), but not \(\mathcal F\), and must return feasible allocations while making expected service nondecreasing in an individual’s report, holding the background mass profile fixed. The question is to characterize the smallest worst-case loss factor \(\lambda\) for a universal transformation running in time polynomial in support size \(\tau\) and encoding length \(L\). A solution would be such a transformation with a proved \(\lambda\), or a lower-bound family of anonymous mass instances ruling out better guarantees.

This is a sensible regime: a large service market can have millions of participants but only a few value classes. I expect the black-box repair problem to remain hard for continuum-specific reasons: the transformation must repair incentives while learning feasibility only through oracle outputs. The paper’s theorem does not establish this result for the mass model. It motivates the question.

Secondary — Theorem 5.1, proved here. For the objective \(\max \mathbb E_v[\sum_i h_i(x_i(v))v_i]\), the theorem says that if some \(h_i\) is continuous and superlinear or sublinear, then for every \(\epsilon\in(0,1)\) there is a value distribution and algorithm such that any per-agent ironing that preserves that agent’s value distribution and makes expected allocation monotone must violate the objective-preservation condition (P.3) by a factor of \(\Omega(1/\epsilon)\).

Its mirror is Continuum Per-Agent Ironing for Nonlinear Welfare. The input is a mass distribution \(\mu\) over agent values, an allocation rule giving each value class a lottery over whole- agent allocations, and a continuous increasing nonlinear objective \(h\). The decision variable is a measure-preserving remapping kernel \(K\) on value types: mass of true type \(v\) can be sent to reported type \(v'\), but the total mass of each reported type must remain \(\mu\). The remapped rule must have nondecreasing expected allocation in the true value, and the objective is to maximize \(\int v\,\mathbb E[h(X_{K(v)})]\,d\mu(v)\). A solution is a feasible kernel and its objective value, or a lower-bound certificate showing the best achievable value is small relative to the original rule.

The paper gives a concrete obstruction: with mass \(1-\epsilon\) at value \(0\) and mass \(\epsilon\) at value \(1\), it constructs an algorithm for which every such monotone, distribution-preserving remapping loses a factor \(\Omega(1/\epsilon)\). This lower bound carries to a continuum cohort by integrating the same per-agent construction over the population. It is a firm negative result for per-agent ironing; it does not rule out joint transformations across agents.

The main soft spot is the lead mirror’s anonymity requirement. Theorem 3.1’s construction uses hidden identity-specific sets \(S\) and \(T\). Making membership in those sets part of an agent’s type may increase \(\tau\), while omitting it would make supposedly identical agents behave differently in ways the problem uses. So the mass version is a genuine, narrower problem, not a consequence of Theorem 3.1. A useful next question is whether an anonymous, constant-support version still has a polynomial loss barrier—or whether aggregation makes truthfulness repair easier. I would not use Theorem 4.1 as another anchor: its single forbidden allocation is also tied to named machines, which creates the same type-compression problem.