Sharp nucleolus norm bound for normalized weights

Let [q;w1,,wn][q;w_1,\dots,w_n] be a weighted majority game with q(0,1)q\in(0,1) and wR0nw\in\mathbb{R}_{\ge0}^n normalized by w1=1\Vert w\Vert_1=1. Let Δ=max1inwi\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,1q)\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.

Sources & referencesView supporting material

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.