| paper | d4-conf-atal-2024-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given a rational finite-support society μ of unit-size transaction types and capacity shares \(0<κ<ρ<1\), let reports form a mass distribution ν; include the top ρ mass and confirm the top κ mass. Optimize over anonymous linear rebate rules \(R_C^K(ν)=a+\int Q^C_ν(q)\,dK(q)\) and \(R_U^K(ν)=a+\int Q^U_ν(q)\,dK(q)\), where \(K\) is a finite signed measure over included ranks and the quantiles use the leave-one-out, one-sided rank limits for confirmed and unconfirmed units. For every ν, require restricted truthfulness and user individual rationality, require \(κ R_C^K+(ρ-κ)R_U^K\le κ p_{\mathrm{in}}\), and maximize \(f\) subject to \(κ R_C^K\ge fκ p_{\mathrm{out}}\). Here \(p_{\mathrm{in}}\) is the lowest confirmed-side cutoff bid and \(p_{\mathrm{out}}\) the highest unconfirmed-side cutoff bid, allowing a gap between them. Return the optimal rule and its allocation and payments on μ.
A proportional-capacity auction over a rational distribution of transaction types, with mass ρ included and mass κ confirmed. Anonymous linear rebates depend on leave-one-out rank quantiles; distinct one-sided cutoff bids determine rebates to confirmed and unconfirmed mass. The design maximizes the worst-case fraction of gross VCG payments returned to confirmed mass subject to restricted truthfulness, user IR, and the approximate miner-revenue bound.
The proposed single rebate for all included mass misses the finite mechanism’s distinct \(b_k\) and \(b_{k+1}\) rebates when a positive-mass bid gap straddles the confirmation boundary.
fatal: False
Covers Theorem 4’s optimal linear-rebate design with proportional capacities. It does not establish that the paper’s strategic-miner manipulation results, including Theorems 5–7, survive without a specified positive mass of fake transactions; it also leaves the impossibility results aside.
The paper has no named theorem classifying a problem as in P, NP-hard, or otherwise. I see one useful anchor under your allowance for a formulation that the paper actually solves: Theorem 4, proved here. For \(n\ge k+2\), it gives the unique R-TFRM solution in the paper’s deterministic, anonymous linear-rebate class: the worst-case fraction rebated to the top \(k\) users is \(f^*=k/n\), with \(c_k^*=k/n\) and \(c_i^*=0\) for every \(i\ne k\). This is an exact optimization result, not a complexity classification.
A plausible regime is a large rollup or batch market processing many standardized, one-slot transactions in an epoch. There might be \(N\) requests but only \(\tau\ll N\) distinct user types: each type has a particular value for confirmation and the same transaction size. Let \(\mu_t\) be the fraction of requests of type \(t\). Suppose the batch service provisions capacity proportionally to demand: it includes mass \(\rho\) and confirms mass \(\kappa\), where \(0<\kappa<\rho<1\). This is the paper’s homogeneous unit-demand auction at high multiplicity: an individual transaction still gets an integral outcome, while the mass selected from a type can be fractional.
I would ask one question, Continuous Robust Redistribution Design. Its input is a finite rational value set \(T\), a rational society \(\mu\) over \(T\), and rational capacity shares \(\kappa,\rho\). Given reports, include the highest-bid mass \(\rho\), confirm the highest-bid mass \(\kappa\), and leave the rest of the included mass as price-setting transactions. Find an anonymous linear rebate rule \(K\) and the largest \(f\) such that, for every report distribution \(\nu\), the rule is restricted truthful for agents already included, gives included users nonnegative utility, and satisfies the paper’s approximate miner-revenue bound. Specifically, if \(Q_\nu\) is the descending bid quantile among included mass and \(P_\nu\) is the critical opponent bid for confirmation, each included unit receives \(r_K(\nu)=a+\int_{[0,\rho]}Q_\nu(q)\,dK(q)\). The constraints are \(\rho r_K(\nu)\le\kappa P_\nu\) and \(\kappa r_K(\nu)\ge f\kappa P_\nu\); the first bounds total rebates, and the second defines the guaranteed fraction returned to confirmed users. A solution is the rule \(K\), its guarantee \(f\), and the resulting allocation and payments for \(\mu\). Requiring the constraints for all \(\nu\), rather than just the supplied society, preserves the paper’s worst-case design objective.
The expected answer is tractable. The mass-scale counterpart of Theorem 4 is \(r(\nu)=(\kappa/\rho)P_\nu\), corresponding to \(K=(\kappa/\rho)\delta_\kappa\) and \(a=0\). It gives total rebates \(\kappa P_\nu\), so it meets the approximate miner bound, and returns fraction \(\kappa/\rho\) of the gross VCG payments. A constant positive bid profile gives the matching upper bound \(f\le\kappa/\rho\). Applying the rule to the input society requires sorting its \(\tau\) reported types and accumulating their rational masses, so evaluation is polynomial in \(\tau\) and the input bit length \(L\). The bridge is direct: if \(n/N\to\rho\) and \(k/N\to\kappa\), then \(k/n\to\kappa/\rho\).
The mirror is plausible because it keeps the paper’s transaction auction, confirmation objective, price-setting mass, and redistribution question; only the population and capacities become mass quantities. It covers Theorem 4’s optimal linear-rebate design, not the paper’s impossibility results or its claims about manipulation by a strategic miner.
The soft spot is that this result may be little more than a scaled limit of the paper’s finite LP. It gives a credible, narrow tractability mirror, but not much of a new complexity landscape. Also, in an atomless population, one user’s bid has zero effect on the aggregate, and a single fake transaction has zero mass. So the mirror does not automatically preserve the finite market’s strategic-miner challenge: modeling that would require a specified positive mass of miner-generated transactions. The proportional-capacity regime also fits expanding batch or sharded services better than a single fixed-capacity block. Natural follow-ups are to allow positive fake mass, require full UIC for users outside the included set, or permit transactions of different sizes.
The strongest case against this anchor is that Theorem 4 does not expose a computational landscape for continuization to chart. It gives a closed-form optimum: \(c_k^*=k/n\), with all other coefficients zero. In the proposed mass model, the corresponding coefficient is simply \(\kappa/\rho\). The society \(\mu\) does not affect that design; sorting its \(\tau\) types only applies the already-specified mechanism. That is a plausible continuous limit, but its main result is a scaling identity, not a new computational question about populations.
There is also a mismatch in the proposed mirror. In the finite mechanism, a confirmed user gets rebate \((k/n)b_{k+1}\), while an included but unconfirmed user gets \((k/n)b_k\). If the cutoff falls between two positive-mass bid types, the gap between \(b_k\) and \(b_{k+1}\) persists as the population grows. A single quantile rebate \(r_K(\nu)\) for every included unit therefore is not generally the limit of the paper’s mechanism. One can repair the model with separate one-sided cutoff quantiles for confirmed and unconfirmed mass. But then the design still reduces to the same scalar coefficient and remains independent of \(\mu\).
A fixed-capacity block also does not supply the proposed positive mass of included transactions: as the mempool grows, the included share tends to zero, while the rebate mechanism still acts on finitely many slots. The proponent’s scalable batch or rollup regime avoids that degeneracy, but it does so by scaling capacity with the population. That is plausible for some services, though it is a different operating regime from a fixed-capacity block.
So the negative case is limited. A scalable batch market is a sensible high-multiplicity scenario, and the repaired mass version is well-posed. The case against is that this paper offers little for ChoCo’s computational programme: its best anchor appears to yield a short asymptotic reformulation of an already solved optimization, rather than a complexity result or an algorithmic frontier.
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.