Adversarial leakage in games

Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

While the minimax (or maximin) strategy has become the standard and most agreedupon solution for decision making in adversarial settings, as discussed in game theory, computer science, and other disciplines, its power arises from the use of mixed strategies, also known as probabilistic algorithms. Nevertheless, in adversarial settings we face the risk of information leakage about the actual strategy instantiation. Hence, real robust algorithms should take information leakage into account. In this paper we introduce the notion of adversarial leakage in games, namely, the ability of a player to learn the value of b binary predicates about the strategy instantiation of her opponent. Different leakage models are suggested and tight bounds on the effect of adversarial leakage as a function of the level of leakage (captured by b) are established. The complexity of computing optimal strategies under these adversarial leakage models is also addressed. Together, our study introduces a new framework for robust decision making and provides rigorous fundamental understanding of its properties.

Original languageEnglish (US)
Pages (from-to)363-385
Number of pages23
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number1
DOIs
StatePublished - May 6 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Adversarial information leakage
  • Two-player zero-sum games

Fingerprint Dive into the research topics of 'Adversarial leakage in games'. Together they form a unique fingerprint.

Cite this