| paper | d4-conf-atal-2015-0225 |
| 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: All asserted limits hold, and \(V_j\leq V_\star\) for every identity. Exact computation is polynomial-time solvable, in \(\mathrm{FP}\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given finitely many types \(T\) with rational masses \(\mu_t>0\) summing to \(1\), rational reference pieces \(r_t\), a focal type \(t^\star\), and finitely many reports \(s_0,\ldots,s_k\), refine the endpoint partition using the population and report reference pieces. For each cell \(I\), let \(\alpha_I=\sum_{t:I\subseteq r_t}\mu_t\). Compute and prove, for every population sequence whose type frequencies converge to \(\mu\), the limits of the aggregate allocation to type \(t\), \(Y_t(I)=\mu_t\lambda(I)/\alpha_I\) when \(I\subseteq r_t\) and \(\alpha_I>0\), and \(0\) otherwise; and the focal user's \(N\)-scaled expected utility from identity \(j\), \(V_j=\lambda(r_{t^\star})^{-1}\sum_{I\subseteq r_{t^\star}\cap r_{s_j}}\lambda(I)/\alpha_I\). Also establish the limiting truthful comparison \(V_j\leq V_\star\) for every reported identity.
A continuum population of piecewise-uniform valuation types with masses \(\mu_t\) shares the cake cell by cell. On a cell wanted by population mass \(\alpha_I\), type \(t\)'s aggregate allocation is proportional to \(\mu_t\), giving its cohort average bundle density \(1/\alpha_I\). Retain a finite tagged user and its reports to measure individual payoffs at the \(N\)-scaled limit.
Finitely many tagged identities have no effect on the limiting cell masses, so this captures their first-order individual payoffs but not their finite-population influence on the allocation; the proponent acknowledges the tagged-user scaling, while the mirror remains meaningful for Theorem 4's per-identity weak false-name condition.
fatal: False
The mirror covers Mechanism 2's ex-post envy-freeness, ex-post proportionality, Pareto efficiency, and weak false-name-proofness in the mass limit. It leaves the strong false-name results, including Theorem 1 and the results for Mechanism 1 in Theorem 3 and Proposition 2, unmirrored.
The strongest case is a narrow, constructive mirror of the paper’s weak false-name result. The paper has no named complexity-class theorem. Its closest constructive anchor is Theorem 4, proved here: Mechanism 2 satisfies ex-post envy-freeness, ex-post proportionality, Pareto efficiency, and weak false-name-proofness. The paper gives the mechanism and proves those guarantees, but does not claim a running-time bound.
A plausible high-multiplicity setting is a large service assigning recurring time slots to users whose preferences come from a small set of patterns. A type is a user’s piecewise-uniform valuation, described by its reference piece \(r_t\); \(\mu_t\) is the fraction of the population with that type. There may be many users but only \(\tau\) distinct types. This is a population mirror, not an appeal to the fact that the cake itself is already continuous.
I would ask a prover to study Mass-Limit Weak-FNP Cake Allocation. An instance gives rational masses \(\mu_t>0\), summing to \(1\), over finitely many types with reference pieces that are finite unions of intervals with rational endpoints. It also gives a focal type \(t^\star\) with \(\mu_{t^\star}>0\), and a finite list of reports \(s_0,\ldots,s_k\) for that user’s real and fake identities. The task is to compute the limiting allocation to each population type and the focal user’s limiting utility from each reported identity. More precisely, take populations of size \(N\) whose type frequencies converge to \(\mu\), add those finitely many tagged identities, and run Mechanism 2. Report the limits of population allocations and of \(N\) times each tagged identity’s expected utility. A solution must give the limits and prove they hold for every such convergent sequence.
Partition the cake at all reference-piece endpoints. For each resulting cell \(I\), let \(\alpha_I=\sum_{t:I\subseteq r_t}\mu_t\) be the mass that wants it. The limiting aggregate allocation to type \(t\) on \(I\) is \(Y_t(I)=\mu_t\lambda(I)/\alpha_I\) when \(t\) wants \(I\), and zero otherwise, where \(\lambda\) is interval length. Thus the population-scaled average bundle \(B_t=Y_t/\mu_t\) has density \(1/\alpha_I\) on cells in \(r_t\). The focal type’s scaled expected utility from identity reporting \(s_j\) is \(V_j=\lambda(r_{t^\star})^{-1}\sum_{I\subseteq r_{t^\star}\cap r_{s_j}}\lambda(I)/\alpha_I\). A complete output consists of these cell allocations and utilities, plus the truthful baseline \(V_\star\) obtained by setting \(s_j=t^\star\).
This is a genuine limit of the paper’s mechanism: on a cell \(I\), Mechanism 2 divides the cell among its \(q\) claimants, where \(q/N\) tends to \(\alpha_I\). The type cohorts’ aggregate allocations therefore converge to \(Y_t\), while the tagged identities retain nonzero scaled utilities. The resulting rule uses all mass of any cell that someone wants; types that want the same cell receive the same scaled average density, and \(\alpha_I\leq1\) gives scaled utility at least \(1\). Also, each reported identity’s utility for the focal user is an integral over a subset of \(r_{t^\star}\), so \(V_j\leq V_\star\). That is the weak false-name condition: no individual identity beats truthful reporting, though the result says nothing about the sum across fake identities.
I expect this mirror to be tractable. The interval cells, masses, and densities can be computed in time polynomial in the number of types \(\tau\), the number of endpoints, the number of tagged reports, and their bit length. That is a complexity claim for the stated mirror, not one made by Theorem 4.
The main weakness is that the limit retains a tagged infinitesimal manipulator and scales utilities by \(N\); a model using only \(\mu\) would erase the individual false-name deviation. The construction also mirrors only Theorem 4’s weak false-name setting. It does not cover the strong false-name impossibility in Theorem 1, or Theorem 3’s bound and Proposition 2’s matching result for strong false-name-proof mechanisms. A natural next question is whether the same limit can support other mechanism guarantees, and what becomes of strong false-name-proofness under this scaling.
Theorem 4 is the right anchor to examine, and its limit calculation is coherent: on a cell \(I\), the number of claimants is asymptotically \(N\alpha_I\), so each gets a piece of length \(|I|/(N\alpha_I)\). The type totals and the scaled payoff of a tagged user therefore have the limits the proponent gives. The cohort example also makes high multiplicity plausible. Those points keep this from being a case against the model’s mathematical legitimacy.
The problem is what the mirror asks us to compute. The paper’s named results establish axiomatic properties of mechanisms; it gives no complexity theorem or computational task whose complexity those results classify. Mechanism 2 itself partitions the cake at reference-piece endpoints, counts claimants on each cell, and divides the cell equally. With type support \(\tau\), the proposed limit replaces those counts with \(\alpha_I\) and evaluates the displayed formulas cell by cell. That is a valid limit theorem and an efficient computation, but it does not open a complexity landscape of the kind the programme is meant to chart. Polynomial time is not the objection; the mirror’s computation is a direct restatement of the explicit rule, rather than a computational question posed by the paper.
The strategic content makes the gap sharper. False-name-proofness concerns an individual whose added identities change the finite claimant counts and whose gains can be compared across those identities. In the proposed limit, finitely many tagged identities have zero effect on \(\alpha_I\). For weak false-name-proofness, each reported identity can claim only cells within the true user’s reference piece, while truthful reporting covers all of those cells; the payoff inequality follows by subset inclusion. This captures a first-order payoff for a singled-out user, but the population limit has removed that user’s effect on the mechanism. If aliases are instead represented by positive mass, the deviation becomes a coalition’s report change, which is a different strategic unit.
The stronger possible mirror of Theorem 3 fares worse as a population limit. If a contested cell has \(q\) claimants, Mechanism 1 allocates only a fraction \(q/2^{q-1}\) of it. With \(q\) growing proportionally to population size, the contested allocation vanishes; only uniquely desired cells remain. One can retain a finite alias count or rescale the vanishing quantity, but then the first choice keeps the discrete manipulation central and the second changes the efficiency measure. Theorem 1’s impossibility likewise relies on the finite identity manipulation; a mass-only profile does not encode that step.
So the proposed mirror survives as a neat asymptotic description of Mechanism 2, but not, in my view, as a worthwhile computational continuization of this paper. A richer continuous mechanism-design problem over mass profiles could be worth studying, but it would need new computational questions and a careful account of individual deviations; this paper’s results do not supply them. I cannot rule out every useful extension, especially given the plausible recurring-resource setting. The negative case is strongest on scope: this paper offers no computational result to mirror, and its explicit mechanism leaves little computational work for the proposed limit.
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.