The inverse power index lower-bound conjecture for the distribution (0.75,0.25,0,… )(0.75,0.25,0,\dots)

About 14 years old · traced to

For n≥2n\ge 2 voters, let dd be the desired power distribution defined by

d1=0.75,d2=0.25,di=0for 3≤i≤n.d_1=0.75,\qquad d_2=0.25,\qquad d_i=0\quad\text{for }3\le i\le n.

For a simple game (including a complete simple game or a weighted voting game) χ\chi, let SS(χ)\mathcal{SS}(\chi) and BZ(χ)\mathcal{BZ}(\chi) denote its Shapley–Shubik and Banzhaf power vectors, respectively, and let kmk_m and lml_m be defined by k1=1k_1=1, l1=2l_1=2, l2=5l_2=5, and

km={2km−1m≡0(mod2),8km−1−1m≡1(mod2),m≥2,k_m=\begin{cases}2k_{m-1}&m\equiv0\pmod 2,\\8k_{m-1}-1&m\equiv1\pmod 2,\end{cases}\qquad m\ge2, lm={2lm−1+3m≡0(mod2),8lm−1−2m≡1(mod2),m≥3.l_m=\begin{cases}2l_{m-1}+3&m\equiv0\pmod 2,\\8l_{m-1}-2&m\equiv1\pmod 2,\end{cases}\qquad m\ge3.

Inverse power index lower-bound conjecture. Every such simple game satisfies

∥SS(χ)−d∥1≥13\left\|\mathcal{SS}(\chi)-d\right\|_1\ge\frac13

and

∥BZ(χ)−d∥1≥k⌈n/2⌉l⌈n/2⌉.\left\|\mathcal{BZ}(\chi)-d\right\|_1\ge\frac{k_{\left\lceil n/2\right\rceil}}{l_{\left\lceil n/2\right\rceil}}.

The distribution (0.75,0.25,0,… )(0.75,0.25,0,\dots) is motivated by its maximal ℓ1\ell^1-distance from the achievable two-voter power vectors for both indices. Computations for games with at most 1616 voters support the recursive Banzhaf bound, but the paper gives no proof of the conjectured inequalities.

References

Primary source

Sascha Kurz, “On the inverse power index problem”, arXiv:1211.6353 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.