We study the subgame perfect equilibria of two-player stochastic  games with perfect monitoring for a fixed discount factor. We develop a novel algorithm that, starting from larger  correspondences, spirals inwards towards the state-dependent equilibrium payoff correspondence. At each iteration, starting from  a vector of pivot points that are on the boundaries of each state's candidate equilibrium payoff set, we shave off part of each state's  set of payoffs in a carefully chosen direction. The pivots are then advanced in this direction.

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. Cover (1965) gave the optimal algorithm that minimizes worst-case regret for the case of 2 experts. In this talk, I will describe the optimal algorithm, adversary and regret for the case of 3 experts. We will see that optimal algorithm for 2 and 3 experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary.

An evidence game is a strategic disclosure game in which an agent who has different pieces of verifiable evidence decides which ones to disclose and which ones to conceal, and a principal chooses an action (a "reward"). The agent's preference is the same regardless of his information (his "type")—he always prefers the reward to be as high as possible—whereas the principal prefers the reward to fit the agent's type.

We analyze a model of voluntary information disclosure and acquisition. An agent chooses among different certification options, may privately obtain verifiable results, and decides whether to disclose them before selling an asset. We show that equilibria are informationally inefficient and that agents choose certifications that are too easy to pass. Self-regulation or a monopolist certifier do not help resolve the inefficiency.

We consider a setting where in a future known time, a certain continuous variable will be realized.There is a public prediction that converges to its value, and an expert has access to a more accurate prediction.Our goal is to study when should the expert reveal his information, assuming that his reward is based on a logarithmic market scoring rule (i.e., his reward is proportional to the gain in log likelihood of the realized value).Our contributions are: (1) we show that the optimal expert policy is threshold based.

As economic systems "move" to the Internet, they can become much more complex and this new complexity often becomes their defining characteristic.  We will consider a very simple scenario of this form: a single seller that is selling multiple items to a single buyer.  We will discuss the question of how  *complex* must the pricing scheme be in order for the seller to maximize (approximately, at least) his revenue.Based on joint works with Sergiu Hart, with Shaddin Duhgmi and Li Han and with Moshe Babioff and Yannai Gonczarowski. 

Decentralized markets are often characterized as opaque and prone to trade delays, leading to the perception that they are less efficient  than standard centralized limit order markets. We show that in the presence of information  asymmetries decentralized markets can promote higher trade efficiency  than centralized limit order markets through at least two channels.

he talk will attempt to characterize good strategies for some special cases of stochastic games. For instance, the talk will argue that there might always be a good strategy with a certain property for all games in a special case of stochastic games or that no good strategy exists that have some property for some game.

We study a multi-dimensional collective decision under incomplete information. With votes taken by simple majority in each dimension, the outcome is the coordinate-wise median. But, judicious rotations of the orthogonal axes - the dimensions, or issues that are voted upon - lead to welfare improvements. Such rotations cover the entire set of anonymous, Pareto efficient and dominant strategy incentive compatible mechanisms in our environment (Kim and Rousch (1984) and Peters et. al (1992)).

We extend Kreps and Wilson's 1982 definition of sequential equilibrium to multi-stage games with infinite sets of signals and actions. We define “broad sequential epsilon-equilibria” by properties of “sequential epsilon-rationality” and “broad consistency.” Given beliefs, a player's strategy is sequentially epsilon-rational if, at every date t, at every possible signal outside a uniformly unlikely set, the player cannot expect to gain more than epsilon by any feasible deviation.

We consider a decision maker with recursive utility, as formalized by Epstein and Zin (1989). We show that, as this decision maker  becomes more patient, his ranking of conditionally i.i.d. processes is approximately that of an expected utility decision maker.

We consider two-player repeated games, where the players observe their own payoffs with a positive probability. Typically, a player observes neither the other's actions nor her payoff.  We show that knowing her own payoff is sufficient to obtain any strictly efficient payoff  by sequential equilibrium, when costly communication is available and the players are  sufficiently patient.

For a constant ε>0, we prove a poly(N) lower bound on the (randomized) communication complexity of ε-Nash equilibrium in two-player N×N games.For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ε,ε)-weak approximateNash equilibrium, which is a profile of mixed actions such that at least (1-ε)-fraction of the players are ε-best replying.