| paper | A truthful randomized mechanism for combinatorial public projects via convex optimization |
| authors | S. Dughmi |
| venue | SIGECOM 2011 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: An expected-polynomial-time algorithm exists that outputs exactly \(S\sim r_k(\bar x)\) for a fixed instance-dependent \(\bar x\in P_k\), with \(\mathbb{E}[W(S)]\ge(1-1/e)\mathrm{OPT}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given \(m\), \(k\), a finite type set \(T\), rational masses \(\mu_t\), and bounded-lottery-value oracles for normalized monotone MRS valuations \(v_t\), compute in expected time polynomial in \(m\), \(|T|\), and the input encoding a randomized feasible project set \(S\subseteq[m]\), sampled as \(S\sim r_k(x)\) for some \(x\in P_k=\{x\in[0,1]^m:\sum_jx_j\le k\}\), such that \(\mathbb{E}[\sum_{t\in T}\mu_t v_t(S)]\ge(1-1/e)\max_{|R|\le k}\sum_{t\in T}\mu_t v_t(R)\).
A high-multiplicity public-project society with valuation types \(T\) carrying masses \(\mu\); the planner chooses \(x\in P_k\), samples an integral outcome \(S\sim r_k(x)\), and optimizes the per-capita objective \(F_\mu(x)=\mathbb{E}_{S\sim r_k(x)}[\sum_t\mu_t v_t(S)]\).
The opponent's residual concern is that \(F_\mu\) collapses to one aggregate MRS valuation, so the mirror contributes high-multiplicity compression rather than new public-project combinatorics; the proponent establishes eligibility but not greater substantive novelty.
fatal: False
It covers the welfare-allocation, MIDR, convex-optimization, and \((1-1/e)\)-approximation content of Theorem 3.1; it leaves numerical-conditioning details, payment sampling, and individual-level incentive interpretation outside the surviving mirror.
The strongest honest mirror is a high-multiplicity version of the paper’s flexible Combinatorial Public Projects problem. The projects and feasible outcomes remain discrete; the population of players becomes continuous.
My lead anchor is Theorem 3.1, proved in this paper. It states that, for CPP with matroid-rank-sum valuations and bounded-lottery-value oracles, there is a truthful-in-expectation \((1-1/e)\)-approximation mechanism running in expected \(\operatorname{poly}(n,m)\) time. The paper also explains that this approximation factor is optimal for coverage valuations unless \(P=NP\), but that lower bound is attributed to Raz and Sviridenko rather than proved as a numbered hardness theorem here. Thus Theorem 3.1 is the paper’s strongest usable anchor; there is no comparable numbered hardness anchor of its own.
A natural regime is a large city running a participatory-budgeting scheme. There are \(m\) candidate public projects and at most \(k\) can be selected. The population consists of many residents, but residents fall into a relatively small number of repeated preference cohorts: for example, neighborhood and demographic groups with the same benefits from projects. A type \(t\) is the complete MRS valuation \(v_t:2^{[m]}\to\mathbb{R}_+\) of such a cohort, including its lottery-value oracle. If \(N_t\) residents have that type among \(N\) residents, its mass is \(\mu_t=N_t/N\). The intended regime is \(N\) very large and \(\tau=|T|\ll N\), with \(\mu_t\) given by rational proportions.
The continuous problem I would hand to a prover is:
\[ \textsc{Continuous-MRS-CPP}_\infty \]
An instance consists of \(m\), \(k\), a finite type set \(T\), rational masses \(\mu_t\ge 0\) satisfying \(\sum_t\mu_t=1\), and bounded-lottery-value oracles for normalized monotone MRS valuations \(v_t\). Define the per-capita population valuation
\[ \bar v_\mu(S)=\sum_{t\in T}\mu_t v_t(S) \]
for every project set \(S\subseteq [m]\), and
\[ \operatorname{OPT}_\mu = \max_{\substack{S\subseteq[m]\\ |S|\le k}} \bar v_\mu(S). \]
The planner must construct a randomized feasible outcome with expected welfare at least
\[ \left(1-\frac1e\right)\operatorname{OPT}_\mu. \]
More specifically, the mechanism may choose \(x\) in
\[ P_k=\left\{x\in[0,1]^m:\sum_{j=1}^m x_j\le k\right\}, \]
then sample \(S\sim r_k(x)\), where \(r_k\) is the paper’s \(k\)-bounded-lottery rounding scheme. Its objective is
\[ F_\mu(x) = \mathbb{E}_{S\sim r_k(x)}[\bar v_\mu(S)]. \]
A solution is an \(x\in P_k\) maximizing \(F_\mu(x)\), together with the corresponding sampler for \(r_k(x)\). Since the integral point \(1_S\) satisfies
\[ \mathbb{E}[\bar v_\mu(r_k(1_S))] \ge \left(1-\frac1e\right)\bar v_\mu(S), \]
an optimizer of \(F_\mu\) gives the required approximation.
The strategic version retains the paper’s mechanism-design content. Treat each positive-mass type as a reporting block with aggregate valuation \(\mu_t v_t\). Given reports \(\hat v_t\), choose \(x^*\) maximizing
\[ \sum_t\mu_t \mathbb{E}_{S\sim r_k(x)}[\hat v_t(S)]. \]
Then sample \(S\sim r_k(x^*)\). The total VCG payment charged to block \(t\) is
\[ P_t= \max_{x\in P_k} \sum_{u\ne t}\mu_u \mathbb{E}[\hat v_u(r_k(x))] - \sum_{u\ne t}\mu_u \mathbb{E}[\hat v_u(r_k(x^*))]. \]
Truthful reporting is optimal in expectation for every type block, and \(P_t/\mu_t\) can be interpreted as the common per-capita transfer. This is the high-multiplicity, type-level analogue of the paper’s truthful-in-expectation mechanism.
The mirror is faithful rather than a tractable surrogate. The aggregate valuation \(\bar v_\mu\) is itself MRS: if each \(v_t\) is a nonnegative weighted sum of matroid-rank functions, then multiplying by \(\mu_t\) and summing preserves that representation. Thus the paper’s Lemma 3.2, proved here, gives concavity of the rounded welfare objective, while Lemma 3.3, also proved here, gives the \((1-1/e)\) guarantee at integral solutions. The bounded-lottery and gradient queries are simply weighted sums of the \(\tau\) type-level queries. Consequently, the paper’s convex-optimization argument should yield expected time polynomial in \(m\), \(\tau\), and the encoding length of the masses, rather than in the potentially enormous number \(N\) of residents.
This is therefore a Class A mirror for the approximation problem. The continuous population is doing real work: it replaces a sum over \(N\) repeated players by a mass-weighted sum over \(\tau\) types. The outcome space has not been continuized, and \(x\) is only the paper’s internal optimization variable, not the population object.
The further questions are whether the \((1-1/e)\) lower bound remains valid when \(\tau\) is genuinely small, whether exact welfare maximization remains hard in that regime, and how to formulate truthful payments when reports come from individual nonatomic residents rather than type blocks.
My weakest point is precisely the incentive interpretation. For a truly nonatomic population, one individual has zero influence on the aggregate distribution, so individual truthfulness becomes vacuous. The block-reporting formulation avoids that problem but makes an explicit modelling choice: identical agents report through their type cohort. I would defend the continuous welfare and MIDR allocation problem without hesitation; I would claim the full individual-level truthful mechanism only under this clearly stated type-block interpretation.
The strongest objection is that the proposed mirror does not make population mass computationally active. For every input \(\mu\), define
\[ \bar v_\mu(S)=\sum_{t\in T}\mu_t v_t(S). \]
Because MRS valuations are closed under nonnegative linear combinations,
\[ F_\mu(x) =\mathbb{E}_{S\sim r_k(x)}[\bar v_\mu(S)] \]
is exactly the paper’s original objective for one MRS valuation \(\bar v_\mu\). Equivalently, it is CPP with \(\tau\) weighted players. The population distribution disappears into a single valuation before the optimization begins. No constraint, feasible outcome, or intervention depends on population mass; the only genuine decision variable is the paper’s fractional outcome vector \(x\), not the society.
This also defeats the stronger strategic version. For truly nonatomic residents, one individual has zero effect on \(\mu\), so every report induces the same allocation and individual truthfulness is vacuous; the corresponding VCG externality is zero. Treating a whole type as a reporting block restores nontrivial payments, but changes the strategic agents from residents to coalitions. It is then simply a finite weighted-player mechanism, not the continuum limit of the paper’s individual-level truthful mechanism. The per-capita payment \(P_t/\mu_t\) is a block accounting convention, not an individual incentive guarantee.
Attempts to repair this by making \(\mu\) manipulable, imposing type quotas, allocating mass, or allowing fractional projects would produce genuinely new problems, but they would no longer mirror Theorem 3.1. Any faithful version retaining the paper’s public-project welfare objective collapses by linearity to \(\bar v_\mu\).
That is a real case against calling this a substantive continuous-population contribution: the result is an exact weighted-profile compression, and its “continuous” content is exhausted by replacing \(N\) repeated oracle calls with \(\tau\) weighted ones. However, it does not defeat the anchor under ChoCo’s stated standard. High-multiplicity compression is explicitly within scope, and a large population with repeated valuation types is a credible regime. Theorem 3.1 is a named computational result, and its convex-optimization proof transfers to the weighted instance. Thus the strategic interpretation is weak, but the welfare/MIDR mirror survives as a modest Class A high-multiplicity problem. An honest universal negative cannot be sustained.
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.