| paper | d4-conf-sagt-2016-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 25 limits what a restricted class of incentive-compatible mechanisms can achieve; it does not show that computing an allocation is hard or state an algorithmic approximation guarantee. The proposed fleet limit is a plausible asymptotic extension, but its question lacks a computational anchor in this paper.
fails bit a — no named computational result to mirror
The proposed question concerns only Theorem 25’s related-machine makespan barrier; it leaves the paper’s binary-allocation constructions, path-auction characterizations, and divisible-item result untouched.
The strongest honest anchor is Theorem 25, proved in this paper. It says that for makespan minimization on three related machines with two-value cost domains, no bribeproof \(\lambda\)-linear mechanism can approximate the optimum within a factor below \(2/\sqrt{3}\). This is an approximation barrier, not an NP-hardness or running-time result. If the anchor rule requires a complexity-class result, the paper has none; Theorem 25 is only a possible anchor if approximation guarantees count.
A concrete mirror would be High-Multiplicity Bribeproof Related-Machine Scheduling. Consider a large fleet of machines, such as a cloud or warehouse fleet. A machine’s complete type includes its cost per unit of work, \(L\) or \(H\), and any public machine attributes. The population is a rational distribution \(\mu\) over a fixed finite type set \(T\). Jobs have sizes from a finite set \(W\), with \(\nu_w\) jobs of size \(w\) per machine. At scale \(N\), there are about \(N\mu_t\) machines of each type and \(N\nu_w\) jobs of each size.
For a bundle \(B\in\mathbb N^W\), let \(b_w\) be its number of jobs of size \(w\). A limiting allocation is described by masses \(x_{t,B}\geq 0\), the fraction of the whole fleet of type \(t\) receiving bundle \(B\), satisfying
\[
\sum_B x_{t,B}=\mu_t,\qquad
\sum_{t,B}x_{t,B}b_w=\nu_w\quad(w\in W).
\]
Its makespan is
\[
C(x)=\max_{t,B:\,x_{t,B}>0}\theta_t\sum_{w\in W}w b_w.
\]
Each finite-\(N\) mechanism must assign every job integrally and pay machine \(i\) \(f_i+q_\lambda a_i\), where \(a_i\) is its assigned load and \(q_\lambda=\lambda L+(1-\lambda)H\). It must satisfy the paper’s bribeproofness condition for every pair of machines and unilateral report change. The question is to determine the infimum worst-case limiting ratio \(C/\mathrm{OPT}\) over such exactly bribeproof mechanism families, and give a family attaining the ratio with a matching lower bound. The masses \(x_{t,B}\) can be fractional even though each machine receives an integral bundle.
I would treat this as a continuum-specific question, not transferred hardness: Theorem 25’s obstruction uses just three machines and does not establish that its factor survives as type masses grow. A natural follow-up is whether that bound persists in the limit, and whether allowing mechanisms beyond the \(\lambda\)-linear class improves it.
The soft spot is substantial: this mirror preserves individual bribeproofness by defining it on finite replications, while the limit records only type masses and bundles. Theorem 25 gives no result about that limit, and it is an incentive-compatibility barrier rather than computational intractability. It supports a plausible high-multiplicity research question, but it is not a strong complexity anchor under the strict reading.
Theorem 25 is the only plausible anchor, and it is not a computational result in ChoCo’s sense. It bounds the makespan approximation achievable by a restricted class of \(\lambda\)-linear, bribeproof mechanisms. It gives no complexity bound for computing an allocation, and its conclusion is explicitly limited to that mechanism class; the paper leaves open whether other bribeproof mechanisms exist. So there is no computational result here whose population-continuous counterpart the proposed question would preserve.
The fleet scenario is plausible, and the proposed bundle masses are a sensible high-multiplicity scheduling model. But asking for the best limiting ratio over bribeproof mechanism families changes the object of study: it is a new asymptotic mechanism-design problem, not a continuous version of Theorem 25. The theorem’s three-machine bound does not itself specify an asymptotic population question or an algorithmic one.
There is also a basic tension in carrying the theorem’s defining incentive condition into a continuum. With atomless agents, one machine’s report changes no population mass, so it cannot change another machine’s allocation through the aggregate. The pairwise bribe condition that distinguishes the paper’s problem from ordinary strategyproofness therefore loses its force. One can preserve it by defining a sequence of finite fleets and requiring exact bribeproofness at each size, as the proposed mirror does. But then the operative incentive constraints belong to those finite instances, not to the limiting distribution. Makespan has a related issue: one machine of mass \(1/N\) can set the finite fleet’s maximum load and disappear from the limiting allocation distribution.
That does not show the high-multiplicity scheduling question is uninteresting; it could be worthwhile in a broader mechanism-design programme. The negative case is strongest and most honest when narrower: the paper supplies no computational anchor for ChoCo, and the best proposed mirror either loses the pairwise incentive feature in the atomless model or restores it through finite replications, yielding a different asymptotic mechanism-design project.
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.