| paper | d4-conf-atal-2011-0278 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in the stated parameters. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given a finite set of complete report types \(T\) with rational masses \(\mu_t\) summing to \(1\), evaluation scale \(M\), rational \(\varepsilon\in(0,1)\), weight \(\alpha\), per-capita reward \(v\), and tables \(x_{t,u}\in\{1,\ldots,M\}\) and \(y_{t,u}\in\Delta_M\), compute each type’s per-member share to additive error \(2^{-q}\). Here \(x_{t,u}\) is type \(t\)’s evaluation of type \(u\), and \(y_{t,u}\) is its prediction of the ratings received by type \(u\). Define \(X_{u,k}=(1-\varepsilon)\sum_t\mu_t\mathbf{1}[x_{t,u}=k]+\varepsilon/M\), \(Y_{u,k}=\exp(\sum_t\mu_t\ln((1-\varepsilon)y_{t,u,k}+\varepsilon/M))\), and \(R_{t,u}=\sum_k\mathbf{1}[x_{t,u}=k]\ln(X_{u,k}/Y_{u,k})+\sum_kX_{u,k}\ln(((1-\varepsilon)y_{t,u,k}+\varepsilon/M)/X_{u,k})\). With \(a_t=\sum_u\mu_u x_{t,u}\), the requested share is \(g_u=v\sum_t\mu_t x_{t,u}/a_t+\alpha\sum_w\mu_wR_{u,w}\).
A continuum of evaluator and recipient types carries masses \(\mu_t\); each type has the same mechanism-relevant reports and beliefs. The input gives the type-pair evaluation and prediction tables, and the output is each type’s per-member share under reward supply \(v\) per unit of population mass. The computation uses mass-weighted rating frequencies, geometric prediction aggregates, and incoming evaluations normalized by each evaluator type’s average rating.
The paper’s independent-signals assumption sits uneasily with assigning every evaluator the same rating to all members of a recipient type, and the proponent does not show that this block-homogeneous profile is compatible with the Bayesian signal model.
fatal: False
The mirror covers Proposition 3’s share computation on block-homogeneous reports; it does not establish the incentive-compatibility, fairness, or individual-rationality results, and leaves Section 4’s empirical findings outside.
The best positive case is one anchor, and it is the paper’s only named computational tractability result: Proposition 3, proved here. It says the proposed mechanism computes all agents’ shares in \(O(n^3M)\) time: normalization takes \(O(n^2)\), and the evaluation, truth-score, and final-share calculations together take \(O(n^3M)\). The paper gives no comparable NP-hardness result, so this is the right algorithmic lead. Its computational task is to calculate the mechanism’s allocation from reported opinions; it is not an optimization problem, and there is no separate objective to minimize or maximize.
A plausible regime is a very large collaborative workforce sharing a homogeneous task bonus. Participants fall into a moderate number \(\tau\) of role and contribution classes. Within a class, participants are indistinguishable for this mechanism: they make the same evaluation of every recipient class, predict the same rating distribution for its members, and have the same relevant beliefs and other mechanism-relevant attributes. A type \(t\) is that complete description; its mass \(\mu_t\) is the fraction of the workforce in the class. Think thousands or millions of participants, but a much smaller support of types. Each member still receives an individual share. The mechanism can use type-level reports because every member of a recipient type gets the same reports from each evaluator type.
Here is the continuous problem I would hand to a prover. Call it Continuous BTS Reward-Share Computation. An instance gives a finite support \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), an evaluation scale \(M\), recalibration parameter \(\varepsilon\), weight \(\alpha\), and reward supply \(nv\) for a discrete population of \(n\) agents, so the reward per unit of population mass is \(v\). For each pair of types \(t,u\), it gives an evaluation \(x_{t,u}\in\{1,\ldots,M\}\) that a member of \(t\) reports for each member of \(u\), and a prediction vector \(y_{t,u}\in\Delta_M\) for the evaluations members of \(u\) receive. The task is to output the mechanism’s per-person share for every type, or approximate each share to additive error \(2^{-q}\) for requested precision \(q\).
For each recipient type \(u\), define its smoothed frequency of rating \(k\) and the geometric aggregate prediction by
\[
X_{u,k}=(1-\varepsilon)\sum_t\mu_t\mathbf{1}[x_{t,u}=k]+\frac{\varepsilon}{M},
\qquad
Y_{u,k}=\exp\left(\sum_t\mu_t\ln\left((1-\varepsilon)y_{t,u,k}+\frac{\varepsilon}{M}\right)\right).
\]
The BTS score for an evaluator of type \(t\) assessing a member of type \(u\) is
\[
R_{t,u}
=
\sum_{k=1}^M \mathbf{1}[x_{t,u}=k]\ln\frac{X_{u,k}}{Y_{u,k}}
+
\sum_{k=1}^M X_{u,k}
\ln\frac{(1-\varepsilon)y_{t,u,k}+\varepsilon/M}{X_{u,k}}.
\]
Let \(a_t=\sum_u\mu_u x_{t,u}\). The output share for a member of type \(u\) is
\[
g_u
=
v\sum_t\mu_t\frac{x_{t,u}}{a_t}
+
\alpha\sum_w\mu_w R_{u,w}.
\]
The first term is the limiting incoming-evaluation share; the second is that member’s average truth-telling score weighted by \(\alpha\). These are the paper’s normalization and share formulas with sums over agents replaced by mass-weighted sums. A share vector is the solution; there is no choice of report or optimization over allocations in this computation task.
I expect this mirror to be tractable. The finite-support input allows direct aggregation over type pairs and rating levels, in \(O(\tau^2M)\) arithmetic operations. With rational input and a requested precision \(q\), the logarithms can be approximated in time polynomial in the input bit length and \(q\); the smoothing parameter keeps their arguments bounded away from zero. This is the type-level counterpart of Proposition 3’s polynomial-time computation. Integrating the output shares over types also gives total reward \(v\), consistent with budget balance.
The mirror covers Proposition 3, not the paper’s whole result set. It is plausible that the authors would recognize it: the mechanism still divides a joint reward using peers’ evaluations and predictions, and applies the same Bayesian truth serum calculation. The continuum represents many indistinguishable participants, not fractional outcomes for a finite set of agents.
The weak point is the cohort assumption. The paper’s mechanism elicits opinions about named peers, while this mirror assumes members of a recipient type are indistinguishable to evaluators and receive the same report. That is plausible for a large, anonymous workforce with repeated roles and contribution classes, but it is narrower than the paper’s general model. A further question is whether the paper’s incentive-compatibility, fairness, and individual-rationality results extend under the corresponding nonatomic Bayesian assumptions. Another is how accurately the type-level formula approximates finite populations when cohort reports vary or the excluded self-report still matters. Those are extensions, not extra anchors: Proposition 3 is the single computational result this case rests on.
Proposition 3 is a genuine computational result, so the “no named result” objection does not apply. The strongest case against its mirror is that the result concerns evaluating a fully specified formula, not finding or optimizing anything. The input already contains every agent’s evaluation and prediction; the mechanism then calculates each share. In fact, its aggregates can be precomputed once per recipient, giving an \(O(n^2M)\) calculation from the paper’s explicit reports. With the proponent’s compressed type input, the same calculation takes \(O(\tau^2M)\), essentially linear in the size of that input. That is a valid compressed-input version of Proposition 3, but it offers little of the algorithmic question the programme is designed to uncover: there is no hidden search, pricing problem, or structural optimization to resolve.
The difficulty is making that compression faithful to the paper’s model. A type must include an agent’s relevant opinions and beliefs. Here, opinions concern named peers, and the paper assumes an agent’s signals about different peers are independent. Grouping many recipients into one type and having each evaluator assign them the same rating makes those signals perfectly correlated, unless they are deterministic. Grouping evaluators likewise requires their reports and relevant beliefs to match across recipient types. One can certainly posit a block-homogeneous workforce, but that is a narrow restriction on the subjective information the mechanism was built to elicit. Alternatively, define types by complete opinion profiles; then independent signals give those profiles many possible combinations, and a small support \(\tau\) is no longer a natural large-population regime.
A better attempt would retain independent, recipient-specific reports and model their distribution within each role class. But then the task is to compute expected shares under a new stochastic model, not the shares from a type-compressed report profile. The BTS score uses logarithms of recipient-specific empirical frequencies and predictions, so replacing reports by their type-level averages does not generally preserve the expected score. This could be an interesting new model, but it needs additional assumptions about the joint distribution of evaluations and predictions; it is not a direct continuization of Proposition 3.
Even granting the proponent’s cohort scenario, the resulting mirror remains well-posed and recognizable. The negative case is therefore about its value to this programme, not its validity: it gives a straightforward arithmetic translation of an already tractable computation, while preserving the mechanism’s intended informational structure seems to erase the small-support advantage. I cannot make that a decisive objection. A reader who regards compressed computation itself as a worthwhile result may reasonably keep this anchor.
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.