Uniform Banzhaf and Shapley–Shubik approximation lower bounds

About 12 years old · traced to

For each n∈Nn\in\mathbb{N}, let σn=(0.75,0.25,0,…,0)∈R≥0n\sigma^n=(0.75,0.25,0,\dots,0)\in\mathbb{R}_{\ge0}^n, and let vv be a simple game on nn voters. Uniform approximation lower-bound conjecture.

∥Bz⁡(v)−σn∥1≥1437and∥SSI⁡(v)−σn∥1≥13.\left\Vert\operatorname{Bz}(v)-\sigma^n\right\Vert_1\ge\frac{14}{37}\qquad\text{and}\qquad\left\Vert\operatorname{SSI}(v)-\sigma^n\right\Vert_1\ge\frac13.

These bounds concern non-approximability of a concentrated desired power distribution; the supplied text gives no resolution.

References

Primary source

Sascha Kurz, “Ready for the design of voting rules?”, arXiv:1405.0823 (2014).

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.