Sergiu Hart

STOC Conference 2007 Conference Paper

The communication complexity of uncoupled nash equilibrium procedures

• Sergiu Hart
• Yishay Mansour

We study the question of how long it takes players to reach a Nashequilibrium in uncoupled setups, where each player initially knowsonly his own payoff function. We derive lower bounds on the communication complexity of reaching a Nash equilibrium, i.e., on thenumber of bits that need to be transmitted, and thus also on the requirednumber of steps. Specifically, we show lower bounds that are exponential inthe number of players in each one of the following cases: (1) reaching apure Nash equilibrium; (2) reaching a pure Nash equilibrium in a Bayesiansetting; and (3) reaching a mixed Nash equilibrium. We then show that, incontrast, the communication complexity of reaching a correlated equilibriumis polynomial in the number of players.

TARK Conference 2005 Invited Paper

Stochastic uncoupled dynamics and nash equilibrium: extended abstract

• Sergiu Hart
• Andreu Mas-Colell

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence to Nash equilibria, and present a number of possibility and impossibility results. Basically, we show that if in addition to random moves some recall is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it suffices to recall the last two periods of play. Journal of Economic Literature Classification Numbers: C7, D83.

TARK Conference 1996 Conference Paper

The Absent-Minded Driver

• Robert J. Aumann
• Sergiu Hart
• Motty Perry

FOCS Conference 1984 Conference Paper

Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme

• Sergiu Hart
• Micha Sharir

Davenport-Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport-Schinzel sequence composed of n symbols is (n /spl alpha/(n)), where /spl alpha/ (n) is the functional inverse of Ackermann's function, and is thus very slow growing. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes.

STOC Conference 1984 Conference Paper

Probabilistic Temporal Logics for Finite and Bounded Models

• Sergiu Hart
• Micha Sharir

We present two (closely-related) propositional probabilistic temporal logics based on temporal logics of branching time as introduced by Ben-Ari, Pnueli and Manna and by Clarke and Emerson. The first logic, PTL f , is interpreted over finite models, while the second logic, PTL b , which is an extension of the first one, is interpreted over infinite models with transition probabilities bounded away from 0. The logic PTL f allows us to reason about finite-state sequential probabilistic programs, and the logic PTL b allows us to reason about (finite-state) concurrent probabilistic programs, without any explicit reference to the actual values of their state-transition probabilities. A generalization of the tableau method yields exponential-time decision procedures for our logics, and complete axiomatizations of them are given. Several meta-results, including the absence of a finite-model property for PTL b , and the connection between satisfiable formulae of PTL b and finite state concurrent probabilistic programs, are also discussed.