Disarmament games with resources

Published

Conference Paper

Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. A paper by Deng and Conitzer in AAAI'17 introduces disarmament games, in which players alternatingly commit not to play certain pure strategies. However, in practice disarmament usually does not consist in removing a strategy, but rather in removing a resource (and doing so rules out all the strategies in which that resource is used simultaneously). In this paper, we introduce a model of disarmament games in which resources, rather than strategies, are removed. We prove NP-completeness of several formulations of the problem of achieving desirable outcomes via disarmament. We then study the case where resources can be fractionally removed, and prove a result analogous to the folk theorem that all desirable outcomes can be achieved. We show that we can approximately achieve any desirable outcome in a polynomial number of rounds, though determining whether a given outcome can be obtained in a given number of rounds remains NP-complete.

Duke Authors

Cited Authors

  • Deng, Y; Conitzer, V

Published Date

  • January 1, 2018

Published In

  • 32nd Aaai Conference on Artificial Intelligence, Aaai 2018

Start / End Page

  • 981 - 988

International Standard Book Number 13 (ISBN-13)

  • 9781577358008

Citation Source

  • Scopus