{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:53:56Z","timestamp":1787320436973,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>While the minimax (or maximin) strategy has become the standard and most agreed-upon 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.<\/jats:p>","DOI":"10.1137\/110858021","type":"journal-article","created":{"date-parts":[[2013,2,12]],"date-time":"2013-02-12T10:35:19Z","timestamp":1360665319000},"page":"363-385","source":"Crossref","is-referenced-by-count":10,"title":["Adversarial Leakage in Games"],"prefix":"10.1137","volume":"27","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Emek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Tennenholtz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,2,12]]},"reference":[{"key":"atypb1","first-page":"1749","author":"Alon N.","year":"1995","journal-title":"Amsterdam"},{"key":"atypb2","first-page":"544","author":"Alon N.","year":"1990","journal-title":"MO, IEEE"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.003"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"<scp>N. Alon and J.H. Spencer<\/scp><i>The Probabilistic Method<\/i> 3rd ed., John Wiley, New York, 2008.","DOI":"10.1002\/9780470277331"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.2307\/1911661"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.5.54"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"<scp>M. Budinich and L. Fortnow<\/scp><i>Repeated matching pennies with limited randomness<\/i> in Proceedings of the 12th ACM Conference on Electronic Commerce, 2011, pp. 111-118.","DOI":"10.1145\/1993574.1993592"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"<scp>S. Dziembowski and K. Pietrzak<\/scp><i>Leakage-resilient cryptography<\/i> in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, 2008, pp. 293-302.","DOI":"10.1109\/FOCS.2008.56"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.09.006"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1998549.1998551"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"atypb12","first-page":"3","author":"Lov\u00e1sz L.","year":"1973","journal-title":"Canada"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"atypb14","unstructured":"<scp>A. Matsui<\/scp><i>Information Leakage Forces Cooperation<\/i> Discussion paper, Northwestern University, 1988."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"<scp>J. Naor and M. Naor<\/scp><i>Small-bias probability spaces: Efficient constructions and applications<\/i> in Proceedings of the 22nd Annual ACM STOC, ACM Press, 1990, pp. 213-223.","DOI":"10.1145\/100216.100244"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"<scp>H. Nasheri<\/scp><i>Economic Espionage and Industrial Spying<\/i> Cambridge University Press, Cambridge, UK, 2005.","DOI":"10.1017\/CBO9780511610288"},{"key":"atypb17","unstructured":"<scp>J.S. Provan<\/scp><i>The Use of Spies in Strategic Situations: Preliminary Report<\/i> UNC\/STOR\/ 07\/01, University of North Carolina at Chapel Hill, NC, 2008."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(86)90021-9"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00177-5"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1065"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.2307\/1884852"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2004.02.002"},{"key":"atypb24","unstructured":"<scp>J. von Neumann and O. Morgenstern<\/scp><i>Theory of Games and Economic Behavior<\/i> Princeton University Press, Princeton, NJ, 1944."},{"key":"atypb25","unstructured":"<scp>A. Weil<\/scp><i>Sur les courbes algebriques et les varietes qui s'en deduisent<\/i> Actualit\u00e9s Sci. Indust. 1041, Herman, Paris, 1948."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110858021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:56:53Z","timestamp":1787317013000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110858021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110858021"],"URL":"https:\/\/doi.org\/10.1137\/110858021","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}