Exact cost of local monotonicity for the Banzhaf and proportional power indices

Let n2n\ge 2, let W\mathfrak{W} denote the class of weighted games, and let cP(n,W)c_{\mathcal{P}}(n,\mathfrak{W}) be the cost of local monotonicity for the power-index collection P=(Bzr,PGIr)\mathcal{P}=\left(\operatorname{Bz}^r,\operatorname{PGI}^r\right). Exact-cost conjecture.

cP(n,W)=max ⁣(0,n3n1).c_{\mathcal{P}}(n,\mathfrak{W})=\max\!\left(0,\frac{n-3}{n-1}\right).

The preceding lower-bound result establishes the right-hand side as a lower bound, and the paper reports that it is attained computationally for all n10n\le 10. The conjecture concerns whether this lower bound is exact for every number of players; resolving it would determine the precise asymptotic cost of enforcing local monotonicity for this pair of indices.

Sources & referencesView supporting material

Primary source

Josep Freixas and Sascha Kurz, “The cost of getting local monotonicity”, arXiv:1411.0944 (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.