Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

11.04.2016 | Ausgabe 2/2017

Theory of Computing Systems 2/2017

Path-Disruption Games: Bribery and a Probabilistic Model

Zeitschrift:
Theory of Computing Systems > Ausgabe 2/2017
Autoren:
Anja Rey, Jörg Rothe, Adrian Marple
Wichtige Hinweise
Preliminary versions of parts of this paper appear in the proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT’11) [47], the 20th European Conference on Artificial Intelligence (ECAI’12) and the 6th European Starting AI Researcher Symposium (STAIRS’12) [48], and the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’14) [36].

Abstract

Path-disruption games, recently introduced by Bachrach and Porat, are coalitional games played on graphs where one or multiple adversaries each seeks to reach a given target vertex from a given source vertex, while a coalition of agents seeks to prevent that from happening by blocking every path from the source to the target for each adversary. These coalitional games model, for instance, security issues in computer networks. Inspired by bribery in voting, we introduce the notion of bribery for path-disruption games. We analyze the question of how hard it is to decide whether the adversaries can bribe some of the agents such that no coalition will form that blocks all paths for them. We show that this problem is NP-complete for a single adversary and complete for \({\Sigma }^{\mathrm {P}}_{2} = \text {NP}^{\text {NP}}\), the second level of the polynomial hierarchy, for the case of multiple adversaries. We also expand the model by allowing uncertainty about the targets: In probabilistic path-disruption games, we assign to each vertex the probability that an adversary wants to reach it, and we study the complexity of problems related to common solution concepts (such as the core and the ε-core) and other properties of such games.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2017

Theory of Computing Systems 2/2017 Zur Ausgabe

Premium Partner

    Bildnachweise