| paper | d4-conf-aaai-2005-0003 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A deterministic polynomial-time algorithm attains the \(1-2^{-k}\) welfare approximation guarantee. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(\ell\) Boolean variables and \(\tau\) clause types \((C_j,v_j)\), each with at least \(k\) literals, positive rational per-capita value \(v_j\), and positive rational mass \(\mu_j\) summing to \(1\), return an assignment \(x\) such that \(W_\mu(x)=\sum_{j=1}^{\tau}\mu_jv_j\mathbf{1}[x\models C_j]\ge(1-2^{-k})\max_y W_\mu(y)\). What running time is achievable in \(\ell,\tau\), and the binary input length?
The society is a finite-support distribution over complete clause and value types \((C_j,v_j)\). Every unit of mass faces the same Boolean assignment \(x\); the objective is per-capita satisfied value, \(\sum_j\mu_jv_j\mathbf{1}[x\models C_j]\).
The objective rewrites as weighted clause satisfaction, so the paper’s conditional-expectation proof appears to supply the same approximation immediately; this limits what remains to prove but does not erase the distributional input model.
fatal: False
Covers the welfare-approximation component of Theorem 2 for known \(k\)-SAT. It leaves out individual truthfulness and critical payments, the unknown-domain characterization, and the paper’s other application results.
My lead is Population Weighted \(k\)-SAT Welfare. It keeps the paper’s social choice problem intact: the outcome is still one Boolean assignment, and each agent still values an outcome according to whether their clause is satisfied. Only the population changes from a finite list of agents to a distribution over agent types.
An instance has \(\ell\) Boolean variables and a finite support \(\{(C_j,v_j,\mu_j)\}_{j=1}^{\tau}\). Each \(C_j\) is a clause with at least \(k\) literals, \(v_j>0\) is the value of agents with that clause, and \(\mu_j>0\) is their share of the population, with \(\sum_j\mu_j=1\). A type is the complete pair \((C_j,v_j)\); mass \(\mu_j\) means that fraction of society has that type. Given an assignment \(x\in\{0,1\}^{\ell}\), per-capita welfare is
\[
W_\mu(x)=\sum_{j=1}^{\tau}\mu_jv_j\,\mathbf{1}[x\models C_j].
\]
The problem is to return an assignment satisfying
\[
W_\mu(x)\ge (1-2^{-k})\max_{y\in\{0,1\}^{\ell}}W_\mu(y).
\]
A prover would receive the clauses, binary rational values and masses, and be asked for such an assignment. The natural target is polynomial time in \(\ell,\tau\), and the input bit length.
The anchor is Theorem 2, proved in this paper. It says that the conditional expectation algorithm is truthful for the known \(k\)-SAT domain, where clauses are public and values are private, and achieves a \((1-1/2^k)\)-approximation in polynomial time. The mass version has the same welfare objective with each clause’s contribution weighted by its population share. Conditional expectations can be computed from those weighted contributions, so the theorem gives a concrete reason to expect the approximation problem to remain tractable. The example regime is a large population of stakeholders expressing needs over a small set of binary policy or design choices: many people, relatively few recurring clauses and value tiers, with the designer knowing each need type.
This is a Class A case for the approximation problem. It does not claim that exact optimization is easy, or that the approximation dissolves a hardness result: the provided paper has no numbered hardness anchor to mirror. Nor does this mirror cover the full incentive result. Theorem 2’s truthfulness and critical payments refer to an individual’s report changing the finite profile. A normalized population distribution alone does not specify the granularity of an individual deviation, so I would leave a continuous truthfulness and payment theorem as a follow-up question rather than claim it comes for free.
The mirror covers the paper’s known SAT welfare result only. Its main soft spot is that this captures the objective and algorithmic approximation more directly than the paper’s mechanism-design contribution. I think the authors would recognize the weighted clause-satisfaction problem as their central computational task, while reasonably asking for a separate model before accepting a claim about continuous incentive compatibility. Further questions include whether exact welfare optimization is tractable when parameterized by support size, and how the known-case result changes when satisfying clauses are private, as in the unknown domain.
The strongest negative case is that the proposed mirror drops the paper’s central mechanism-design distinction. In Theorem 2, values are private reports and the result combines a welfare approximation with truthfulness. If an atomless society reports a distribution over clause and value types, one person’s report has zero effect on that distribution. Truthfulness is then vacuous for an allocation based on the distribution; recovering a nontrivial incentive question would require a different model, such as strategic cohorts with positive mass. The proposed optimization problem instead treats the distribution as known input, so it mirrors only the welfare part of the theorem.
There is also a serious novelty objection to that welfare part. Set \(w_j=\mu_jv_j\). The proposed objective becomes \(\sum_j w_j\mathbf{1}[x\models C_j]\), exactly the weighted clause-satisfaction objective covered by Theorem 2’s conditional-expectation algorithm, which permits arbitrary agent values. For this task, the mass-and-value representation adds no computational structure: the solver only sees the clause weights. One could argue the paper has already solved the proposed mirror, rather than presenting it as a new complexity question.
But those objections do not sustain the universal negative claim. Theorem 2 explicitly includes an approximation result, and the programme allows one result to anchor a mirror. More importantly, a large population with recurring, publicly known needs over shared policy choices is a credible high-multiplicity regime; the support-size representation is meaningful for it. The programme also says a known answer does not itself defeat a well-posed mirror. So the honest negative case is weak: the incentive-theoretic extension may degenerate, and the welfare mirror may be settled by the paper’s existing algorithm, but I cannot make a convincing case that no worthwhile continuous mirror exists.
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.