A SEARCH-BASED APPROACH TO ANNEXATION AND MERGING IN WEIGHTED VOTING GAMES

摘要

Weighted voting games are classic cooperative games which provide a compact representation for coalition formation models in multiagent systems. We consider manipulation in weighted voting games via annexation and merging, which involves an agent or some agents misrepresenting their identities in anticipation of gaining more power at the expense of other agents in a game. We show that annexation and merging in weighted voting games can be more serious than as presented in the previous work. Specifically, using similar assumptions as employed in a previous work, we show that manipulators need to do only a polynomial amount of work to find a much improved power gain, and then present two search-based pseudo-polynomial algorithms that manipulators can use. We empirically evaluate our search-based method for annexation and merging. Our method is shown to achieve significant improvement in benefits for manipulating agents in several numerical experiments. While our search-based method achieves improvement in benefits of over 300% more than those of the previous work in annexation, the improvement in benefits is 28% to 45% more than those of the previous work in merging for all the weighted voting games we considered.