d4-conf-ijcai-2021-0641

The strongest mirror is the paper’s single-group setting, where each person belongs to one of \(m\) disjoint groups. A convincing regime is a large survey or recruitment market: millions of potential participants fall into a few demographic strata, and people in the same stratum and cost class are interchangeable for selection. Their private cost might be the compensation they require for their time or privacy. Let the total population have mass \(1\), with group \(j\) having mass \(\lambda_j>0\). A complete type is \((j,c)\): group and true cost. The number \(N\) of people grows while the number \(\tau\) of positive-mass group-cost types stays moderate.

Here is the continuous problem I would hand to a prover: Continuous Single-Group Budget-Feasible Proportional Procurement. An instance specifies rational group masses \((\lambda_j)\), a finite rational cost domain \(K\), and budget \(B\). At execution, the mechanism receives a measure of cost reports in each group; it does not know the true cost distribution. It chooses, for each reported cost \(b\), a selection rate \(q_j(b)\) and an expected per-person transfer \(p_j(b)\). The selected mass at that report is the reported mass times \(q_j(b)\), and total transfers must be at most \(B\) for every report measure.

Require dominant-strategy truthfulness for an infinitesimal individual, individual rationality, and budget feasibility. In particular, holding the other agents’ mass fixed, a person of cost \(c\) must prefer reporting \(c\): \(p_j(c)-c q_j(c)\ge p_j(b)-c q_j(b)\) for every report \(b\). At truthful costs \(\mu_{j,c}\), the achieved representation is
\[ \mathrm{ALG}(\mu)=\min_j \frac{\sum_c \mu_{j,c}q_j(c)}{\lambda_j}. \]
The natural benchmark is the maximum representation obtainable with costs known, allowing selection of fractional mass:
\[ \mathrm{OPT}(\mu)= \max_{0\le y_{j,c}\le \mu_{j,c}} \min_j \frac{\sum_c y_{j,c}}{\lambda_j} \quad\text{subject to}\quad \sum_{j,c} c\,y_{j,c}\le B. \]
A \(\rho\)-approximation has \(\mathrm{ALG}(\mu)\ge \mathrm{OPT}(\mu)/\rho\) for every truthful cost distribution. A solution to the mechanism-design problem is an explicit, computationally efficient rule taking reported mass measures to selection rates and transfers, with proofs of its incentive, budget, and approximation guarantees. Its running time should be measured in \(m,\tau,L\), where \(L\) is the binary input length.

Theorem 4, proved in this paper, is my lead anchor. It says that BPSG achieves a \((3+\alpha)\)-approximation when it selects at least one agent from every group, where \(\alpha=n_{\max}/n_{\min}\) and the achieved minimum selection ratio is at least \(1/n_{\max}\). It also says that if BPSG cannot select even one agent from each group, so its achieved ratio is zero, no budget-feasible proportion-representative mechanism can achieve any positive ratio on that instance. Its continuous question is whether a mass-based, threshold-payment analogue achieves a factor bounded by \(3+\alpha\), with \(\alpha=\lambda_{\max}/\lambda_{\min}\), and what factor is optimal. I expect this to be Class A: with finitely many cost classes, candidate thresholds are finite, and the required mass for each group and its cost can be computed from sorted cost classes and piecewise-linear optimization. The paper’s common selection-ratio objective and private-cost procurement remain intact.

The zero-result branch of Theorem 4 needs a careful continuous translation. If costs are bounded and \(B>0\), the planner can generally buy a sufficiently small positive mass from every group. Thus the “cannot select one agent” obstruction is an indivisibility effect; its counterpart is a degenerate case such as \(B=0\), not a substantive positive-budget lower bound. The paper’s positive-ratio approximation guarantee is the stronger anchor for this mirror.

Theorem 5, also proved in the paper, supplies a useful second anchor: no budget-feasible proportion-representative mechanism achieves an approximation better than \(\Omega(\alpha)\), with \(\alpha=n_{\max}/n_{\min}\); the lower bound also applies to the multiple-group setting. Its continuous question is whether every mechanism in the defined model has worst-case approximation factor \(\Omega(\lambda_{\max}/\lambda_{\min})\) as group masses become imbalanced, even with unlimited computation. A solution is either a lower-bound proof for mass distributions or a mechanism that beats this dependence. I expect a Class B-style transfer of the approximation obstruction: \(\alpha\) measures relative group masses, not population size, and budget-feasible truthful procurement is still the operative problem. This is an approximation lower bound, not an NP-hardness claim.

The weakest point is whether the exact \(\Omega(\alpha)\) lower bound survives fractional selection. The discrete proof might depend on one-person granularity, and partial selection of a cost cohort could remove that construction. The same issue may improve Theorem 4’s factor: ceilings and the requirement to buy a whole person disappear. I would ask the prover to determine those effects directly rather than promise that either numerical bound carries over unchanged.

This remains the authors’ problem: the planner buys participation from private-cost agents under a hard budget while seeking proportional representation and truthful behavior. The continuum changes the population unit to mass; it does not replace their objective with an outcome-space or axiomatic question. The main scope claim is deliberately narrow: a strong single-group mirror for Theorems 4 and 5, with multiple-group models left as follow-on work.