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

Ramoni O. Lasisi, Vicki H. Allan

2012

Abstract

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.

Paper Citation

in Harvard Style

O. Lasisi R. and H. Allan V. (2012). A SEARCH-BASED APPROACH TO ANNEXATION AND MERGING IN WEIGHTED VOTING GAMES . In Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-8425-96-6, pages 44-53. DOI: 10.5220/0003741300440053

in Bibtex Style

@conference{icaart12,
author={Ramoni O. Lasisi and Vicki H. Allan},
title={A SEARCH-BASED APPROACH TO ANNEXATION AND MERGING IN WEIGHTED VOTING GAMES},
booktitle={Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2012},
pages={44-53},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003741300440053},
isbn={978-989-8425-96-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - A SEARCH-BASED APPROACH TO ANNEXATION AND MERGING IN WEIGHTED VOTING GAMES
SN - 978-989-8425-96-6
AU - O. Lasisi R.
AU - H. Allan V.
PY - 2012
SP - 44
EP - 53
DO - 10.5220/0003741300440053