<div class="csl-bib-body">
<div class="csl-entry">Chen, J., Layegh Khavidaki, S. N., Haydn, S. V., Simola, S., & Sorge, M. (2023). Game Implementation: What Are the Obstructions? In <i>Proceedings of the 37th AAAI Conference on Artificial Intelligence</i> (pp. 5557–5564). AAAI Press. https://doi.org/10.34726/5365</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/192186
-
dc.identifier.uri
https://doi.org/10.34726/5365
-
dc.description.abstract
In many applications, we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called GAME IMPLEMENTATION: Given a game in standard form and a set of desired strategies, can we design a set of payment promises such that if the players take the payment promises into account, then all undominated strategies are desired? Furthermore, we aim to minimize the cost, that is, the worst-case amount of payments.
We study the tractability of computing such payment promises and determine more closely what obstructions we may have to overcome in doing so. We show that GAME IMPLEMENTATION is NP-hard even for two players, solving in particular a long-standing open question and suggesting more restrictions are necessary to obtain tractability results. We thus study the regime in which players have only a small constant number of strategies and obtain the following. First, this case remains NP-hard even if each player's utility depends only on three others. Second, we repair a flawed efficient algorithm for the case of both small number of strategies and small number of players. Among further results, we characterize sets of desired strategies that can be implemented at zero cost as a generalization of Nash equilibria.
en
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
GAME IMPLEMENTATION
en
dc.subject
Social Choice
en
dc.subject
Graph Drawing
en
dc.subject
Game Theory
en
dc.subject
Mechanism Design
en
dc.subject
Applications
en
dc.title
Game Implementation: What Are the Obstructions?
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.identifier.doi
10.34726/5365
-
dc.relation.isbn
978-1-57735-880-0
-
dc.relation.issn
2159-5399
-
dc.description.startpage
5557
-
dc.description.endpage
5564
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
2374-3468
-
tuw.booktitle
Proceedings of the 37th AAAI Conference on Artificial Intelligence
-
tuw.container.volume
37(5)
-
tuw.peerreviewed
true
-
tuw.relation.publisher
AAAI Press
-
tuw.relation.publisherplace
Washington DC
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1609/aaai.v37i5.25690
-
dc.identifier.libraryid
AC17207635
-
dc.description.numberOfPages
8
-
tuw.author.orcid
0000-0002-8163-1327
-
tuw.author.orcid
0000-0003-1440-1019
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.event.name
The 37th AAAI Conference on Artificial Intelligence (AAAI -23)
en
tuw.event.startdate
07-02-2023
-
tuw.event.enddate
14-02-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Washington DC
-
tuw.event.country
US
-
tuw.event.presenter
Chen, Jiehua
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.grantfulltext
open
-
item.openairetype
conference paper
-
item.fulltext
with Fulltext
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity