Yishay Mansour
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yishay Mansour has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
- Michael Kearns
AT&T Bell Laboratories
2 shared publications Satinder Singh
2 shared publications- Alexander Kesselman
School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
1 shared publication - Baruch Awerbuch
MIT Laboratory for Computer Science, Johns Hopkins University, Baltimore, MD 21218, U.S.A.
1 shared publication - Baruch Schieber
IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA.. US
1 shared publication - Boaz Patt-Shamir
Tel Aviv University, Tel Aviv, Israel
1 shared publication
Latest Publications
- Open Access
Nash Convergence of Gradient Dynamics in Iterated General-Sum Games
Multi-agent games are becoming an increasing prevalent formalism for the study of electronic commerce and auctions. The speed at which transactions can take place and the growing complexity of electronic marketplaces makes the study of computationally simple agents an appealing direction. In this work, we analyze the behavior of agents that incrementally adapt their strategy through gradient ascent on expected payoff, in the simple setting of two-player, two-action, iterated general-sum games, and present a surprising result. We show that either the agents will converge to Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium.
Open AccessNash Convergence of Gradient Dynamics in Iterated General-Sum Games
Multi-agent games are becoming an increasing prevalent formalism for the study of electronic commerce and auctions. The speed at which transactions can take place and the growing complexity of electronic marketplaces makes the study of computationally simple agents an appealing direction. In this work, we analyze the behavior of agents that incrementally adapt their strategy through gradient ascent on expected payoff, in the simple setting of two-player, two-action, iterated general-sum games, and present a surprising result. We show that either the agents will converge to Nash equilibrium, or if the strategies themselves do not converge, then their average payoffs will nevertheless converge to the payoffs of a Nash equilibrium.
- Open Access
Fast Planning in Stochastic Games
Stochastic games generalize Markov decision processes (MDPs) to a multiagent setting by allowing the state transitions to depend jointly on all player actions, and having rewards determined by multiplayer matrix games at each state. We consider the problem of computing Nash equilibria in stochastic games, the analogue of planning in MDPs. We begin by providing a generalization of finite-horizon value iteration that computes a Nash strategy for each player in generalsum stochastic games. The algorithm takes an arbitrary Nash selection function as input, which allows the translation of local choices between multiple Nash equilibria into the selection of a single global Nash equilibrium. Our main technical result is an algorithm for computing near-Nash equilibria in large or infinite state spaces. This algorithm builds on our finite-horizon value iteration algorithm, and adapts the sparse sampling methods of Kearns, Mansour and Ng (1999) to stochastic games. We conclude by descrbing a counterexample showing that infinite-horizon discounted value iteration, which was shown by shaplely to converge in the zero-sum case (a result we give extend slightly here), does not converge in the general-sum case.
Open AccessFast Planning in Stochastic Games
Stochastic games generalize Markov decision processes (MDPs) to a multiagent setting by allowing the state transitions to depend jointly on all player actions, and having rewards determined by multiplayer matrix games at each state. We consider the problem of computing Nash equilibria in stochastic games, the analogue of planning in MDPs. We begin by providing a generalization of finite-horizon value iteration that computes a Nash strategy for each player in generalsum stochastic games. The algorithm takes an arbitrary Nash selection function as input, which allows the translation of local choices between multiple Nash equilibria into the selection of a single global Nash equilibrium. Our main technical result is an algorithm for computing near-Nash equilibria in large or infinite state spaces. This algorithm builds on our finite-horizon value iteration algorithm, and adapts the sparse sampling methods of Kearns, Mansour and Ng (1999) to stochastic games. We conclude by descrbing a counterexample showing that infinite-horizon discounted value iteration, which was shown by shaplely to converge in the zero-sum case (a result we give extend slightly here), does not converge in the general-sum case.
- 1 February 2004
- Published by Springer Nature in Distributed Computing
- Vol. 17 (1) , 77-89
Optimal smoothing schedules for real-time streams
- 1 February 2004
- Published by Springer Nature in Distributed Computing
- Vol. 17 (1) , 77-89
Optimal smoothing schedules for real-time streams
- 31 January 2003
- Published by Elsevier in Journal of Algorithms
- Vol. 46 (1) , 79-95
Loss-bounded analysis for differentiated services
- 31 January 2003
- Published by Elsevier in Journal of Algorithms
- Vol. 46 (1) , 79-95
Loss-bounded analysis for differentiated services
- Open Access
On Propagating Updates in a Byzantine Environment
We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than $t$ replicas fail, and that each update is initially received by at least $t$ correct replicas. The goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. To achieve reliable diffusion, each correct replica accepts an update only after receiving it from at least $t$ others. We provide the first analysis of epidemic-style protocols for such environments. This analysis is fundamentally different from known analyses for the benign case due to our treatment of fully Byzantine failures---which, among other things, precludes the use of digital signatures for authenticating forwarded updates. We propose two epidemic-style diffusion algorithms and two measures that characterize the efficiency of diffusion algorithms in general. We characterize both of our algorithms according to these measures, and also prove lower bounds with regards to these measures that show that our algorithms are close to optimal.Open AccessOn Propagating Updates in a Byzantine Environment
We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than $t$ replicas fail, and that each update is initially received by at least $t$ correct replicas. The goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. To achieve reliable diffusion, each correct replica accepts an update only after receiving it from at least $t$ others. We provide the first analysis of epidemic-style protocols for such environments. This analysis is fundamentally different from known analyses for the benign case due to our treatment of fully Byzantine failures---which, among other things, precludes the use of digital signatures for authenticating forwarded updates. We propose two epidemic-style diffusion algorithms and two measures that characterize the efficiency of diffusion algorithms in general. We characterize both of our algorithms according to these measures, and also prove lower bounds with regards to these measures that show that our algorithms are close to optimal. - 28 August 1997
- Published by Elsevier in Information Processing Letters
- Vol. 63 (4) , 211-213
A tight bound for approximating the square root
- 28 August 1997
- Published by Elsevier in Information Processing Letters
- Vol. 63 (4) , 211-213
A tight bound for approximating the square root
- 1 March 1997
- Published by Springer Nature in Combinatorica
- Vol. 17 (1) , 91-107
On construction ofk-wise independent random variables
- 1 March 1997
- Published by Springer Nature in Combinatorica
- Vol. 17 (1) , 91-107
On construction ofk-wise independent random variables
- 1 January 1994
- Published by Springer Nature
- p. 391-424
Learning Boolean Functions via the Fourier Transform
- 1 January 1994
- Published by Springer Nature
- p. 391-424
Learning Boolean Functions via the Fourier Transform