Skip to main content

bibtex

@inproceedings{AAMAS2009Haris,
author = {H. Aziz and M. Paterson},
title = {False name manipulations in weighted voting games: splitting, merging and annexation},
booktitle = {Proceedings of the The Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS)},
series = {},
volume = {},
pages = {},
publisher = {},
month = {},
year = {2009},
doi = {},
note = {Accepted}
}

 

@ARTICLE{Aziz-comsoc2008,
title={Complexity of comparison of influence of players in simple games},
author={H. Aziz},
journal={Proceedings of the Second International Workshop on Computational Social Choice (COMSOC 2008)},
year={2008},
month={},
volume={2},
number={},
pages={61-72},
abstract={Coalitional voting games appear in different forms in multi-agent systems, social choice and threshold logic. In this paper, the complexity of comparison of influence between players in coalitional voting games is characterized. The possible representations of simple games considered are
simple games represented by winning coalitions, minimal winning coalitions, weighted voting game or a multiple weighted voting game. The influence of players is gauged from the viewpoint of basic player types, desirability relations and classical power indices such as Shapley-Shubik index, Banzhaf index, Holler index, Deegan-Packel index and Chow parameters. Among other results, it is shown that for a simple game represented by minimal winning coalitions, although it is easy to verify whether a player has zero or one voting power, computing the Banzhaf value of the player is $\#$P-complete. Moreover, it is proved that multiple weighted voting games are the only representations for which it is NP-hard to verify whether the game is linear or not. For a simple game with a set $W^m$ of minimal winning coalitions and $n$ players, a $O(n.|W^m|+n^2log(n))$ algorithm is presented which returns `no' if the game is non-linear and returns the strict desirability ordering otherwise. The complexity of transforming simple games into compact representations is also examined.},
doi={http://www.csc.liv.ac.uk/~pwg/COMSOC-2008/proceedings.html},
ISSN={}, }

 

@ARTICLE{Aziz-Lampsade-DIMACS2008,
title={Complexity of some aspects of control and manipulation in weighted voting games},
author={H. Aziz and M. Paterson},
journal={Annales du Lamsade},
year={2008},
month={},
volume={},
number={9},
pages={1-16},
abstract={An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere behaviour. Manipulative behaviour has received increased attention since the famous Gibbard-Satterthwaite theorem. We examine the computational complexity of manipulation in weighted voting games which are ubiquitous mathematical models used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. It is a natural question to check how changes in weighted voting game may affect the overall game. Tolerance and amplitude of a weighted voting game signify the possible variations in a weighted voting game which still keep the game unchanged. We characterize the complexity of computing the tolerance and amplitude of weighted voting games. Tighter bounds and results for the tolerance and amplitude of key weighted voting games are also provided. Moreover, we examine the complexity of manipulation and show limits to how much the Banzhaf index of a player increases or decreases if it splits up into sub-players. It is shown that the limits are similar to the previously examined limits for the Shapley-Shubik index. A pseudo-polynomial algorithm to find the optimal split is also provided.},
doi={},
ISSN={}, }

@ARTICLE{Aziz-classification,
title={Classification of computationally tractable weighted voting games},
author={H. Aziz and Mike Paterson},
journal={Lecture Notes in Engineering and Computer Science, World Congress on Engineering},
year={2008},
month={},
volume={1},
number={},
pages={129-134},
abstract={\emph{Weighted voting games} are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model situations where agents with variable voting weight vote in favour of or against a decision. A coalition of agents is winning if and only if the sum of weights of the coalition exceeds or equals a specified quota. The Banzhaf index is a measure of voting power of an agent in a weighted voting game. It depends on the number of coalitions in which the agent is the difference in the coalition winning or losing. It is well known that computing Banzhaf indices in a weighted voting game is \#P-complete. We give a comprehensive characterization of weighted voting games which can be solved in polynomial time. Among other results, we provide a polynomial ($O(k{(\frac{n}{k})}^k)$) algorithm to compute the Banzhaf indices in weighted voting games in which the number of weight values is bounded by $k$. },
doi={},
ISSN={}, }



@inproceedings{easyWVGs,
author = {H. Aziz and M. Paterson},
title = {Computing voting power in easy weighted voting games},
booktitle = {Proceedings of CO 2008 - International Symposium on Combinatorial Optimization 2008},
publisher = {},
series = {},
volume = {},
month = {},
year = {2008},
note = {}
}



@ARTICLE{Aziz-Leech2008,
title={The double majority voting rule of the EU reform treaty as a democratic ideal for an enlarging union: an appraisal using voting power analysis},
author={D. Leech and H. Aziz},
journal={Proceedings of Annual Meeting of the European Public Choice Society 2008, Jena, Germany},
year={2008},
month={},
volume={},
number={},
pages={},
abstract={The Double Majority rule in the Treaty is claimed to be simpler, more transparent and more democratic than the existing rule. We examine these questions against the democratic ideal that the votes of all citizens in whatever member country should be of equal value using voting power analysis considering possible future enlargements involving candidate countries and then to a number of hypothetical future enlargements. We find the Double Majority rule to fails to measure up to the democratic ideal in all cases. We find the Jagiellonian compromise to be very close to this ideal.},
doi={},
ISSN={}, }

 

@ARTICLE{Aziz2007a,
title={Efficient Algorithm for Designing Weighted Voting Games},
author={Aziz, H. and Paterson, M. and Leech, D.},
journal={IEEE International Multitopic Conference},
year={2007},
month={},
volume={},
number={},
pages={},
abstract={eighted voting games are mathematical models, used to analyse situations where voters with variable voting weight vote in favour of or against a decision. They have been applied in various political and economic organizations. Similar combinatorial models are also encountered in neuroscience, threshold logic, reliability theory and distributed systems. The calculation of voting powers of players in a weighted voting game has been extensively researched in the last few years. However, the inverse problem of designing a weighted voting game with a desirable distribution of power has received less attention. We present an elegant algorithm which uses generating functions and interpolation to compute an integer weight vector for target Banzhaf power indices. This algorithm has better performance than any other known to us. It can also be used to design egalitarian two-tier weighted voting games and a representative weighted voting game for a multiple weighted voting game.},
keywords={game theory, interpolation, politicscombinatorial model, economic organization, integer weight vector, interpolation, inverse problem, mathematical model, political organization, target Banzhaf power index, weighted voting game design},
doi={10.1109/INMIC.2007.4557718},
ISSN={}, }


@inproceedings{MWVGspaper,
author = {H. Aziz and M. Paterson},
title = {Computational and combinatorial aspects of multiple weighted voting games},
booktitle = {Algorithms and Complexity in Durham 2007 - Proceedings of
the Third ACiD Workshop, 2007, Durham, UK},
publisher = {King's College, London},
series = {Texts in Algorithmics},
volume = {},
month = {},
year = {2007},
note = {}
}