| paper | d4-conf-atal-2011-0005 |
| 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: \(F\) is false-name-proof on the stated rational-mass domain, and \(R(M)=M/2\) for every rational \(M\ge 2\); the supremum is attained. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
For a finite-support rational mass measure \(\rho\) on \(\mathbb R\), with total mass \(M\ge2\) and every positive type mass at least \(1\), apply the left-right-middle lottery to the support endpoints and their midpoint with probabilities \(1/4,1/4,1/2\). Against deviations in which one resident replaces their truthful unit report by any finite set of unit identity reports, is this mechanism false-name-proof, and is its exact worst-case ratio of expected social cost to the optimum weighted social cost \(M/2\)?
Represent residents by a finite-support distribution of ideal locations with real-valued masses and evaluate social cost as \(\int |t-y|\,d\rho(t)\). The mechanism chooses a facility location by a lottery over the minimum and maximum support points and their midpoint; a resident's false-name deviation adds unit identity reports to the background mass measure.
The mirror covers Theorem 6's left-right-middle lottery, false-name-proofness, and social-cost guarantee. It leaves Theorem 7's universal lower bound, Theorem 2's deterministic characterization, and the paper's maximum-cost and tree results aside.
The strongest case is the paper’s real-line, social-cost results. The paper has no named P/NP, FPT, or parameterized-complexity theorem; its computational anchors are a mechanism characterization and approximation guarantees. Their mirror is still concrete: a large population choosing where to locate a public service, with distance as each resident’s cost and no payments.
Let a resident’s type be their ideal location \(x\in\mathbb R\). A society is a finite-support distribution \(\mu\) over locations, with \(\tau\) distinct types and rational masses. Write \(M\) for its population-equivalent size and \(\epsilon=1/M\) for one resident’s share. The facility remains a point \(y\); the continuized object is the population. A mechanism receives the reported mass measure \(\rho=M\mu\) and returns a location or a lottery over locations. Its per-capita social cost at \(y\) is \(M^{-1}\int |t-y|\,d\rho(t)\); the optimum is attained at a median.
False-name-proofness needs one extra feature: retain a person-sized strategic unit even as their share \(\epsilon\) gets small. If \(\lambda\) is the other population’s mass and the person’s true location is \(x\), honest reporting gives \(\lambda+\delta_x\). A false-name deviation gives \(\lambda+\nu\), where \(\nu\) is a report measure of mass at least one. The condition is
\[
\mathbb E|x-F(\lambda+\delta_x)|
\le
\mathbb E|x-F(\lambda+\nu)|.
\]
The literal paper model is the subcase \(\nu=\sum_{j=1}^k\delta_{z_j}\); allowing fractional \(\nu\) closes that action space under continuization. This fits a setting such as an unauthenticated online consultation about a service location: many residents share a modest number of ideal locations, while one participant can submit extra identities.
The lead anchor is Theorem 7, proved in this paper, with an auxiliary inequality from Procaccia and Tennenholtz [8]. It says that every randomized false-name-proof mechanism has social-cost approximation ratio \(\Omega(n)\). The proof gives a lower bound of \((n-1)/2\): compare the outcome distribution on two reports at \(0\) and \(1\) with a profile containing one report at \(0\) and \(n-1\) at \(1\), which an agent can reach with false names.
Its continuous question is: for total mass \(M\), what is the minimum worst-case expected per-capita social-cost ratio over anonymous randomized false-name-proof mechanism families, on societies whose positive type masses are at least one? Integer-mass profiles embed directly. In the fractional false-mass closure above, the same two-point argument predicts a lower bound \((M-1)/2\), while the next anchor gives an \(M/2\) upper bound. So the expected answer is \(\Theta(M)=\Theta(1/\epsilon)\): fractional masses do not remove the growing approximation barrier. This is the strongest anchor because it survives randomization.
Theorem 6, also proved here, supplies that upper-side question. The left-right-middle mechanism, originally proposed by Procaccia and Tennenholtz, chooses the leftmost report with probability \(1/4\), the rightmost with probability \(1/4\), and their midpoint with probability \(1/2\). The paper proves it is false-name-proof and has social-cost approximation ratio \(n/2\), attained when one extreme report is separated from the other \(n-1\).
The continuous problem is to run the same lottery on the support endpoints of \(\rho\) and determine its guarantee when \(M\) is real and each occupied type has mass at least one. The expected result is false-name-proofness and an exact ratio \(M/2\): a society with mass \(1\) at one endpoint and \(M-1\) at the other attains it. This rule is computable from the \(\tau\) support points, and the bound pairs with Theorem 7 to pin down the leading asymptotic factor. It is a tractable mass-weighted approximation question.
A separate structural question mirrors Theorem 2, proved here using Lemmas 1 and 2. It characterizes anonymous, Pareto-efficient, deterministic false-name-proof rules on the real line: exactly those with a fixed \(\alpha\) that return the median of the \(n\) reports together with \(n-1\) copies of \(\alpha\). In the continuous version, characterize all anonymous Pareto-efficient selectors \(F\) on finite real-mass measures that satisfy the mass-based false-name condition above. The natural candidate is a fixed-\(\alpha\) weighted \(M\)-quantile of \(\rho+(M-1)\delta_\alpha\), with tie selection part of the question. At integer masses it recovers the paper’s rule. I expect a structural characterization that can be evaluated from the sorted support, rather than inherited hardness.
I would keep the scope to the paper’s real-line, false-name-proof results and social-cost objective; the tree characterization and maximum-cost results need not be stretched into this case. The main soft spot is also the necessary co-modification: in a purely atomless model, one resident’s report has zero mass, so false-name-proofness loses its intended meaning. Keeping a one-person strategic unit, then studying the limit as \(\epsilon\to0\), preserves the incentive question while letting type masses vary continuously. The paper’s approximation bounds already depend on population size, so that resolution parameter belongs in the mirror.
The proponent’s best anchors all concern the real-line facility-location model, but none is a named complexity result. Theorem 2 is an axiomatic characterization; Theorems 6 and 7 are distortion bounds for mechanisms. The paper gives no worst-case complexity result for an input problem, and its mechanisms can be evaluated directly from the reports. A continuous extension could be worthwhile mechanism-design research, but it would continue the paper’s axiomatic and approximation analysis rather than the computational programme’s study of problem complexity and algorithms.
Theorem 7 is the strongest candidate, and its best mirror preserves a one-person strategic unit inside a large society. Set total mass to \(M\), keep one unit at one endpoint, and put the remaining \(M-1\) mass at the other. This retains the paper’s false-name argument and gives the proposed \((M-1)/2\) lower bound. But the bound depends on preserving an atomic manipulator while the population grows. In the normalized distribution, that person’s share is \(1/M\); as \(M\) grows, the society converges to one concentrated at the other endpoint, while the optimal per-capita cost tends to zero. The manipulator’s influence does not vanish along with their share. In a genuinely atomless limit, a single person changes no mass and false-name-proofness loses its force. Keeping the unit atom instead gives a coherent hybrid model, but its parameter \(M\) tracks the size of the strategic unit relative to the population; it does not yield a nondegenerate continuum limit. Allowing fractional false-name mass changes the strategic action being modeled, while restricting false names to whole identities preserves the atomic feature. Either way, the result remains an incentive and distortion bound, not a complexity question.
Theorem 6 has the same underlying issue. Its best continuous version applies the endpoint lottery to a mass distribution and obtains the \(M/2\) ratio on the one-unit-versus-\(M-1\) profile. That is a precise weighted distortion exercise, but the bound is again driven by a vanishing minority with persistent strategic influence. The rule also gives an endpoint fixed probability based on its presence in the support, however little mass it carries. Smoothing or removing that influence changes the mechanism whose false-name-proofness is being studied. The mirror therefore either retains the atomic game behind the discrete theorem or turns into a mass-based performance question without the paper’s incentive content. Neither route adds an algorithmic problem: the lottery uses the support endpoints, and evaluating its outcome is immediate.
Theorem 2 admits a better mirror than a literal extension: define a weighted median using the population measure and mass at a fixed \(\alpha\), then characterize the selectors satisfying a stated mass-based false-name condition. That could be a legitimate new theorem. But it is still a characterization of incentive-compatible rules, not a computational-complexity result. With finite support, a proposed weighted-quantile rule can be evaluated by sorting locations and accumulating mass. And in the atomless limit, the negligible individual’s report no longer constrains the selector, so the limiting characterization does not retain the paper’s false-name condition.
So I would not claim that no continuous model could ever be worthwhile. A large cohort of residents sharing location preferences, alongside an individual who can create extra identifiers, is plausible, and the resulting hybrid model could interest mechanism-design researchers. The negative case is stronger and narrower: none of these anchors supplies the kind of computational question ChoCo is meant to chart, and preserving the paper’s central false-name incentive requires keeping the individual atom that a pure continuous-population limit washes away.
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.