Sharp nucleolus norm bound for normalized weights

At least 11 years old · documented by

Let [q;w1,…,wn][q;w_1,\dots,w_n] be a weighted majority game with q∈(0,1)q\in(0,1) and w∈R≥0nw\in\mathbb{R}_{\ge0}^n normalized by ∥w∥1=1\Vert w\Vert_1=1. Let Δ=max⁡1≤i≤nwi\Delta=\max_{1\le i\le n}w_i, and let Nuc⁡\operatorname{Nuc} denote the nucleolus. Nucleolus norm-bound conjecture.

∥Nuc⁡([q;w1,…,wn])−(w1,…,wn)∥1≤Δmin⁡(q,1−q)\left\Vert \operatorname{Nuc}([q;w_1,\dots,w_n])-(w_1,\dots,w_n)\right\Vert_1\le\frac{\Delta}{\min(q,1-q)}

is valid and tight for normalized weights. The surrounding discussion explains that such bounds control the error obtained by using desired power distributions as weights, but the stated sharp bound is not resolved in the supplied text.

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.