Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2016 | OriginalPaper | Buchkapitel

Computing Equilibria with Partial Commitment

verfasst von : Vincent Conitzer

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In security games, the solution concept commonly used is that of a Stackelberg equilibrium where the defender gets to commit to a mixed strategy. The motivation for this is that the attacker can repeatedly observe the defender’s actions and learn her distribution over actions, before acting himself. If the actions were not observable, Nash (or perhaps correlated) equilibrium would arguably be a more natural solution concept. But what if some, but not all, aspects of the defender’s actions are observable? In this paper, we introduce solution concepts corresponding to this case, both with and without correlation. We study their basic properties, whether these solutions can be efficiently computed, and the impact of additional observability on the utility obtained.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel Distributed Methods for Computing Approximate Equilibria
Fußnoten
1
As is commonly assumed in this model, ties for the column player are broken in the row player’s favor; if not, the row player can simply commit to \(1/2-\epsilon \) on a and \(1/2+\epsilon \) on b.
 
2
It is easy to get confused here—does the column player not learn more in a round purely by virtue of his own payoff from that round? It is important to remember that we are not considering repeated play by the column player. The idea is that the column player can observe over time the signals and how the row player acts before the column player ever acts. For discussion of security contexts in which certain types of players can receive messages that are inaccessible to other types, see Xu et al. [24].
 
3
This was verified to be optimal using the linear program in Fig. 1; same for the next case.
 
Literatur
1.
An, B., Kempe, D., Kiekintveld, C., Shieh, E., Singh, S.P., Tambe, M., Vorobeychik, Y.: Security games with limited surveillance. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), Toronto, ON, Canada (2012)
2.
An, B., Shieh, E., Tambe, M., Yang, R., Baldwin, C., DiRenzo, J., Maule, B., Meyer, G.: PROTECT - a deployed game theoretic system for strategic security allocation for the United States Coast Guard. AI Mag. 33(4), 96–110 (2012)
3.
Ashlagi, I., Monderer, D., Tennenholtz, M.: On the value of correlation. J. Artif. Intell. Res. 33, 575–613 (2008)MathSciNetMATH
4.
5.
Balcan, M.F., Blum, A., Haghtalab, N., Procaccia, A.D.: Commitment without regrets: online learning in Stackelberg security games. In: Proceedings of the ACM Conference on Economics and Computation (EC), Portland, OR, USA, pp. 61–78 (2015)
6.
7.
Conitzer, V., Korzhyk, D.: Commitment to correlated strategies. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), San Francisco, CA, USA, pp. 632–637 (2011)
8.
Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: Proceedings of the ACM Conference on Electronic Commerce (EC), Ann Arbor, MI, USA, pp. 82–90 (2006)
9.
10.
Daskalakis, C., Goldberg, P., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009)MathSciNetCrossRefMATH
11.
Fang, F., Nguyen, T.H., Pickles, R., Lam, W.Y., Clements, G.R., An, B., Singh, A., Tambe, M., Lemieux, A.: Deploying PAWS: field optimization of the protection assistant for wildlife security. In: Proceedings of the Twenty-Eighth Innovative Applications of Artificial Intelligence Conference (IAAI), Phoenix, AZ, USA (2016)
12.
Fudenberg, D., Levine, D.: The Theory of Learning in Games. MIT Press, Cambridge (1998)MATH
13.
14.
Korzhyk, D., Conitzer, V., Parr, R.: Solving Stackelberg games with uncertain observability. In: Proceedings of the Tenth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Taipei, Taiwan, pp. 1013–1020 (2011)
15.
Korzhyk, D., Yin, Z., Kiekintveld, C., Conitzer, V., Tambe, M.: Stackelberg vs. nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness. J. Artif. Intell. Res. 41(2), 297–327 (2011)MathSciNetMATH
16.
Letchford, J., Conitzer, V., Munagala, K.: Learning and approximating the optimal strategy to commit to. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 250–262. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04645-2_​23 CrossRef
17.
Letchford, J., Korzhyk, D., Conitzer, V.: On the value of commitment. Auton. Agent. Multi-Agent Syst. 28(6), 986–1016 (2014)CrossRef
18.
Letchford, J., MacDermed, L., Conitzer, V., Parr, R., Isbell, C.: Computing optimal strategies to commit to in stochastic games. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), Toronto, ON, Canada, pp. 1380–1386 (2012)
19.
Pita, J., Jain, M., Ordóñez, F., Tambe, M., Kraus, S.: Robust solutions to Stackelberg games: addressing bounded rationality and limited observations in human cognition. Artif. Intell. 174(15), 1142–1171 (2010)MathSciNetCrossRefMATH
20.
Pita, J., Jain, M., Western, C., Portway, C., Tambe, M., Ordóñez, F., Kraus, S., Parachuri, P.: Deployed ARMOR protection: the application of a game-theoretic model for security at the Los Angeles International Airport. In: Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Estoril, Portugal, pp. 125–132 (2008)
21.
Sandholm, T.: The state of solving large incomplete-information games, and application to poker. AI Mag. 31(4), 13–32 (2010). Special Issue on Algorithmic Game Theory
22.
Tsai, J., Rathi, S., Kiekintveld, C., Ordóñez, F., Tambe, M.: IRIS - a tool for strategic security allocation in transportation networks. In: Proceedings of the Eighth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Budapest, Hungary, pp. 37–44 (2009)
23.
24.
Xu, H., Freeman, R., Conitzer, V., Dughmi, S., Tambe, M.: Signaling in Bayesian Stackelberg games. In: Proceedings of the Fifteenth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Singapore, pp. 150–158 (2016)
25.
Yin, Z., Jiang, A.X., Tambe, M., Kiekintveld, C., Leyton-Brown, K., Sandholm, T., Sullivan, J.P.: TRUSTS: scheduling randomized patrols for fare inspection in transit systems using game theory. AI Mag. 33(4), 59–72 (2012)
Metadaten
Titel
Computing Equilibria with Partial Commitment
verfasst von
Vincent Conitzer
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Web and Internet Economics

Print ISBN: 978-3-662-54109-8

Electronic ISBN: 978-3-662-54110-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-54110-4_1

Premium Partner

    Bildnachweise