Computational aspects of shapley's saddles

Felix Brandt, Markus Brill, Felix Fischer, Paul Harrenstein

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

7 Zitate (Scopus)

Abstract

Game-theoretic solution concepts, such as Nash equilibrium, are playing an ever increasing role in the study of systems of autonomous computational agents. A common criticism of Nash equilibrium is that its existence relies on the possibility of randomizing over actions, which in many cases is deemed unsuitable, impractical, or even infeasible. In work dating back to the early 1950s Lloyd Shapley proposed ordinal set- valued solution concepts for zero-sum games that he refers to as strict and weak saddles. These concepts are intuitively appealing, they always exist, and are unique in important subclasses of games. We initiate the study of computational aspects of Shapley's saddles and provide polynomial-time algorithms for computing strict saddles in normal-form games and weak saddles in a subclass of symmetric zero-sum games. On the other hand, we show that certain problems associated with weak saddles in bimatrix games are NP-hard. Finally, we extend our results to mixed refinements of Shapley's saddles introduced by Duggan and Le Breton. Categories and Subject Descriptors F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; 1.2.11 [Distributed Artificial Intelligence]: Multiagent Sys-tems; J.4 [Computer Applications]: Social and Behavioral Sciences- Economics General Terms Theory, Algorithms, Economics.

OriginalspracheEnglisch
Titel8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009
Herausgeber (Verlag)International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Seiten181-188
Seitenumfang8
ISBN (Print)9781615673346
PublikationsstatusVeröffentlicht - 2009
Extern publiziertJa
Veranstaltung8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009 - Budapest, Ungarn
Dauer: 10 Mai 200915 Mai 2009

Publikationsreihe

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Band1
ISSN (Print)1548-8403
ISSN (elektronisch)1558-2914

Konferenz

Konferenz8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009
Land/GebietUngarn
OrtBudapest
Zeitraum10/05/0915/05/09

Fingerprint

Untersuchen Sie die Forschungsthemen von „Computational aspects of shapley's saddles“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren