| paper | d4-conf-aaai-2015-0421 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
For a sequence of search instances with fixed τ cohort types \(t_j\), counts \(n_j(N)/N\to\mu_j>0\), type search sets \(A_j^{(N)}\), and common intersection \(D_N=\bigcap_j A_j^{(N)}\), assume \(|D_N|/N\to\infty\) and each \(r_j=\lim_N |A_j^{(N)}|/|D_N|\) exists. Run Mechanism 1 and let \(p_j^{(N)}\) be a type-\(j\) agent's simplified-game win probability. Characterize the limiting type allocation shares \(q_j=\lim_N n_j(N)p_j^{(N)}\) and the limiting expected-total-digs ratio to the simplified-game benchmark; in particular, does \(\limsup_N \mathbb{E}[\#\text{ digs with mechanism}]/\mathbb{E}[\#\text{ digs in benchmark}]\le 1/(2R)\) hold for \(R=\min_j r_j\)?
Represent the population by masses μ over a fixed support of cohort types, each type carrying the search set and other problem-relevant features. Keep the location space finite in each instance and the treasure and each assigned location discrete; use a sequence with per-type counts approaching the masses. Mechanism 1 assigns each location in the common intersection to one individual, while its type-level assignment shares \(q_j\) are the continuous aggregates and digging cost is measured by the same benchmark ratio.
A limiting mass vector alone does not specify the search-space growth needed for the type allocation shares; the proponent specifies growth of the common intersection and only the minimum set-size ratio, so the mirror should also fix each type's limiting ratio.
fatal: False
The mirror carries Theorem 3's one-shot welfare guarantee and uses the benchmark comparison in Theorem 2. It does not independently carry Theorem 1's incentive claim, Theorem 4's participation bound, or the composable-coalition results in Theorems 5 and 6.
The paper gives a plausible population-level follow-on, but it has no eligible computational-complexity anchor under your rule. The numbered results concern mechanism properties: Theorem 1, proved by the authors, says that in Mechanism 1 an agent maximizes their chance of finding the treasure by reporting truthfully when everyone else reports truthfully. Theorem 2 says each agent’s win probability under the mechanism equals their probability in the simplified exploration game. Theorem 3 proves that expected digging cost under the mechanism is at most the benchmark cost and, with \(R=\min_i |S_i|/|S_N|\), bounds the cost ratio by \(\frac{n}{2(n+1)R}(1+\epsilon)\), where \(\epsilon\to0\) as \(|S_N|/n\to\infty\). Theorem 4 bounds the voluntary-participation loss; Theorems 5 and 6 concern coalitions and joining order. None classifies an underlying problem as polynomial-time solvable, hard, or parameterized. The paper mentions efficient computation of the winning probabilities in its full version, but that claim is not a numbered result in the supplied text.
The strongest plausible *follow-on mirror* is a high-multiplicity limit of the one-shot fair search allocation problem. Imagine many miners or research teams, grouped into a small number \(\tau\) of cohorts. A type \(A_j\) is the complete description of a cohort’s candidate search set and every other problem-relevant feature, such as its search speed and costs. The mass \(\mu_j\) is the cohort’s fraction of the population. Each type’s set contains the actual treasure location; the common intersection is \(D_N\). The scenario is plausible when many agents share a few search profiles and the common candidate set is large relative to the population. Repeated mining work units or labs using the same candidate map are possible examples. The paper’s randomness over treasure locations and assignments is not itself a continuous population; the proposed mirror puts the population distribution at the center.
One precise candidate is Mass Fair Search Allocation. Its instances are sequences of finite search problems indexed by population size \(N\), with \(\tau\) fixed, \(n_j(N)/N\to\mu_j>0\), common intersection \(D_N\), and \(|D_N|/N\to\infty\). Assume the ratios \(\min_j |A_j|/|D_N|\) converge to \(R\), and the treasure is uniform on \(D_N\). A solution is an allocation rule that assigns each location in \(D_N\) to exactly one agent, treats agents within each type symmetrically, and has a type-level limit: \(q_j\) is the share of locations assigned to type \(j\), with \(\sum_j q_j=1\). Require truthful reporting to maximize a tagged agent’s chance of winning against truthful reports by the others; require the type’s per-agent winning rate, scaled by \(N\), to match its simplified-game benchmark; and ask for a rule whose limiting expected digging-cost ratio is at most \(1/(2R)\). The finite mechanism suggests \(q_j\) as the limiting aggregate of that type’s individual winning probabilities.
I would expect this restricted question to be tractable: it appears to reduce to computing the benchmark rank probabilities and converting them into type-level allocation shares. Theorem 1 supplies the closest named result for the truthfulness condition, and Theorems 2–3 supply the fairness and welfare targets. This candidate covers the paper’s one-shot mechanism results; I would leave the composable-coalition results outside its scope.
The weakest point is substantial: the continuous question above is a limit problem for mechanism guarantees, not a complexity result established by this paper. An individual’s probability of winning shrinks with \(N\), so the limit needs a tagged agent and a normalized win rate. That construction preserves an individual incentive question, but the authors might regard it as a new asymptotic model. The paper’s finite-set types may also proliferate with the population, undermining the intended \(\tau\ll N\) regime. So there is an honest continuous-population research question here, but no qualifying anchor from which to claim that this paper has already opened the programme’s computational landscape.
The strongest objection is a mismatch with ChoCo’s computational target. Theorem 1 proves a truthfulness property; Theorem 2 identifies a win probability with its benchmark value; Theorem 3 bounds expected search cost. None classifies the complexity of a computational problem. The paper says the winning probabilities can be computed efficiently in its full version, but that does not give a named complexity result or an algorithmic problem over continuous populations. These theorems analyze a specified mechanism.
The proposed cohort model also has trouble carrying Theorem 1’s incentive question. One agent’s report can change the intersection of *all* reported sets, and thus change which locations remain eligible for the treasure. A population distribution \(\mu\) records positive-mass types; a zero-mass tagged agent does not change its support or essential intersection. Giving a whole cohort positive mass restores its ability to affect the intersection, but then the deviation is by the cohort, not by the unilateral agent in the theorem. A finite-population sequence with a tagged agent and a normalized win probability can preserve that distinction, but the incentive depends on the tagged perturbation as well as \(\mu\). That hybrid model may be coherent; it is not an incentive question determined by the continuous society alone.
Theorem 2 is easier to carry over, but it supplies little computational content: the mechanism assigns locations according to the benchmark winning probabilities, so equality follows from the construction. A type-level share \(q_j\) can aggregate those probabilities. Computing such shares would amount to taking a limit of the finite mechanism’s calculation. Asking instead for the optimal fair allocation would add an optimization problem that these results do not pose.
Theorem 3’s asymptotic regime makes the model harder to stabilize. Its bound uses \(|S_N|/n\to\infty\). With a fixed finite search space, that regime fails as the population grows. Expanding the search space requires a sequence of changing type sets and assumptions about how their overlap and search costs scale. A continuum of locations would require still more structure to define treasure probability and search effort. A growing hash space and cohorts of similar miners are plausible choices, but they yield an asymptotic mechanism-analysis question; the theorem does not induce a pricing problem or a complexity landscape over mass transfers.
This is a strong case against counting the paper as a ChoCo mirror, rather than a proof that no useful continuum model could be built. A continuum population of miners with a tagged deviator and a carefully scaled sequence of search spaces might support worthwhile work. Its central questions would arise from that new joint scaling model, however, not from a computational result in this paper.
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.