Differentially Private Condorcet Voting (aaai23-25714)

Given candidates \(C\), ranking types \(T=L(C)\), rational masses \(\mu\) over \(T\), mechanism \(\mathit{Rand}\in\{\mathit{LAP},\mathit{EXP},\mathit{RR}\}\), normalized noise parameter \(\beta\), and precision \(r\), compute a candidate whose output distribution is within total variation \(2^{-r}\) of the distribution \(p_\mu\) defined by the paper’s pairwise noisy Condorcet products.

Let \(C\) contain \(m\ge 2\) candidates. A society is given by its support: a list of \(\tau\) strict ranking types \(t\in\mathcal L(C)\) with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings.
Input also includes \(\mathrm{Rand}\in\{\mathrm{LAP},\mathrm{EXP},\mathrm{RR}\}\), a positive binary rational \(\beta\), and a positive integer precision \(r\) supplied in unary. Let \(L\) be the total encoding length of the rankings, masses, and \(\beta\).
Define \(d_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t-\sum_{t:b\succ_t a}\mu_t\).
Set \(g_{\mathrm{LAP},\beta}(x)=\tfrac12e^{\beta x}\) for \(x\le0\), and \(g_{\mathrm{LAP},\beta}(x)=1-\tfrac12e^{-\beta x}\) for \(x>0\); set \(g_{\mathrm{EXP},\beta}(x)=(1+e^{-\beta x/2})^{-1}\).
Set \(g_{\mathrm{RR},\beta}(x)=e^\beta/(1+e^\beta)\) for \(x>0\), \(g_{\mathrm{RR},\beta}(0)=\tfrac12\), and \(g_{\mathrm{RR},\beta}(x)=1/(1+e^\beta)\) for \(x<0\).
For the selected mechanism, define \(W_\mu(a)=\prod_{b\in C\setminus\{a\}}g_{\mathrm{Rand},\beta}(d_\mu(a,b))\) and \(p_\mu(a)=W_\mu(a)/\sum_{c\in C}W_\mu(c)\).
The task is to output one random candidate with law \(q\) satisfying \(\tfrac12\sum_{a\in C}|q(a)-p_\mu(a)|\le2^{-r}\), using independent fair random bits in the Turing bit model.
Is this sampling problem solvable in randomized polynomial time in \(m,\tau,L,r\), or is it NP-hard?
For finite profiles, the discrete sampling result gives normalized pairwise products and claims \(O(m^2)\) sampling time once margins are available, without a bit-precision analysis ([source](https://arxiv.org/pdf/2206.13081)).
No result settling this explicitly supported rational-mass sampling problem in the stated bit model was located.

Result

The sampling problem is solvable in randomized polynomial time in \(m,\tau,L,r\) for all three mechanisms. In fact, the algorithm below has polynomial worst-case running time and uses a fixed polynomial number of independent fair bits.

The cited paper states an \(O(m^2)\) sampling bound after Lemma 1. The argument below supplies a bit-complexity analysis for the definitions in this question. [Li et al., *Differentially Private Condorcet Voting*](https://arxiv.org/pdf/2206.13081)

1. Exact computation of the margins

Write \(n=m-1\), \(\varepsilon=2^{-r}\), and \(d_{ab}=d_\mu(a,b)\).

All margins can be computed exactly in polynomial time. To see the bit-length bound explicitly, write each mass as \(\mu_t=u_t/v_t\), and use the common denominator \(D=\prod_t v_t\). Its binary length is at most the sum of the binary lengths of the input denominators, hence \(O(L)\).

Each margin is therefore a signed sum of integers divided by \(D\). The numerator lengths are polynomial in \(L+\log\tau\). Reading the rankings and accumulating their contributions takes \(O(\tau m^2)\) rational arithmetic operations, all on polynomial-length integers.

In particular, margin signs and ties are decidable exactly.

2. Factorization and rescaling

We factor each weight as

\(W_\mu(a)=e^{-E_a}H_a,\qquad 2^{-n}\le H_a\le1,\)

where \(E_a\) is a nonnegative rational computable exactly.

LAP

Define

\(E_a=\beta\sum_{b\ne a}\max\{-d_{ab},0\}.\)

For each opponent, set \(h_{ab}=1/2\) when \(d_{ab}\le0\), and set

\(h_{ab}=1-\tfrac12e^{-\beta d_{ab}}\)

when \(d_{ab}>0\). Let \(H_a=\prod_{b\ne a}h_{ab}\).

For a negative margin, the corresponding factor in \(W_\mu(a)\) is \(\tfrac12e^{-\beta|d_{ab}|}\). For a zero margin it is \(1/2\); for a positive margin it is \(h_{ab}\). Multiplication proves the claimed factorization.

Every \(h_{ab}\) belongs to \([1/2,1]\).

EXP

Define

\(E_a=\frac{\beta}{2}\sum_{b\ne a}\max\{-d_{ab},0\},\qquad h_{ab}=\frac{1}{1+e^{-\beta|d_{ab}|/2}},\qquad H_a=\prod_{b\ne a}h_{ab}.\)

For a negative margin,

\(g_{\mathrm{EXP},\beta}(d_{ab})=\frac{e^{-\beta|d_{ab}|/2}}{1+e^{-\beta|d_{ab}|/2}}.\)

For a nonnegative margin, \(g_{\mathrm{EXP},\beta}(d_{ab})=h_{ab}\). These identities prove the factorization, including ties. Again, \(h_{ab}\in[1/2,1]\).

RR

Let \(\ell_a=|\{b\ne a:d_{ab}<0\}|\), and define \(E_a=\beta\ell_a\).

Set \(h_{ab}=1/2\) for a tie, and otherwise set

\(h_{ab}=\frac{1}{1+e^{-\beta}}.\)

Let \(H_a=\prod_{b\ne a}h_{ab}\). A negative margin contributes \(e^{-\beta}h_{ab}\), a positive margin contributes \(h_{ab}\), and a tie contributes \(1/2\). Thus the factorization holds, with \(h_{ab}\in[1/2,1]\).

A lower bound on the rescaled normalizer

Compute \(E_*=\min_a E_a\) exactly, and define

\(V_a=e^{-(E_a-E_*)}H_a,\qquad S=\sum_a V_a.\)

The rational quantities \(E_a\), \(E_*\), and their differences have polynomial encoding length: they are formed by polynomially many exact rational operations on the margins and \(\beta\).

The common rescaling cancels in normalization, so

\(p_\mu(a)=V_a/S.\)

Every \(V_a\) lies in \((0,1]\). For a candidate attaining \(E_*\), its exponential factor is \(1\), and consequently

\(S\ge2^{-n}.\)

This bound depends on the number of candidates, but not on the numerical magnitude of \(\beta\). It is the key to the precision analysis.

3. Approximating a decaying exponential

Lemma. Given a nonnegative binary rational \(x\) of encoding length \(B\), and an integer \(k\ge1\), one can compute a rational \(z\in[0,1]\) satisfying

\(|z-e^{-x}|\le2^{-k}\)

in deterministic time polynomial in \(B+k\). The output has \(O(k)\) bits.

Proof. If \(x\ge k+2\), output \(0\). Since \(e>2\),

\(e^{-x}\le2^{-x}\le2^{-(k+2)}.\)

Otherwise, let \(N=6(k+2)\), and compute exactly the Taylor polynomial

\(T=\sum_{j=0}^{N-1}\frac{(-x)^j}{j!}.\)

Taylor’s theorem applies to \(e^{-x}\) on the interval \([0,x]\). The absolute value of its \(N\)-th derivative is at most \(1\) there, so

\(|T-e^{-x}|\le x^N/N!.\)

For completeness,

\(\log(N!)=\sum_{j=1}^N\log j\ge\int_1^N\log t\,dt=N\log N-N+1,\)

which implies \(N!\ge(N/e)^N\). Using \(e<3\), \(x<k+2\), and \(N=6(k+2)\), we obtain

\(\frac{x^N}{N!}\le\left(\frac{ex}{N}\right)^N<2^{-N}\le2^{-(k+2)}.\)

Round \(T\) downward to a multiple of \(2^{-(k+2)}\), then clamp the result to \([0,1]\). Rounding adds less than \(2^{-(k+2)}\) error. Clamping cannot increase the distance to \(e^{-x}\in[0,1]\). The final error is therefore at most \(2^{-k}\).

To check bit complexity, write \(x=p/q\). The Taylor sum can be represented using the common denominator \(q^{N-1}(N-1)!\); its numerator and denominator have \(O(N(B+\log N))\) bits. Exact evaluation and rounding therefore take polynomial time. The clamped output has denominator \(2^{k+2}\) and \(O(k)\) bits. \(\square\)

Thus a huge exponent is handled by an exact comparison and truncation, rather than by computation proportional to its value.

4. Approximating the normalized weights

Choose

\(k=r+n+2\lceil\log_2m\rceil+2.\)

For every exponential appearing in \(e^{-(E_a-E_*)}\) or in \(H_a\), apply the lemma with accuracy \(2^{-k}\). All arguments are nonnegative rationals of polynomial encoding length.

Construct approximate factors from these rational exponential approximations. Constant factors are exact. For LAP, the map \(u\mapsto1-u/2\) changes absolute error by at most a factor \(1/2\). For EXP and RR, for \(u,v\in[0,1]\),

\(\left|\frac1{1+u}-\frac1{1+v}\right|=\frac{|u-v|}{(1+u)(1+v)}\le|u-v|.\)

Hence every approximate factor remains in \([0,1]\) and differs from its exact factor by at most \(2^{-k}\).

Compute each approximate product \(\widetilde V_a\) exactly as a rational. There are \(m\) factors: one rescaling exponential and \(n\) factors from \(H_a\).

For any \(u_i,v_i\in[0,1]\), a telescoping expansion gives

\(\left|\prod_{i=1}^{m}u_i-\prod_{i=1}^{m}v_i\right|\le\sum_{i=1}^{m}|u_i-v_i|.\)

Indeed, each summand in the expansion consists of one difference \(u_i-v_i\) multiplied by factors of absolute value at most \(1\). Consequently,

\(|\widetilde V_a-V_a|\le m2^{-k}.\)

Let \(\Delta=\sum_a|\widetilde V_a-V_a|\) and \(\widetilde S=\sum_a\widetilde V_a\). The chosen precision gives

\(\Delta\le m^2 2^{-k}\le\varepsilon\,2^{-n}/4.\)

Because \(S\ge2^{-n}\), we have \(\Delta\le\varepsilon S/4<S\), so \(\widetilde S>0\). Define the exact rational distribution

\(\widetilde p(a)=\widetilde V_a/\widetilde S.\)

Its normalization error satisfies

\(\sum_a\left|\frac{V_a}{S}-\frac{\widetilde V_a}{\widetilde S}\right| \le\frac{\Delta}{S}+\frac{|\widetilde S-S|}{S} \le\frac{2\Delta}{S}.\)

The first inequality inserts \(\widetilde V_a/S\) between the two terms; summing the resulting normalization contribution gives exactly \(|\widetilde S-S|/S\). Thus

\(\operatorname{TV}(p_\mu,\widetilde p)\le\Delta/S\le\varepsilon/4.\)

All these rational computations have polynomial bit complexity. Each approximate factor has \(O(k)\) bits, a product has \(O(mk)\) bits, and summing and normalizing polynomially many such rationals preserves a polynomial encoding-length bound.

5. Sampling with a fixed number of fair bits

Enumerate the candidates as \(a_1,\ldots,a_m\). Define cumulative probabilities

\(F_0=0,\qquad F_i=\sum_{j=1}^i\widetilde p(a_j).\)

Choose

\(K=r+\lceil\log_2m\rceil+2,\qquad M=2^K,\qquad B_i=\lfloor MF_i\rfloor.\)

These integers are computable exactly in polynomial time. They satisfy

\(0=B_0\le B_1\le\cdots\le B_m=M.\)

Use exactly \(K\) independent fair bits to generate a uniform integer \(U\in\{0,\ldots,M-1\}\). Output the unique candidate \(a_i\) whose interval satisfies

\(B_{i-1}\le U<B_i.\)

Empty intervals are skipped. The nonempty intervals partition the possible values of \(U\), so this always outputs one candidate.

Its law is

\(q(a_i)=\frac{B_i-B_{i-1}}{M}.\)

Since \(|B_i/M-F_i|<1/M\), the triangle inequality gives

\(|q(a_i)-\widetilde p(a_i)|\le2/M.\)

Therefore,

\(\operatorname{TV}(q,\widetilde p)\le m/M\le\varepsilon/4.\)

Combining the two approximation bounds yields

\(\operatorname{TV}(q,p_\mu)\le\operatorname{TV}(q,\widetilde p)+\operatorname{TV}(\widetilde p,p_\mu)\le\varepsilon/2\le2^{-r}.\)

6. Complexity conclusion

Margin computation, exact rescaling, exponential approximation, rational normalization, and cumulative rounding all take polynomial time in \(m,\tau,L,r\). The random stage uses exactly \(K=O(r+\log m)\) fair bits and also has polynomial worst-case running time.

This completely establishes the requested randomized polynomial-time sampling algorithm for LAP, EXP, and RR, including exact ties and binary-encoded parameters of arbitrarily large numerical magnitude.

⟨structured verdict parsed — rendered above⟩

The prover’s output establishes the requested randomized polynomial-time sampling algorithm for all three mechanisms. The factorization, exponential approximation, normalization bounds, and fixed-bit sampling construction are correct. I found no major or minor gaps requiring repair.

• Scope and input model

The algorithm addresses the explicitly listed support of size \( \tau \); it does not enumerate all possible rankings or expand rational masses into individual voters. Its arithmetic uses the binary encodings of the masses and \( \beta \), and its precision requirements are polynomial in the numerical value of \( r \), as permitted by the unary encoding.

The conclusion establishes polynomial-time solvability of the sampling task. It does not require a separate argument excluding hardness under complexity-class collapses.

• Exact margins and their encoding lengths

The denominator \( D=\prod_t v_t \) has binary length at most the sum of the denominator lengths, hence \( O(L) \). Each mass has an integer numerator over \( D \), so every margin can be accumulated exactly using integers of polynomial length.

There are \( \tau \) rankings and at most \( m(m-1) \) ordered candidate pairs. The stated \( O(\tau m^2) \) arithmetic-operation bound is valid. Reading each explicit ranking and obtaining its pairwise comparisons also takes polynomial time.

Consequently, deciding whether each margin is negative, zero, or positive is exact. This is especially necessary for RR, whose definition changes discontinuously at zero.

• The three factorizations

For LAP, a negative margin contributes \( \tfrac12 e^{-\beta|d_{ab}|} \), a zero margin contributes \( \tfrac12 \), and a positive margin contributes \( 1-\tfrac12 e^{-\beta d_{ab}} \). These are exactly the factors used in \( e^{-E_a}H_a \). Every factor of \( H_a \) belongs to \( [1/2,1] \).

For EXP, multiplying the numerator and denominator of the negative-margin expression by \( e^{-\beta|d_{ab}|/2} \) gives the displayed identity. The nonnegative-margin expression agrees with \( h_{ab} \), including \( h_{ab}=1/2 \) at zero. Thus both the exponent \( E_a \) and the product \( H_a \) are correct.

For RR, the non-tie factor \( h_{ab}=1/(1+e^{-\beta}) \) equals \( e^\beta/(1+e^\beta) \). Multiplication by \( e^{-\beta} \) gives \( 1/(1+e^\beta) \), as required for a negative margin. Ties contribute exactly \( 1/2 \).

Therefore, for every mechanism and candidate, the asserted identity \( W_\mu(a)=e^{-E_a}H_a \) and bounds \( 2^{-n}\le H_a\le1 \) hold.

• Rescaling and the lower bound on the normalizer

Each \( E_a \) is a nonnegative rational obtained from the exact margins and \( \beta \). The previously established common-denominator bound ensures that these quantities, their minimum, and their differences have polynomial encoding length.

Since \( E_*=\min_a E_a \), every difference \( E_a-E_* \) is nonnegative. The rescaling is common to all weights, so it preserves the normalized distribution: \( p_\mu(a)=V_a/S \).

There is at least one candidate attaining \( E_* \). Its rescaling exponential equals one, and its \( H_a \) is at least \( 2^{-n} \). Hence \( S\ge2^{-n} \) is correct. This remains valid for arbitrarily large binary-encoded \( \beta \) and supplies the needed normalization bound.

• The decaying-exponential approximation lemma

Both branches of the lemma are valid.

In the truncation branch, \( x\ge k+2 \) and \( e>2 \) imply \( e^{-x}\le2^{-x}\le2^{-(k+2)} \). Returning zero therefore satisfies the required accuracy.

In the Taylor branch, \( x<k+2 \), and the polynomial includes precisely the terms of degrees zero through \( N-1 \). Taylor’s theorem applies because \( e^{-t} \) is differentiable to every order on \( [0,x] \). The absolute value of its \( N \)-th derivative is at most one on that interval, giving the stated remainder bound \( x^N/N! \).

The factorial estimate follows from the displayed integral comparison. With \( N=6(k+2) \) and \( e<3 \), one has \( ex/N<1/2 \). Thus the remainder is less than \( 2^{-N} \), which is at most \( 2^{-(k+2)} \).

Downward rounding adds less than \( 2^{-(k+2)} \) error, including when the Taylor value is negative. Clamping to \( [0,1] \) cannot increase distance from the target \( e^{-x}\in[0,1] \). The resulting error is therefore within \( 2^{-k} \).

The bit-complexity argument is also sound. The denominator \( q^{N-1}(N-1)! \) accommodates every Taylor term, and the numerator and denominator have the claimed polynomial lengths. Exact evaluation, division for rounding, and clamping all take polynomial time. The output denominator is \( 2^{k+2} \), so its encoding length is \( O(k) \).

• Approximate products and normalization

Every exponential argument supplied to the lemma is nonnegative and has polynomial encoding length.

The LAP transformation has absolute-error multiplier at most \( 1/2 \). The displayed reciprocal identity proves the required error bound for EXP and RR because both exponential approximations lie in \( [0,1] \). The resulting factors are nonnegative and bounded above by one.

The product estimate applies to exactly \( m=n+1 \) factors: the rescaling exponential and the \( n \) opponent factors. Its telescoping justification is valid, giving \( |\widetilde V_a-V_a|\le m2^{-k} \).

The precision choice satisfies
\( m^2 2^{-k}\le 2^{-r}2^{-n}/4 \),
because \( m^2\le2^{2\lceil\log_2m\rceil} \). Consequently, \( \Delta\le\varepsilon S/4<S \). Since \( |\widetilde S-S|\le\Delta \), the approximate normalizer is strictly positive.

The normalization inequality is correct. Its second contribution sums to \( |\widetilde S-S|/S \), using nonnegativity of the approximate weights and their sum \( \widetilde S>0 \). Therefore,
\( \operatorname{TV}(p_\mu,\widetilde p)\le\Delta/S\le\varepsilon/4 \).

Exact rational products and normalization retain polynomial encoding length. Reciprocal factors have \( O(k) \)-bit encodings, products have \( O(mk) \)-bit encodings, and summing polynomially many such rationals remains polynomial.

• Sampling using exactly the prescribed number of fair bits

The rational cumulative probabilities are well-defined, nondecreasing, and end at one. Their rounded boundaries consequently satisfy \( B_0=0 \) and \( B_m=M \).

Exactly \( K \) independent fair bits produce a uniform integer in \( \{0,\ldots,M-1\} \). The half-open intervals between successive boundaries partition this set. Empty intervals cause no ambiguity, and every possible random-bit string produces exactly one candidate.

The output probabilities are therefore exactly \( q(a_i)=(B_i-B_{i-1})/M \). Each rounded cumulative probability differs from its original value by less than \( 1/M \), so the displayed per-candidate bound and total-variation bound follow.

The choice \( K=r+\lceil\log_2m\rceil+2 \) ensures \( m/M\le\varepsilon/4 \). Combining this with the normalization error yields \( \operatorname{TV}(q,p_\mu)\le\varepsilon/2\le2^{-r} \).

• Running time, boundary cases, and citation

Every deterministic stage has polynomial worst-case bit complexity. The random stage uses exactly \( K=O(r+\log m) \) fair bits and requires only polynomial-time integer comparisons. There is no rejection loop or dependence on the numerical magnitude of \( \beta \).

The argument covers \( m=2 \), support size one, exact ties, tied minimum exponents, zero approximate weights, and empty sampling intervals. The strict positivity of \( \widetilde S \) prevents the only potential normalization failure.

The cited paper does state an \( O(m^2) \) sampling bound immediately after Lemma 1. That citation is contextual; the submitted proof supplies its own bit-complexity argument and does not depend on importing the paper’s sampling analysis. [Li et al., *Differentially Private Condorcet Voting*, p. 5](https://arxiv.org/pdf/2206.13081)

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩