k-Prize Weighted Voting Games

Wei-Chen Lee; David Hyland; Alessandro Abate; Edith Elkind; Jiarui Gan; Julian Gutierrez; Paul Harrenstein; Michael Wooldridge

doi:10.5555/3545946.3598878

k-Prize Weighted Voting Games

Wei-Chen Lee
, David Hyland
, Alessandro Abate
, Edith Elkind
, Jiarui Gan
, Julian Gutierrez
, Paul Harrenstein
, Michael Wooldridge

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

We introduce a natural variant of weighted voting games, which we refer to as k-Prize Weighted Voting Games. Such games consist of n players with weights, and k prizes, of possibly differing values. The players form coalitions, and the i-th largest coalition (by the sum of weights of its members) wins the i-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.

Original language	English
Title of host publication	Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems
Editors	Alessandro Ricci, William Yeoh
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	2049-2057
Number of pages	9
ISBN (Electronic)	9781450394321
DOIs	https://doi.org/10.5555/3545946.3598878
Publication status	Published - 2023
Event	International Conference on Autonomous Agents and Multiagent Systems 2023 - London, United Kingdom Duration: 29 May 2023 → 2 Jun 2023 Conference number: 22nd https://dl.acm.org/doi/proceedings/10.5555/3545946 (Proceedings) https://aamas2023.soton.ac.uk/ (Website)

Conference

Conference	International Conference on Autonomous Agents and Multiagent Systems 2023
Abbreviated title	AAMAS 2023
Country/Territory	United Kingdom
City	London
Period	29/05/23 → 2/06/23
Internet address	https://dl.acm.org/doi/proceedings/10.5555/3545946 (Proceedings) https://aamas2023.soton.ac.uk/ (Website)

Keywords

Coalition formation
Cooperative game theory
Cooperative games with externalities
Core
Efficiency
Partition function form
Stability
Weighted Voting Game

Access to Document

10.5555/3545946.3598878

Cite this

@inproceedings{52c4a031a3ce450a901f778279d4c903,

title = "k-Prize Weighted Voting Games",

abstract = "We introduce a natural variant of weighted voting games, which we refer to as k-Prize Weighted Voting Games. Such games consist of n players with weights, and k prizes, of possibly differing values. The players form coalitions, and the i-th largest coalition (by the sum of weights of its members) wins the i-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.",

keywords = "Coalition formation, Cooperative game theory, Cooperative games with externalities, Core, Efficiency, Partition function form, Stability, Weighted Voting Game",

author = "Wei-Chen Lee and David Hyland and Alessandro Abate and Edith Elkind and Jiarui Gan and Julian Gutierrez and Paul Harrenstein and Michael Wooldridge",

note = "Funding Information: Lee was supported by the Oxford-Taiwan Graduate Scholarship and the Oxford-DeepMind Graduate Scholarship. Wooldridge and Har-renstein were supported by the UKRI under a Turing AI World Leading Researcher Fellowship (EP/W002949/1) awarded to Wooldridge. Publisher Copyright: {\textcopyright} 2023 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.; International Conference on Autonomous Agents and Multiagent Systems 2023, AAMAS 2023 ; Conference date: 29-05-2023 Through 02-06-2023",

year = "2023",

doi = "10.5555/3545946.3598878",

language = "English",

pages = "2049--2057",

editor = "Alessandro Ricci and William Yeoh",

booktitle = "Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

url = "https://dl.acm.org/doi/proceedings/10.5555/3545946, https://aamas2023.soton.ac.uk/",

}

Lee, W-C, Hyland, D, Abate, A, Elkind, E, Gan, J, Gutierrez, J, Harrenstein, P & Wooldridge, M 2023, k-Prize Weighted Voting Games. in A Ricci & W Yeoh (eds), Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. Association for Computing Machinery (ACM), New York NY USA, pp. 2049-2057, International Conference on Autonomous Agents and Multiagent Systems 2023, London, United Kingdom, 29/05/23. https://doi.org/10.5555/3545946.3598878

k-Prize Weighted Voting Games. / Lee, Wei-Chen; Hyland, David; Abate, Alessandro et al.
Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. ed. / Alessandro Ricci; William Yeoh. New York NY USA: Association for Computing Machinery (ACM), 2023. p. 2049-2057.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - k-Prize Weighted Voting Games

AU - Lee, Wei-Chen

AU - Hyland, David

AU - Abate, Alessandro

AU - Elkind, Edith

AU - Gan, Jiarui

AU - Gutierrez, Julian

AU - Harrenstein, Paul

AU - Wooldridge, Michael

N1 - Conference code: 22nd

PY - 2023

Y1 - 2023

N2 - We introduce a natural variant of weighted voting games, which we refer to as k-Prize Weighted Voting Games. Such games consist of n players with weights, and k prizes, of possibly differing values. The players form coalitions, and the i-th largest coalition (by the sum of weights of its members) wins the i-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.

AB - We introduce a natural variant of weighted voting games, which we refer to as k-Prize Weighted Voting Games. Such games consist of n players with weights, and k prizes, of possibly differing values. The players form coalitions, and the i-th largest coalition (by the sum of weights of its members) wins the i-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.

KW - Coalition formation

KW - Cooperative game theory

KW - Cooperative games with externalities

KW - Core

KW - Efficiency

KW - Partition function form

KW - Stability

KW - Weighted Voting Game

UR - https://www.scopus.com/pages/publications/85171284812

U2 - 10.5555/3545946.3598878

DO - 10.5555/3545946.3598878

M3 - Conference Paper

AN - SCOPUS:85171284812

SP - 2049

EP - 2057

BT - Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

A2 - Ricci, Alessandro

A2 - Yeoh, William

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

T2 - International Conference on Autonomous Agents and Multiagent Systems 2023

Y2 - 29 May 2023 through 2 June 2023

ER -

k-Prize Weighted Voting Games

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this