d4-conf-ijcai-2016-0043 (d4-conf-ijcai-2016-0043)

Given \(m\) candidates, \(z\) equal-mass districts, fixed tie-breaking, and a polynomial-time sampler \(M\) that outputs rational mass vectors \(\mu\) over types \((d,\pi)\) with total mass \(1/z\) in each district, estimate \(\mathbb{E}_{\mu\sim M}[\mathrm{MR}_\infty(\mu)]\) within additive error \(\varepsilon\) with probability at least \(1-\delta\). For plurality, \(\mathrm{MR}_\infty(\mu)\le m^2\), so Hoeffding sampling uses at most \(\left\lceil (m^2-1)^2\ln(2/\delta)/(2\varepsilon^2)\right\rceil\) samples; each sample’s ratio is computable from its supported types.

Let \(C\) contain \(m\ge 2\) candidates and let \(z\ge 1\) be the number of districts. A type is \((d,\pi)\), where \(d\in\{1,\ldots,z\}\) and \(\pi\) is a strict ranking of \(C\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Require \(\sum_\pi\mu(d,\pi)=1/z\) for every district, so total mass is \(1\).
Each district selects its plurality winner using mass-weighted scores; the overall winner \(w(\mu)\) is the candidate winning the most districts. Fixed input priority orders resolve ties at both levels. Let \(S_c(\mu)\) be candidate \(c\)'s global mass-weighted plurality score and define \(\mathrm{MR}_\infty(\mu)=\max_{c\in C}S_c(\mu)/S_{w(\mu)}(\mu)\).
Access to \(M\) consists of independent sampling calls, each returning such a society in time at most \(T_M\). Let \(\tau\) bound every output's support size and \(L\) bound the binary encoding lengths of the input and each output. Accuracy parameters \(\varepsilon,\delta\) are binary rationals with \(0<\varepsilon,\delta<1\).

Can \(r=\mathbb{E}_{\mu\sim M}[\mathrm{MR}_\infty(\mu)]\) be estimated by a randomized algorithm returning \(\widehat r\) with \(\Pr(|\widehat r-r|\le\varepsilon)\ge1-\delta\), in time polynomial in \(m,z,\tau,L,T_M,\varepsilon^{-1},\log(1/\delta)\), or is achieving this approximation guarantee NP-hard?

For finite equal-size districts, Bachrach, Lev, Lewenberg and Zick established additive estimation with confidence \(1-\delta\), polynomial in the score-ratio range, \(\varepsilon^{-1}\), and \(\log(1/\delta)\), assuming efficient sampling and winner computation. [Source](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/main.pdf)
No result explicitly addressing this supported rational-mass sampling problem was located in the literature search.

Result

The requested guarantee is achievable in randomized polynomial time. An empirical mean of independently sampled ratios suffices. The essential facts are a uniform bound \(\mathrm{MR}_\infty(\mu)\le m^2\) and polynomial-time exact evaluation of each ratio from its supported rational representation.

1. A uniform bound on the ratio

For each district \(d\) and candidate \(c\), define the district plurality score
\[ \]
\(s_{d,c}=\sum_{\pi:\,\pi\text{ ranks }c\text{ first}}\mu(d,\pi).\)

Every ranking has exactly one first-ranked candidate. Consequently, the prescribed district normalization gives
\[ \]
\(\sum_{c\in C}s_{d,c}=1/z.\)

Let \(h_d\) be the selected winner of district \(d\). Since tie-breaking selects a candidate with maximum score,
\[ \]
\(s_{d,h_d}=\max_{c\in C}s_{d,c}\ge 1/(mz).\)

Define \(K_c=|\{d:h_d=c\}|\). Each district selects exactly one winner, so \(\sum_{c\in C}K_c=z\). The overall winner \(w=w(\mu)\) maximizes \(K_c\), even when selected by tie-breaking. Thus
\[ \]
\(K_w\ge\lceil z/m\rceil.\)

The global score of \(w\) includes its scores in all districts it wins. Nonnegativity therefore implies
\[ \]
\(S_w(\mu)=\sum_{d=1}^{z}s_{d,w}\ge \frac{K_w}{mz}\ge\frac{\lceil z/m\rceil}{mz}\ge\frac1{m^2}.\)

Also, the global candidate scores sum to the total mass:
\[ \]
\(\sum_{c\in C}S_c(\mu)=1.\)

Hence \(\max_c S_c(\mu)\le1\). The denominator is strictly positive, and including \(w\) among the candidates in the numerator gives
\[ \]
\(1\le\mathrm{MR}_\infty(\mu)=\frac{\max_c S_c(\mu)}{S_w(\mu)}\le m^2.\)

This bound holds for every permitted society, independently of the smallest positive mass and of either priority order. In particular, the expectation \(r\) exists and is finite.

2. Exact evaluation from the support

Consider a sampled society with support size \(t\le\tau\), and write its masses as \(a_j/b_j\), with positive integer denominators. Set
\[ \]
\(Q=\prod_{j=1}^{t}b_j.\)

Each mass can be represented exactly as the integer weight
\[ \]
\(u_j=a_j(Q/b_j).\)

Because the masses sum to one, \(\sum_j u_j=Q\). Accumulate these integer weights according to district and first-ranked candidate. All district scores then have common denominator \(Q\), so their comparisons, including exact ties, reduce to integer comparisons. Apply the input district priorities, count district wins, and apply the overall priority.

Similarly, let \(A_c=QS_c(\mu)\), obtained by summing the appropriate integer weights. The exact sampled ratio is
\[ \]
\(\mathrm{MR}_\infty(\mu)=\frac{\max_c A_c}{A_w},\)

where \(A_w>0\) by Section 1.

Conservatively, each denominator has at most \(L\) bits, so \(Q\) has at most \(O(\tau L)\) bits. Every accumulated score lies between zero and \(Q\). Integer multiplication, exact division, addition, and comparison on these lengths take polynomial time. Reading the supported rankings and processing the candidate–district scores likewise takes polynomial time in \(m,z,\tau,L\).

Thus there is a deterministic exact evaluation procedure whose running time is polynomial in \(m,z,\tau,L\). It never enumerates unsupported rankings or expands rational masses into individual voters.

3. Estimator and accuracy proof

Put \(B=m^2-1\). Let \(k\) be the smallest nonnegative integer satisfying
\[ \]
\(2^k\delta\ge2,\)

and choose
\[ \]
\(N=\left\lceil\frac{B^2k}{2\varepsilon^2}\right\rceil.\)

The integer \(k\) is computable by exact rational comparisons. Moreover,
\[ \]
\(k=\lceil\log_2(2/\delta)\rceil\ge\ln(2/\delta).\)

Make \(N\) independent calls to \(M\), compute the exact values \(X_i=\mathrm{MR}_\infty(\mu_i)\), and return
\[ \]
\(\widehat r=\frac1N\sum_{i=1}^{N}X_i.\)

The variables \(X_i\) are independent, each has expectation \(r\), and each belongs to \([1,m^2]\).

Hoeffding’s inequality states that independent variables in a common interval of length \(B\) satisfy
\[ \]
\(\Pr\left(\left|\frac1N\sum_{i=1}^{N}X_i-\frac1N\sum_{i=1}^{N}\mathbb E[X_i]\right|\ge\varepsilon\right)\le2\exp\left(-\frac{2N\varepsilon^2}{B^2}\right).\)

All its hypotheses have just been verified. Substituting the chosen sample count yields
\[ \]
\(\Pr(|\widehat r-r|\ge\varepsilon)\le2e^{-k}\le\delta.\)

Therefore
\[ \]
\(\Pr(|\widehat r-r|\le\varepsilon)\ge1-\delta.\)

This is the same bounded-range sampling principle used in Theorem 5.1 of [Bachrach, Lev, Lewenberg and Zick](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/main.pdf). The preceding sections establish the range and exact evaluation requirements directly for the supported rational-mass model.

4. Bit complexity and conclusion

The sample count satisfies
\[ \]
\(N=O\!\left(m^4\varepsilon^{-2}\bigl(1+\log(1/\delta)\bigr)\right).\)

Sampling costs at most \(NT_M\). Each sampled ratio has numerator and denominator of \(O(\tau L)\) bits. To form the exact empirical mean, one may use the product of these denominators as a common denominator and then divide by \(N\). The resulting numerator and denominator have at most
\[ \]
\(O(N\tau L+\log N+\log m)\)

bits: the denominator product has \(O(N\tau L)\) bits, and the sum is at most \(Nm^2\) times that product. Consequently, exact accumulation and output also take polynomial time in the requested parameters.

The first alternative in the question is therefore proved: efficient independent sampling permits the stated additive approximation in randomized polynomial time.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the requested estimation problem correctly. The uniform ratio bound, exact evaluation procedure, concentration inequality, and bit-complexity analysis all hold under the stated assumptions. No mathematical gaps or false steps were found.

Step-by-step verification

1. Uniform bound on the ratio

Every strict ranking contributes its mass to exactly one first-ranked candidate. Thus the district normalization correctly implies
\[ \sum_{c\in C}s_{d,c}=\frac1z. \]

Among \(m\) nonnegative scores summing to \(1/z\), the maximum is at least \(1/(mz)\). Because district tie-breaking selects a maximizer, the asserted bound on \(s_{d,h_d}\) holds regardless of the priority order.

Each district contributes exactly one district win. Consequently, the nonnegative integer counts \(K_c\) sum to \(z\), and their maximum is at least \(\lceil z/m\rceil\). Overall tie-breaking also selects a maximizer, so this applies to \(K_w\).

Summing the winning candidate’s scores over the districts it wins gives the valid lower bound
\[ S_w(\mu)\ge\frac{K_w}{mz} \ge\frac{\lceil z/m\rceil}{mz} \ge\frac1{m^2}. \]
The final inequality follows from \(\lceil z/m\rceil\ge z/m\). Contributions from other districts are nonnegative.

The global candidate scores sum to one, so their maximum is at most one. Since the numerator includes the winning candidate, the conclusion
\[ 1\le\mathrm{MR}_\infty(\mu)\le m^2 \]
is correct. In particular, division by zero cannot occur, and the expectation exists.

These arguments cover \(z=1\), \(z<m\), candidates with zero global score, and ties at either level.

2. Exact evaluation from the support

The common denominator \(Q=\prod_j b_j\) is valid without requiring reduced fractions. Each \(Q/b_j\) is an integer, so the weights \(u_j=a_j(Q/b_j)\) represent the original masses exactly.

Total mass one implies \(\sum_j u_j=Q\). Hence every individual weight and every accumulated score lies between zero and \(Q\).

Accumulation by district and first-ranked candidate computes precisely the district plurality scores after multiplication by \(Q\). Integer comparison therefore preserves both strict comparisons and exact ties. Applying the supplied priorities and counting district wins computes the prescribed overall winner.

The global integers \(A_c\) likewise equal \(QS_c(\mu)\), so the returned fraction is exactly the required ratio. Section 1 guarantees its denominator is positive.

The bound of \(O(\tau L)\) bits for \(Q\) is conservative and valid. Products, exact divisions, sums, comparisons, and processing explicitly listed rankings all take polynomial time in the stated parameters. Unsupported types need not be enumerated.

3. Sample count and probability guarantee

Because \(m\ge2\), the interval length \(B=m^2-1\) is positive. Because \(0<\delta<1\), the integer \(k\) exists and is positive.

Its stated characterization is correct:
\[ k=\left\lceil\log_2(2/\delta)\right\rceil \ge\ln(2/\delta). \]
Here \(2/\delta>1\), and division by \(\ln 2<1\) makes the base-two logarithm at least the natural logarithm.

The independent sampling assumption supplies independent \(X_i\) with common expectation \(r\). Section 1 supplies the common bounded interval required by the precisely stated Hoeffding inequality.

The ceiling in the definition of \(N\) ensures
\[ \frac{2N\varepsilon^2}{B^2}\ge k. \]
Therefore the displayed tail bound is valid:
\[ \Pr(|\widehat r-r|\ge\varepsilon)\le2e^{-k}\le\delta. \]
This implies the requested guarantee with \(\le\varepsilon\); the different strictness of the complementary events causes no problem.

The attribution to Theorem 5.1 accurately describes its bounded-range sampling argument. The rational-mass result is established directly here, rather than assumed from the finite-voter theorem. [Cited paper](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/main.pdf)

4. Bit complexity and total runtime

The sample count has the claimed polynomial bound. Exact computation of \(k\) and \(N\) from binary rational parameters also fits the requested runtime.

Each sampled ratio has numerator and denominator of \(O(\tau L)\) bits. The product of their denominators therefore has \(O(N\tau L)\) bits. The stated bound on the numerator of their sum follows from every ratio being at most \(m^2\); dividing by \(N\) adds at most \(O(\log N)\) denominator bits.

Thus exact accumulation and writing the output remain polynomial-time operations. Together with sampling cost at most \(NT_M\), this establishes polynomial time in every parameter requested by the task.

Issues and required clarification

None. The argument establishes the randomized polynomial-time alternative under the supplied sampling and representation assumptions.

⟨structured verdict parsed — rendered above⟩