d4-conf-ijcai-2015-0153 (d4-conf-ijcai-2015-0153)

For α∈[0,1], let \(k_N=\lfloor α N\rfloor\). Draw \(N\) binary opinions independently and uniformly, choose a hidden coalition of \(k_N\) advisors uniformly, and let non-colluders report truthfully. Over all joint stochastic reporting kernels \(Q_N(r_{K_N}\mid o_{K_N})\) for the coalition, determine whether \(V(α)=\lim_{N→\infty}N^{-1}\min_{Q_N} I(O^N;R^N)\) exists, its value, and an asymptotically optimal family of kernels.

A society is represented by its support: the list of its \(\tau\) positive-mass types, with masses given as binary rationals summing to \(1\); \(\tau\) is the support size, not the number of possible types. Here the opinion alphabet has size \(m=2\), and the support is \(\{0,1\}\), each with mass \(1/2\). State any running times in \(N,m,\tau,L\) and any precision parameter, where \(L\) is the input bit length.
Fix \(\alpha\in[0,1]\). For each positive integer \(N\), put \(k_N=\lfloor\alpha N\rfloor\), draw \(O_1,\ldots,O_N\) independently from this distribution, and independently choose \(K_N\) uniformly among the \(k_N\)-element subsets of \(\{1,\ldots,N\}\).
An admissible attack is an arbitrary stochastic kernel \(Q_N\) from \(\{0,1\}^{k_N}\) to \(\{0,1\}^{k_N}\), used identically for every coalition after ordering its members by index. It may jointly randomize all coalition reports using only their opinions; reporting truthfully is permitted. Set \(R_i=O_i\) outside \(K_N\). For \(k_N=0\), use the unique empty-vector kernel.
The observer receives the full indexed vector \(R^N\), knows \(k_N\) and the kernel, and does not observe \(K_N\). Mutual information uses base-two logarithms and the joint law with \(K_N\) marginalized out. Write \(a_N(\alpha)=\min_{Q_N}I(O^N;R^N)\). A kernel family is asymptotically optimal when \(\bigl(I_{Q_N}(O^N;R^N)-a_N(\alpha)\bigr)/N\to0\).

Does \(V(\alpha)=\lim_{N\to\infty}a_N(\alpha)/N\) exist for every \(\alpha\in[0,1]\), and, if so, what is its value and which admissible kernel families are asymptotically optimal?

For finite populations, unrestricted coordinated reporting has a published claimed sharp leakage bound and an explicit claimed attaining kernel ([Wang et al., 2015](https://www.ijcai.org/Proceedings/15/Papers/023.pdf)); the displayed bound is inconsistent with the accompanying entropy calculation.
No result addressing this precise normalized limit was located in the literature search.

1. Result

Define the binary entropy function by
\(h_2(p)=-p\log_2 p-(1-p)\log_2(1-p)\), with \(h_2(0)=h_2(1)=0\).

The limit exists for every \(\alpha\in[0,1]\), and
\[ V(\alpha)=1-h_2\!\left(\min\{\alpha,1/2\}\right) = \begin{cases} 1-h_2(\alpha),&0\leq\alpha\leq1/2,\\ 0,&1/2\leq\alpha\leq1. \end{cases} \]

In fact, the exact finite minimum is
\[ a_N(\alpha)=N-\log_2\!\left(\sum_{j=0}^{k_N}\binom Nj\right). \]

Here is a characterization of all asymptotically optimal admissible kernel families. For a given family, let \(E^N=O^N\oplus R^N\) be its error vector, and let
\(T_N=|\{i\in K_N:R_i=O_i\}|\) count coalition members reporting truthfully.

• If \(\alpha=0\), the unique admissible family is optimal.
• If \(0<\alpha\leq1/2\), the family is asymptotically optimal if and only if \(\mathbb E T_N=o(N)\).
• If \(1/2<\alpha\leq1\), the family is asymptotically optimal if and only if

\(N-H(E^N)=o(N)\) and \(I(E^N;R^N)=o(N)\).

All entropies below use base-two logarithms, and coalition membership is marginalized out.

2. Exact finite minimum and an attaining admissible kernel

Fix \(N\) and \(k\in\{0,\ldots,N\}\), and write
\(B_{N,k}=\sum_{d=0}^k\binom Nd\).

Lower bound

Every admissible attack satisfies \(|E^N|\leq k\) almost surely, because reports outside the coalition are truthful.

For each report vector \(r\) of positive probability, the conditional support of \(O^N\) therefore lies in the Hamming ball
\(\{o:|o\oplus r|\leq k\}\), which has exactly \(B_{N,k}\) elements. The entropy of a distribution supported on \(B_{N,k}\) points is at most \(\log_2 B_{N,k}\). Consequently,
\[ H(O^N\mid R^N)\leq\log_2 B_{N,k}. \]
Since the opinions are independent fair bits, \(H(O^N)=N\), giving
\[ I(O^N;R^N)\geq N-\log_2 B_{N,k}. \]

Construction and normalization

Use the following kernel, identically for every ordered coalition:

• Independently of its opinions, draw \(D\in\{0,\ldots,k\}\) with

\(\Pr(D=d)=\binom Nd/B_{N,k}\).

• Choose uniformly a \(d\)-element subset of the \(k\) coalition positions.
• Flip exactly those opinions and report all remaining opinions truthfully.

These instructions use only coalition opinions and internal randomness. The probabilities for \(D\) sum to one, so this defines an admissible stochastic kernel. Explicitly, for coalition vectors \(u,v\) at Hamming distance \(d\),
\[ Q_{N,k}(v\mid u)= \frac{\binom Nd}{B_{N,k}\binom kd}. \]

To verify its induced global error law, fix a subset \(S\subseteq\{1,\ldots,N\}\) of size \(d\leq k\). Exactly \(\binom{N-d}{k-d}\) possible coalitions contain \(S\). Thus
\[ \Pr(E^N=\mathbf 1_S) = \frac{\binom Nd}{B_{N,k}}\, \frac{\binom{N-d}{k-d}}{\binom Nk}\, \frac1{\binom kd} = \frac1{B_{N,k}}, \]
where the final equality uses
\(\binom Nk\binom kd=\binom Nd\binom{N-d}{k-d}\).

Hence \(E^N\) is uniform over all binary vectors of weight at most \(k\). It is also independent of \(O^N\), since coalition selection and all flip choices are independent of the opinions.

Because \(O^N\) is uniform and \(R^N=O^N\oplus E^N\), for every \(e,r\),
\[ \Pr(E^N=e,R^N=r)=\Pr(E^N=e)\,2^{-N}. \]
Therefore \(E^N\) and \(R^N\) are independent. Given \(R^N\), the correspondence between \(O^N\) and \(E^N\) is bijective, so
\[ H(O^N\mid R^N)=H(E^N\mid R^N)=\log_2 B_{N,k}. \]
The lower bound is attained, proving the asserted finite minimum. This includes \(k=0\) and \(k=N\).

Relation to the cited claim

This kernel agrees with equation (3) of [Wang et al., Theorem 5](https://www.ijcai.org/Proceedings/15/Papers/023.pdf). Its normalization and attainment have been checked directly above. The displayed lower endpoint \(2^k/B_{N,k}\) in that theorem is inconsistent with the entropy calculation; the correct endpoint is \(N-\log_2 B_{N,k}\). For example, at \(N=4,k=2\), the minimum is \(4-\log_2 11\), rather than \(4/11\).

3. The normalized limit and a simpler optimal family

Put \(d=\min\{k,\lfloor N/2\rfloor\}\). The largest binomial coefficient among indices \(0,\ldots,k\) is \(\binom Nd\). Hence
\[ \binom Nd\leq B_{N,k}\leq(N+1)\binom Nd. \]

We also have the elementary bounds
\[ \frac{2^{Nh_2(d/N)}}{N+1}\leq\binom Nd\leq2^{Nh_2(d/N)}. \]
For completeness, when \(0<d<N\), set \(p=d/N\). The binomial probability
\(\binom Nd p^d(1-p)^{N-d}\) is a mode of the distribution with parameters \(N,p\): its successive probability ratios decrease, and the ratios immediately before and after \(d\) are respectively
\((N-d+1)/(N-d)>1\) and \(d/(d+1)<1\).
A mode has probability at least \(1/(N+1)\), and every probability is at most one. Substituting
\(p^d(1-p)^{N-d}=2^{-Nh_2(p)}\) proves the bounds. The endpoint cases follow directly.

Combining these inequalities gives
\[ \left| \frac{N-\log_2 B_{N,k}}N- \left(1-h_2(d/N)\right) \right| \leq\frac{\log_2(N+1)}N. \]
For \(k=k_N\), we have \(d/N\to\min\{\alpha,1/2\}\). Continuity of \(h_2\) proves the claimed limit.

A simpler asymptotically optimal kernel is:

Choose uniformly exactly \(d_N=\min\{k_N,\lfloor N/2\rfloor\}\) coalition positions and flip their opinions.

The same counting argument shows that its global error vector is uniform over all vectors of weight exactly \(d_N\), independently of the opinions. Its leakage is therefore
\[ I(O^N;R^N)=N-\log_2\binom N{d_N}. \]
Its excess over the exact minimum satisfies
\[ 0\leq I(O^N;R^N)-a_N(\alpha) =\log_2\frac{B_{N,k_N}}{\binom N{d_N}} \leq\log_2(N+1). \]
Thus this family is asymptotically optimal for every \(\alpha\). For \(\alpha\leq1/2\), it simply flips every coalition opinion.

4. Characterization of all asymptotically optimal families

The following arguments apply to arbitrary admissible kernels, including kernels whose randomness depends jointly on the coalition opinions.

A general entropy identity

For fixed \(R^N\), the transformation \(O^N\mapsto E^N=O^N\oplus R^N\) is bijective. Consequently,
\[ I(O^N;R^N) =N-H(E^N\mid R^N) =N-H(E^N)+I(E^N;R^N). \]
Both terms on the right are nonnegative, because \(E^N\) is a binary vector of length \(N\).

The regime \(0<\alpha\leq1/2\)

Let \(q_N=\mathbb E|E^N|/N\). Entropy subadditivity and concavity of \(h_2\) give
\[ H(E^N)\leq\sum_{i=1}^N h_2(\Pr(E_i=1)) \leq Nh_2(q_N). \]
Thus
\[ \frac{I(O^N;R^N)}N\geq1-h_2(q_N). \]
Since errors occur only inside the coalition,
\[ q_N=\frac{k_N-\mathbb E T_N}{N}\leq\frac{k_N}N\leq\alpha. \]

If the family is asymptotically optimal, its normalized leakage converges to \(1-h_2(\alpha)\). The preceding inequality, together with the strict increase of \(h_2\) on \([0,1/2]\), forces \(q_N\to\alpha\). Since \(k_N/N\to\alpha\), this implies \(\mathbb E T_N/N\to0\). This proves necessity.

For sufficiency, couple the given reports with the reports \(R^{*,N}\) obtained by flipping every member of the same coalition. Define
\(Z^N=R^N\oplus R^{*,N}\). Binary reporting implies \(|Z^N|=T_N\) exactly.

The all-flip channel has leakage
\[ I(O^N;R^{*,N})=N-\log_2\binom N{k_N}. \]
Furthermore, the mutual-information chain rule gives
\[ I(O^N;R^N) \leq I(O^N;R^{*,N})+H(R^N\mid R^{*,N}) \leq I(O^N;R^{*,N})+H(Z^N). \]
Again using subadditivity and concavity,
\[ H(Z^N)\leq Nh_2(\mathbb E T_N/N). \]
Because \(k_N\leq\lfloor N/2\rfloor\), Section 3 bounds the all-flip channel’s excess leakage by \(\log_2(N+1)\). Hence
\[ 0\leq I(O^N;R^N)-a_N(\alpha) \leq\log_2(N+1)+Nh_2(\mathbb E T_N/N). \]
If \(\mathbb E T_N=o(N)\), the right side is \(o(N)\). This proves sufficiency, including the boundary \(\alpha=1/2\).

The regime \(1/2<\alpha\leq1\)

Here \(a_N(\alpha)/N\to0\), so asymptotic optimality is equivalent to \(I(O^N;R^N)=o(N)\).

The general identity above expresses this leakage as the sum of two nonnegative terms. Therefore asymptotic optimality holds exactly when
\[ N-H(E^N)=o(N), \qquad I(E^N;R^N)=o(N). \]
Equivalently, the first condition is
\(D(P_{E^N}\Vert U_N)=o(N)\), where \(U_N\) is uniform on \(\{0,1\}^N\) and relative entropy uses base-two logarithms.

These conditions imply \(\mathbb E|E^N|/N\to1/2\), since
\(H(E^N)\leq Nh_2(q_N)\) and \(h_2\) has its unique maximum at \(1/2\). The converse does not follow from the average flip count alone.

To see this, for sufficiently large \(N\), flip the entire coalition with probability \(t_N=N/(2k_N)\), and otherwise report truthfully. Then \(q_N=1/2\) exactly. Nevertheless, its opinion-independent error vector has entropy
\[ H(E^N)=h_2(t_N)+t_N\log_2\binom N{k_N}. \]
It is independent of \(R^N\), by the uniform-input argument from Section 2. Consequently,
\[ \frac{I(O^N;R^N)}N \longrightarrow 1-\frac{h_2(\alpha)}{2\alpha}>0, \]
where strict positivity follows from \(h_2(\alpha)\leq1<2\alpha\). This family has the required average flip count but is not asymptotically optimal.

5. Representation and computation

Here \(m=\tau=2\). The constructions use the listed support directly; no enumeration of additional possible types is needed.

Given the integers \(N,k_N\), the exact attaining kernel has a succinct sampling description. Using elementary integer arithmetic, its binomial weights can be constructed and it can be sampled exactly in expected \(O(L+N^3)\) bit operations, with \(O(L+N^2)\) bits of storage. Indeed, all binomial coefficients and cumulative weights have \(O(N)\) bits; there are \(O(N)\) recurrence steps. Exact sampling uses rejection sampling of uniform integers followed by uniform subset selection. No numerical precision parameter is needed.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task. The exact finite minimum, normalized limit, and characterization of all asymptotically optimal families are correct. I found no major or minor mathematical gaps.

• Finite lower bound.

Reports outside the coalition are truthful, so the error vector satisfies \(|E^N|\leq k\) almost surely. Consequently, for each report vector of positive probability, the conditional opinion distribution is supported on a Hamming ball containing exactly \(B_{N,k}\) vectors.

The support-size entropy bound applies directly and yields
\(H(O^N\mid R^N)\leq\log_2 B_{N,k}\).
Independence and fairness of the opinions give \(H(O^N)=N\), so the asserted lower bound follows. This argument correctly marginalizes coalition membership.

• Admissibility and normalization of the attaining kernel.

The construction uses coalition opinions only to produce the chosen flips. Its random choices require the known parameters \(N,k\), but neither outside opinions nor coalition indices. Choosing positions uniformly within the ordered coalition defines the same kernel for every coalition.

The distribution of \(D\) is normalized. Conditional on \(D=d\), there are exactly \(\binom{k}{d}\) possible outputs for each input, each receiving the stated probability. Thus every kernel row sums to one.

For a fixed error support \(S\) of size \(d\), the coalition-counting calculation is correct. The identity
\(\binom{N}{k}\binom{k}{d}=\binom{N}{d}\binom{N-d}{k-d}\)
cancels all factors except \(1/B_{N,k}\). Therefore the global error vector is uniform on the required Hamming ball.

• Attainment and endpoint cases.

Coalition selection and flip selection are independent of the opinions, establishing independence of \(E^N\) and \(O^N\). Uniformity of \(O^N\) then gives the displayed joint law of \(E^N,R^N\), establishing their independence.

The conditional bijection between opinions and errors is valid for every fixed report vector. Hence conditional entropy equals \(\log_2 B_{N,k}\), attaining the lower bound.

Both endpoint cases are included correctly: \(k=0\) gives the unique truthful channel and leakage \(N\); \(k=N\) gives uniform errors on the entire binary cube and leakage zero. The minimum is attained explicitly, so no separate existence argument is missing.

• Comparison with the cited publication.

The attribution is accurate. Equation (3), together with the paper’s uniform coalition probability, agrees with the proposed kernel after applying the same binomial identity. Theorem 5 displays the endpoint described by the prover, whereas its entropy argument supports the corrected endpoint. The numerical example has \(B_{4,2}=11\), so the two expressions are indeed different. See [Wang et al., Theorem 5 and equation (3)](https://www.ijcai.org/Proceedings/15/Papers/023.pdf).

The prover establishes attainment independently; the publication’s erroneous bound is not used as a premise.

• Binomial estimates and the normalized limit.

The selected index \(d=\min\{k,\lfloor N/2\rfloor\}\) maximizes the binomial coefficient over the permitted indices, including the tied central coefficients for odd \(N\).

The binomial-probability argument is correct. At \(p=d/N\), the ratios immediately before and after index \(d\) have the stated values, establishing that index as a mode. Its probability lies between \(1/(N+1)\) and one, giving the asserted entropy estimates. The endpoint cases are immediate and are explicitly covered.

Combining the estimates gives the stated absolute error bound with exactly the claimed constant. The floor operations have vanishing normalized effect, and continuity of binary entropy establishes existence and the stated value of the limit for every permitted \(\alpha\).

• The simpler asymptotically optimal family.

Uniformly selecting exactly \(d_N\) coalition positions is admissible. The counting argument produces uniform global errors of that weight, independently of the opinions.

Its leakage formula follows by the already verified uniform-input argument. Its excess leakage is nonnegative and at most \(\log_2(N+1)\), which is sublinear. For \(\alpha\leq1/2\), the equality \(d_N=k_N\) holds for every positive integer \(N\), including odd \(N\) at the boundary.

• Characterization when \(0<\alpha\leq1/2\).

The general entropy identity remains valid for opinion-dependent kernels: its justification uses a conditional bijection, not independence.

Entropy subadditivity and concavity give the stated bound in terms of the mean error fraction. That fraction lies in \([0,\alpha]\). Strict increase of binary entropy on this interval, together with convergence of optimal normalized leakage, correctly forces \(q_N\to\alpha\). The identity relating errors and truthful coalition reports then establishes necessity.

For sufficiency, the coupling uses the same opinions and coalition, so it is well-defined for every admissible kernel. Binary reporting makes the number of discrepancies from the all-flip reports exactly \(T_N\).

The mutual-information inequality follows from the chain rule and nonnegativity of conditional mutual information. Conditional on the all-flip reports, the discrepancy vector determines the given reports, giving the entropy bound used next. The final excess bound tends to zero after division by \(N\) whenever \(\mathbb E T_N=o(N)\). This includes \(\alpha=1/2\).

• Characterization when \(1/2<\alpha\leq1\).

Since the optimal normalized leakage tends to zero, asymptotic optimality is equivalent to sublinear leakage. The entropy identity expresses leakage as a sum of two nonnegative quantities. Therefore the two stated sublinear conditions are jointly necessary and sufficient.

The relative-entropy reformulation is correct. The implication for average error weight follows from the unique maximum of binary entropy.

The example showing that average error weight alone is insufficient is also correct. For sufficiently large \(N\), its mixing probability is valid, its mean error fraction is exactly \(1/2\), and its two error-weight components have disjoint supports. This justifies the entropy formula. The limiting leakage is strictly positive throughout the stated regime, including \(\alpha=1\).

• Representation and computational claims.

The discussion correctly treats \(m=\tau=2\) as fixed and uses the listed support. The sampling bound is conditional on receiving the integers \(N,k_N\), as explicitly stated; it does not assume an encoding or effective access procedure for arbitrary real \(\alpha\).

The claimed bit-operation and storage bounds are conservative bounds consistent with elementary arithmetic on the binomial weights, cumulative weights, rejection sampling, and uniform subset selection. Exact rational sampling requires no numerical precision parameter. These are polynomial bounds in the stated parameters \(N,L\); they do not assert polynomial dependence on \(L\) alone when \(N\) is binary encoded.

No additional clarification is needed to verify the mathematical conclusion.

⟨structured verdict parsed — rendered above⟩