| paper | d4-journals-geb-2015-0099 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 4.4
statement extracted from the paper’s text layer
Given a population scale \(N\), budget \(B\), and finite-support rational distribution \(\mu\) over verified-bit, linear-cost types \((b,v)\), choose a submeasure \(\xi\le\mu\) with \(\xi_{(b,v)}=r(v)\mu_{(b,v)}\) for a common selection rate \(r(v)\in[0,1]\). Maximize selected mass \(q=\|\xi\|\) subject to \(qv_q/(1-q)\le B\) and \(q\le 1-1/N\), where \(v_q\) is the cutoff in the marginal valuation distribution and partial selection at a tie is allowed. Return the threshold allocation and payment, with per-selected-person privacy level \(\epsilon=1/[N(1-q)]\) and payment \(v_q/[N(1-q)]\), and the estimate \(\hat{s}=\int b\,d\xi+(1-q)/2+\operatorname{Lap}(1-q)\) of the normalized statistic \(\int b\,d\mu\).
A finite-support mass procurement auction over \((b,v)\): select the cheapest \(q\) mass by \(v\), at a common cutoff price, without conditioning selection on \(b\); optimize \(q\) under the budget and use the paper's normalized midpoint-plus-Laplace estimator. Individual incentives retain the \(N\)-scaled privacy and payment terms, so their exact nonatomic interpretation must be specified.
At the strict nonatomic limit, one person's report cannot change the cutoff, while their privacy loss and payment vanish with \(N\); the proponent flags this but does not fully specify how the finite auction's truthfulness claim carries over.
fatal: False
The mirror covers FairQuery's budget-constrained accuracy objective and the optimality claim in Proposition 4.4, with Theorem 4.1 supporting the mechanism's guarantees. It leaves the privacy bounds in Section 3, the minimum-payment result in Section 4.2, and the sensitive-value impossibility in Theorem 5.1 without a mirror.
The strongest case is a narrow mirror of the paper’s budget-constrained procurement problem. A plausible regime is a very large patient or customer population in which many people share the same private bit and privacy cost. Let a type be \(t=(b,v)\), where \(b\in\{0,1\}\) is the bit and \(v\) is the parameter in the linear cost function \(c(v,\epsilon)=v\epsilon\). The society is a rational distribution \(\mu\) over these types, with support size \(\tau\ll N\), where \(N\) is the population scale. Mass is the fraction of people of each type.
The best named anchor is Proposition 4.4, proved in this paper. It says that for every valuation vector \(v\), FairQuery attains the highest accuracy possible under budget \(B\) among truthful, individually rational, envy-free fixed-purchase mechanisms. FairQuery buys privacy from the largest affordable number of people, all at the same privacy level, using a uniform price. This is an algorithmic mechanism result, though the proposition does not itself classify a problem as being in P; the paper proves no named complexity classification or hardness result.
A continuous counterpart would be Continuous FairQuery. Its instance is a population scale \(N\), a finite-support rational distribution \(\mu\) over \((b,v)\), and a budget \(B\). The mechanism chooses a selected submeasure \(\xi\leq\mu\), with the same selected fraction for both bit values at each valuation \(v\), so selection does not depend on \(b\). Write \(q\) for the selected mass and \(v_q\) for its marginal valuation—the cutoff among the cheapest \(q\) mass. The mechanism buys privacy level \(\epsilon=1/[N(1-q)]\) from selected individuals and pays each the cutoff price \(v_q/[N(1-q)]\). Its total payment is \(qv_q/(1-q)\). It outputs the selected bit mass, plus \((1-q)/2\), plus Laplace noise of scale \(1-q\). The question is to choose a cheapest-mass selection and \(q\) that maximize \(q\), subject to \(qv_q/(1-q)\leq B\), and return the allocation, price, and estimator. Here \(N\epsilon\) is the scaled privacy level: each represented individual has sensitivity \(1/N\), so the normalized Laplace scale is \(1-q\). The midpoint estimate has worst-case bias at most \((1-q)/2\); the Laplace noise gives the paper’s corresponding \(2/3\)-probability error bound of \((1/2+\ln 3)(1-q)\).
This mirror should be tractable for finite rational support: sort the valuation levels and scan the quantile breakpoints, with partial selection at a tie. That gives a direct continuous optimization counterpart to FairQuery’s budget-versus-accuracy objective. The authors would likely recognize it as their privacy procurement problem expressed in mass units, with the population normalization and per-capita privacy scaling made explicit. It covers the paper’s fixed-purchase, budget-constrained result; it does not mirror the sensitive-value impossibility result or the whole paper.
The weak point is that the paper studies privacy markets and mechanism design, not computational social choice. Its result is also already simple to compute by sorting in the finite model, so the continuous version mainly sharpens a high-multiplicity formulation rather than opening a substantial new complexity landscape. Truthfulness needs care in the mass model: with nonatomic agents, one person cannot affect the cutoff, so incentive constraints can become weak. That does not erase the population mirror, but it limits how much computational content this particular anchor can support.
Proposition 4.4 is the only plausible anchor, but the best case against it is that it proves mechanism-design optimality, not a complexity classification. Once the paper restricts attention to fixed-purchase mechanisms, the computation is sorting valuations and finding a cutoff. The proposed mass version replaces that order statistic with a quantile. It yields a clean limit formulation, but it does not expose the kind of computational bottleneck—such as pricing over exponentially many variables—that makes a continuization especially valuable to this programme.
There is a more structural concern: a distribution over types records masses, while truthfulness and individual rationality concern what happens when one person changes their report or opts out. In the proposed scaling, with selected fraction \(q\) in a population of size \(N\), each selected person has privacy level \(1/[N(1-q)]\) and receives payment on the order of \(1/N\). In a literal nonatomic limit, those individual quantities vanish. Keeping \(N\) and the \(1/N\)-sized agent deviations preserves the mechanism, but makes the mirror a high-multiplicity sequence of finite auctions rather than a standalone continuum problem.
That objection does not defeat the anchor. A large population with repeated \((b,v)\) types is a sensible regime, and the authors could reasonably recognize the mass formulation, including the population scaling, as their problem. The paper’s computation being simple is not enough to rule it out under the programme’s stated standard. So the negative case is weak: I cannot honestly claim that no worthwhile continuous mirror survives.
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.