Answer: A unique strongly optimal admissible rule exists and equals the proposed logarithmic rule, including its unanimous and empty-state values.
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateRule GFNP2 is the strongly optimal neutral group false-name-proof voting rule with 2 alternatives that satisfies voluntary participation. Responsiveness in the limit If c is sufficiently large (at least 1/2), then FNP2 coin- cides with the majority rule. However, there is no (finite) c such that GFNP2 coincides with the majority rule, because for any c there there exists some sufficiently large k such that a coalition of size k would like to group false-name- manipulate the majority rule in (for example) tied states.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For rational \(c>0\), let a society have preference types \(A,B\) with masses \(\mu_A+\mu_B=1\). Find a neutral lottery rule \(P_A(a,b)\) that is pointwise maximal for every state \(a\ge b\), subject to the mass-scaled group false-name-proof constraints: for every \(A\)-preferring coalition of mass \(\kappa>0\), background ballot masses \(z_A,z_B\ge0\), and added false-ballot masses \(\delta_A,\delta_B\ge0\), require \(P_A(z_A+\kappa,z_B)\ge P_A(z_A+\kappa+\delta_A,z_B+\delta_B)-c(\delta_A+\delta_B)/\kappa\); impose the symmetric constraint for \(B\), along with neutrality and the corresponding participation and strategy-proofness conditions. Is the pointwise-optimal rule \(P_A(a,b)=\min\{1,\tfrac12+c\ln(a/b)\}\) for \(a\ge b>0\), with \(P_A(a,0)=1\) for \(a>0\) and \(P_A(0,0)=1/2\)?
There are \(m=2\) alternatives, \(A,B\), and two strict preference types; utility per unit mass is \(1\) for the preferred outcome and \(0\) otherwise. A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with \(\mu_A+\mu_B=1\). Here \(\tau\) is the support size, not the number of possible types; state any running times in \(m,\tau,L\) and other relevant parameters, where \(L\) is the input bit length.
For rational \(c>0\), seek an anonymous lottery rule \(P_A:\mathbb R_{\ge0}^2\to[0,1]\), with \(P_B=1-P_A\) and neutrality \(P_A(a,b)=1-P_A(b,a)\). States are ballot masses, need not sum to one, and all constraints below apply universally on this domain; no continuity is assumed.
Genuine ballot mass is free, abstention costs nothing, and added false-ballot mass \(\delta_A+\delta_B\) costs \(c(\delta_A+\delta_B)\). Coalitions of one preference type can commit to transfers and share this cost equally per unit mass.
Participation and strategy-proofness require, for all \(x,y\ge0\) and \(h>0\), \(P_A(x+h,y)\ge P_A(x,y)\) and \(P_A(x+h,y)\ge P_A(x,y+h)\), with the symmetric requirements for \(B\).
Group false-name-proofness requires, for every \(\kappa>0\) and \(z_A,z_B,\delta_A,\delta_B\ge0\), \(P_A(z_A+\kappa,z_B)\ge P_A(z_A+\kappa+\delta_A,z_B+\delta_B)-c(\delta_A+\delta_B)/\kappa\), and symmetrically for \(B\).
An admissible rule is strongly optimal if, for every admissible \(Q\), \(P_A(a,b)\ge Q_A(a,b)\) at every \(a\ge b\ge0\).
Does a strongly optimal admissible rule exist, and is it given by \(P_A(a,b)=\min\{1,\tfrac12+c\ln(a/b)\}\) for \(a\ge b>0\), \(P_A(a,0)=1\) for \(a>0\), and \(P_A(0,0)=\tfrac12\), extended by neutrality, or does this characterization fail?
For integer ballot counts, the strongly optimal neutral group false-name-proof rule satisfying participation has majority probability \(\min\{1,\tfrac12+c\sum_{k=b}^{a-1}1/k\}\) for \(a\ge b>0\), with unanimous and empty-state values as above. [Wagman–Conitzer, 2008](https://www.cs.cmu.edu/~conitzer/costly_votingAAAI08.pdf)
The later treatment studies individual false-name-proofness with general costs and leaves group extensions as future work; no result settling this exact mass model was located. [Wagman–Conitzer, 2014](https://www.cs.cmu.edu/~conitzer/costlyIJGT13.pdf)
1. Result
The characterization holds: there is a unique strongly optimal admissible rule, and it is the proposed logarithmic rule. No continuity assumption is needed.
Fix \(c>0\). Define the clipping function
\(C(t)=\max\{0,\min\{1,t\}\}\), and set
\(P_A(a,b)=C\!\left(\tfrac12+c\ln(a/b)\right)\) for \(a,b>0\),
with \(P_A(a,0)=1\) for \(a>0\), \(P_A(0,b)=0\) for \(b>0\), and \(P_A(0,0)=\tfrac12\). Set \(P_B=1-P_A\).
For \(a\ge b>0\), this is exactly
\(P_A(a,b)=\min\{1,\tfrac12+c\ln(a/b)\}\).
2. A universal bound without continuity
Let \(Q\) be any admissible rule. For every \(u>0\), \(b\ge0\), and \(d\ge0\), group false-name-proofness, applied with
\(\kappa=u\), \(z_A=0\), \(z_B=b\), \(\delta_A=d\), and \(\delta_B=0\), gives
\(Q_A(u+d,b)-Q_A(u,b)\le cd/u.\)
Participation gives the corresponding lower bound. Thus
\(0\le Q_A(u+d,b)-Q_A(u,b)\le cd/u.\)
We claim that, for every \(v>u>0\),
\(Q_A(v,b)-Q_A(u,b)\le c\ln(v/u).\)
To prove this, fix a positive integer \(n\), put \(\Delta=(v-u)/n\), and define \(u_i=u+i\Delta\). Each \(u_i\) is positive, so the preceding inequality applies to every consecutive pair. Summing gives
\(Q_A(v,b)-Q_A(u,b) =\sum_{i=0}^{n-1}\bigl(Q_A(u_{i+1},b)-Q_A(u_i,b)\bigr) \le c\sum_{i=0}^{n-1}\Delta/u_i.\)
The sum on the right is a left Riemann sum for the continuous function \(t\mapsto1/t\) on \([u,v]\). Consequently, its limit is
\(\int_u^v dt/t=\ln(v/u)\). Since the displayed bound holds for every \(n\), taking the limit proves the claim. No limit or regularity property of \(Q_A\) was used.
Neutrality forces \(Q_A(b,b)=\tfrac12\). Therefore, for \(a\ge b>0\),
\(Q_A(a,b)\le\tfrac12+c\ln(a/b).\)
Combining this with \(Q_A(a,b)\le1\) yields the universal upper bound
\(Q_A(a,b)\le\min\{1,\tfrac12+c\ln(a/b)\}.\)
3. Admissibility of the proposed rule
The clipping function satisfies three elementary properties:
The second property follows by considering intervals lying below zero, inside \([0,1]\), or above one, and splitting any interval that crosses an endpoint. On each piece, the change in \(C\) is either zero or the length of that piece. The third property follows directly from the same three regions.
Neutrality. For positive coordinates,
\(\tfrac12+c\ln(b/a)=1-(\tfrac12+c\ln(a/b))\). The third clipping property therefore gives
\(P_A(a,b)=1-P_A(b,a)\). The specified axis and empty-state values satisfy this identity as well.
Participation. For fixed \(b>0\), the positive-coordinate formula is nondecreasing in \(a\), because the logarithm and \(C\) are nondecreasing. Its value at \(a=0\) is zero, so monotonicity also holds there. For \(b=0\), the value is \(\tfrac12\) at \(a=0\) and one for every \(a>0\), again nondecreasing.
Neutrality then implies that \(P_A\) is nonincreasing in its second coordinate: if \(b'\ge b\), then
\(P_A(a,b')=1-P_A(b',a)\le1-P_A(b,a)=P_A(a,b).\)
These two coordinate monotonicities establish participation for both preference types.
Strategy-proofness. For every \(x,y\ge0\) and \(h>0\), coordinate monotonicity gives
\(P_A(x+h,y)\ge P_A(x,y)\ge P_A(x,y+h).\)
This is precisely the required inequality for type \(A\); exchanging the alternatives proves the requirement for type \(B\).
Group false-name-proofness. Fix arbitrary \(\kappa>0\) and nonnegative \(z_A,z_B,\delta_A,\delta_B\). Write \(a=z_A+\kappa>0\) and \(b=z_B\). Since additional mass for \(B\) cannot increase \(P_A\),
\(P_A(a+\delta_A,b+\delta_B)-P_A(a,b) \le P_A(a+\delta_A,b)-P_A(a,b).\)
If \(b=0\), the right-hand side is zero because both probabilities equal one.
If \(b>0\), the second clipping property gives
\(P_A(a+\delta_A,b)-P_A(a,b) \le c\ln\!\left(1+\delta_A/a\right) \le c\delta_A/a.\)
Here the last inequality follows from
\(\ln(1+t)=\int_0^t(1+s)^{-1}\,ds\le t\) for \(t\ge0\).
Finally, \(a\ge\kappa\), so
\(c\delta_A/a\le c\delta_A/\kappa \le c(\delta_A+\delta_B)/\kappa.\)
Combining these inequalities proves exactly the stated constraint for type \(A\), including all boundary cases. Because \(P_B(a,b)=P_A(b,a)\), exchanging coordinates and alternatives proves the symmetric constraint for type \(B\).
Thus \(P\) is admissible.
4. Strong optimality and uniqueness
For every admissible \(Q\) and every \(a\ge b>0\), the bound proved in Section 2 gives
\(Q_A(a,b)\le\min\{1,\tfrac12+c\ln(a/b)\}=P_A(a,b).\)
For \(a>0=b\), the inequality follows from \(Q_A(a,0)\le1=P_A(a,0)\). At the empty state, neutrality forces
\(Q_A(0,0)=\tfrac12=P_A(0,0)\). Hence \(P\) is strongly optimal on the entire required domain.
If another admissible rule \(R\) were strongly optimal, strong optimality of \(P\) and \(R\) would give equality at every \(a\ge b\). Neutrality would then give equality at every \(a<b\). Therefore the strongly optimal rule is unique.
5. Scope
The discrete harmonic characterization appears in [Wagman–Conitzer (2008), Theorem 3](https://www.cs.cmu.edu/~conitzer/costly_votingAAAI08.pdf). The proof above establishes the mass characterization directly from the stated constraints.
The normalized society has \(m=2\) and support size \(\tau\in\{1,2\}\). Its outcome is obtained by evaluating this rule at \((\mu_A,\mu_B)\), treating an absent type as having zero mass. Normalization is not used in the proof: admissibility and optimality hold universally on \(\mathbb R_{\ge0}^2\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated characterization correctly. The proposed rule is admissible and uniquely strongly optimal. No mathematical gaps or false steps were found.
The group false-name-proofness substitution is valid: \(\kappa=u>0\), \(z_A=0\), \(z_B=b\ge0\), \(\delta_A=d\ge0\), and \(\delta_B=0\) satisfy every domain restriction. It gives
\[
Q_A(u+d,b)-Q_A(u,b)\le cd/u.
\]
Participation supplies the lower bound, including \(d=0\), where the difference is zero.
For \(v>u>0\), all partition points \(u_i\) remain positive. The telescoping equality and the application of the increment bound to each consecutive pair are correct.
The left Riemann sums converge because \(t\mapsto1/t\) is continuous on the compact interval \([u,v]\), which excludes zero. The quantity on the left is independent of the partition size. Thus taking the limit of the numerical upper bounds requires no continuity or other regularity of \(Q_A\).
Neutrality gives \(Q_A(b,b)=1/2\). Applying the bound with \(u=b\) and \(v=a\) proves the claimed upper bound when \(a>b>0\). When \(a=b>0\), neutrality supplies it directly. Combining with the probability bound \(Q_A\le1\) is valid.
The clipping function maps every real input into \([0,1]\), so the positive-coordinate formula defines a lottery probability. Its monotonicity, increment bound, and identity \(C(1-t)=1-C(t)\) are correct; the supplied piecewise explanations suffice.
For positive coordinates, swapping them replaces the clipping argument by its complement. The axis values and the empty-state value also satisfy neutrality. The rule is anonymous because it depends only on the two ballot masses.
The first-coordinate monotonicity argument covers all cases:
Neutrality then correctly yields monotonicity in the opposite direction for the second coordinate, including its boundary cases. These properties establish participation for both alternatives.
The chain
\[
P_A(x+h,y)\ge P_A(x,y)\ge P_A(x,y+h)
\]
is valid for every permitted \(x,y,h\). Exchanging alternatives establishes the symmetric strategy-proofness condition.
For an arbitrary permitted coalition, \(a=z_A+\kappa\) is strictly positive and satisfies \(a\ge\kappa\). Second-coordinate monotonicity correctly bounds the gain from adding both kinds of ballots by the gain from adding only \(A\)-ballots.
If \(b=0\), both probabilities in that latter difference equal one, so its value is zero.
If \(b>0\), both logarithmic arguments are defined, and their difference is
\[
c\ln(1+\delta_A/a).
\]
The clipping increment bound therefore applies. The inequality \(\ln(1+t)\le t\) is correctly justified for every \(t\ge0\), including zero. Finally, \(a\ge\kappa>0\) and \(c>0\) justify both subsequent cost bounds.
Consequently, the argument proves the full universally quantified constraint, including zero added mass and additions of only opposing ballots. The identity \(P_B(a,b)=P_A(b,a)\) correctly transfers this verification to type \(B\).
The universal upper bound establishes domination of every admissible rule throughout the positive majority region. On the nonempty unanimous axis, domination follows from the probability upper bound. At the empty state, neutrality forces equality.
If another admissible rule is strongly optimal, applying each rule’s defining domination property to the other gives equality on the entire majority region. Neutrality then gives equality on the remaining region. The uniqueness conclusion follows.
The proof uses the full nonnegative mass domain and does not rely on normalization, rational ballot masses, or continuity. The discussion of normalized societies correctly identifies the support size as \(\tau\in\{1,2\}\).
The discrete attribution is accurate: [Wagman–Conitzer (2008), Definition 10 and Theorem 3](https://www.cs.cmu.edu/~conitzer/costly_votingAAAI08.pdf) give the stated harmonic rule and its strong optimality under neutrality, group false-name-proofness, and voluntary participation. That theorem is background rather than a premise of the continuous proof.
No running time or computational representation claim is made. The task’s requirement concerning how to state running times is therefore not violated, but the output does not establish a complexity classification.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.