On \(\alpha\)-roughly weighted games (Q403979): Difference between revisions

The authors study the concept of \(\alpha\)-roughly weighted games, a class of voting games introduced by \textit{T. Gvozdeva} et al. [Int. J. Game Theory 42, No. 1, 1--17 (2013; Zbl 1282.91029)]. For games in this class, voters can each be given a weight so that coalitions with total weight greater than \( \alpha\) are winning, while coalitions with total weight less than 1 are losing. Coalitions with total weight in \([1,\alpha]\) might be winning or losing. This paper mainly investigates the notion of the \textit{critical threshold value} for a given game, the smallest value of \(\alpha\) for which the game is \(\alpha\)-roughly weighted. A number of results are given on the maximum critical threshold value possible for a game with \(n\) voters (with varying assumptions on the game) and the spectrum of possible critical threshold values for a given type of game. The authors make a connection to the \textit{cost of stability} of the voting game as well. The paper emphasizes the linear programs used to speed up the relevant calculations for small values of \(n\).