Bounds on the Cost of Stabilizing a Cooperative Game
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 2069
- Type
- D - Journal article
- DOI
-
10.1613/jair.1.11270
- Title of journal
- Journal of Artificial Intelligence Research
- Article number
- -
- First page
- 87
- Volume
- 63
- Issue
- -
- ISSN
- 1076-9757
- Open access status
- Compliant
- Month of publication
- December
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
7
- Research group(s)
-
-
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper introduces the notion of cost of stability: the minimum subsidy needed to stabilise a cooperative game, so that no group of players wants to deviate. It proves bounds on the cost of stability for several classes of games, relates it to other measures of (in)stability, and analyses the complexity of computing the cost of stability in weighted voting games. After the conference version appeared, other researchers adopted the concept, proving bounds on cost of stability for further game classes (AAMAS�11, https://dl.acm.org/doi/10.5555/2034396.2034448; AAMAS�14, https://dl.acm.org/doi/10.5555/2615731.2615827; SAGT�18, https://doi.org/10.1007/978-3-319-99660-8_21). The concept is covered in an undergraduate textbook, �Economics and Computation� (https://link.springer.com/book/10.1007%2F978-3-662-47904-9).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -