Abstract: We consider a dynamical model of influence with a set of non-strategic agents and two strategic agents. The non-strategic agents are organized in a network along which they communicate . The strategic agents have two opposite opinions 0 and 1. At each stage, the opinion of the non-strategic agents changes depending on the opinion of their neighbors at the previous stage and of the strategic agents if they are under their influence. We study this model with the tools of stochastic games and prove the existence of the uniform value.

The schedule for 2015 - 2016 was:

(October-27 2015) Eilon Solan.

(November-3 2015) Yaron Azrieli.

(November-10 2015) David Lagziel.

(November-17 2015) Gaetan Fournier.

(November-24 2015) Igal Milchtaich.

(December-8 2015) Moshe Tennenholtz.

(December-15 2015) Ron Holzman.

(December-22 2015) Rann Smorodinsky.

(December-29 2015) Omer Tamuz.

(January-5 2016) Shiri Alon-Eron.

(January-12 2016) Francis Bloch.

(March-1 2016) Sergiu Hart.

(March-8 2016) Ron Peretz.

(March-15 2016) Simina Brânzei.

(March-22 2016) Itai Arieli.

(March-29 2016) Yakov Babichenko.

(April-5 2016) Galit Ashkenazi-Golan.

(April-12 2016) Yaron Azrieli.

(May-10 2016) Niv Buchbinder.

(May-24 2016) Eilon Solan.

(May-31 2016) Yannai Gonczarowski.

(June-7 2016) Adam Lampert.

(June-6 2016) Adam Lampert, Arizona State University. 

Title: Dynamic game theory approaches to analyze management of ecological systems by multiple agents.

Abstract: A major threat on human well­ being is the accelerated rate of environmental degradation. Restoration of degraded ecological systems entails cooperation among multiple agents, such as land owners, agencies, and sometimes countries. These agents may have incentives to invest less and free­ride on other's investment, which may lead to inefficient treatment. In this talk, I will introduce a dynamic game approach to study how to establish a common environmental project by multiple agents, taking into account the costs of both treatment and degradation over time. As a first step, I will use optimal control to show some general principle governing dynamic investment. Next, I will introduce a dynamic game model where each agent decides how and how much to invest over time, considering some state­feedback. I will show that, under certain conditions, there exists a subgame perfect Nash equilibrium where all agents invest simultaneously, albeit slowly enough, and no agent has an incentive to reduce his/her investment. This solution that exists in the “dynamic” model is different from solutions to “static” games of public good provision. Finally, I will introduce a model with incomplete information where each agent may either suffer or not from the environmental degradation, and the agent's type is initially unknown to the other agents. I will examine different mechanisms to establish the project despite the lack of information that often reduces efficiency. I will demonstrate that if the agents adopt the simultaneous investment Nash equilibrium proposed here, the lack of information may actually increase efficiency in some cases. This study suggests that utilizing the course of time may reduce free­riding and facilitate cooperation.

(May-31 2016) Yannai Gonczarowski, Hebrew University of Jerusalem and Microsoft Research. 

Title: The Menu-Size Complexity of Revenue Approximation (with Moshe Babaioff and Noam Nisan).

Abstract: We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F1, F2, ..., Fn that possibly have unbounded support. It is well known that - unlike in the single item case - the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility to extract an arbitrarily high fraction of the optimal revenue via a finite menu size remained open.

In this paper, we give an affirmative answer to this open question, showing that for every n and for every epsilon>0, there exists a complexity bound C=C(n,epsilon) such that auctions of menu size at most C suffice for obtaining a (1-epsilon) fraction of the optimal revenue. We prove upper and lower bounds on the revenue approximation complexity C(n,epsilon).

Link: http://arxiv.org/abs/1604.06580

(May-24 2016) Eilon Solan, Tel Aviv University 

Title: Acceptable Strategy Profiles in Stochastic Games.

Abstract: In this paper we present a new solution concept for multiplayer stochastic games, namely, acceptable strategy profiles. For each player $i$ and state $s$ in a stochastic game, let $w_i(s)$ be a real number. A strategy profile is \emph{$w$-acceptable}, where $w=(w_i(s))$, if the discounted payoff to each player $i$ is at least $w_i(s)$ when the initial state is $s$, provided the discount factor of the players is sufficiently close to 1. Our goal is to provide simple strategy profiles that are $w$-acceptable for payoff vectors $w$ in which all coordinates are high.

(May-10 2016) Niv Buchbinder, Tel Aviv University 

Title: A Primal-Dual Approach to Online Optimization Problems.

Abstract: The primal-dual method is one of the fundamental design methodologies in the areas of linear programming, combinatorial optimization, and approximation algorithms. In this talk I will provide an introduction to the area of online combinatorial optimization. I will then discuss the primal-dual method as a unified framework to the design and analysis of online algorithms. Examples for which this approach is applicable include central online problems such as paging, routing, scheduling, online set cover, and graph connectivity problems. Finally, I will show some connections between online combinatorial optimization and online learning.

(April-12 2016) Yaron Azrieli, Ohio State University 

Title: Symmetric mechanism design (joint with Ritesh Jain).

Abstract: Designers of economic mechanisms often have an incentive to bias the rules of the mechanism in favor of certain groups of agents. This paper studies the extent to which a policy prohibiting biased mechanisms is effective in achieving fair outcomes. Our main result is a characterization of the class of social choice functions that can be implemented by symmetric mechanisms. When the solution concept used is Bayes-Nash equilibrium, symmetry is typically not very restrictive and discriminatory social choice functions can be implemented by symmetric mechanisms. Our characterization in this case is based on a ‘revelation principle’ type of result, where we show that a social choice function can be symmetrically implemented if and only if a particular kind of (indirect) symmetric mechanism implements it. When implementation in dominant strategies is considered, only symmetric social choice functions can be implemented by symmetric mechanisms. We illustrate our results in environments of voting with private values, voting with a common value, and assignment of indivisible goods.

link: http://yaronazrieli.weebly.com/uploads/6/5/6/8/65683525/symmetric-design-web.pdf

(April-5 2016) Galit Ashkenazi-Golan, Seminar Hakibutzim and Tel Aviv University 

Title: What You Get is What You See: Repeated Games with Observable Payoffs (joint with Ehud Lehrer).

Abstract: We consider two-player repeated where the players observe their own payoffs. We prove that any strictly efficient payoff can be obtained as sequential equilibrium payoff, when costly communication is available and the players are sufficiently patient.

(March-29 2016) Yakov Babichenko, Technion 

Title: Random Extensive form games (joint with Itai Arieli).

Abstract: We consider two-player random extensive form games where the payoff s at the leaves are independently drawn uniformly at random from a given feasible set C. We study the asymptotic distribution of the subgame perfect equilibrium outcome for binary-trees with increasing depth in various random (or deterministic) assignments of players to nodes. We characterize the assignments under which the asymptotic distribution concentrates around a point. Our analysis provides a natural way to derive from the asymptotic distribution a novel solution concept for two-player bargaining problems with a solid strategic justification.

(March-22 2016) Itai Arieli, Technion. 

Title: Private Bayesian Persuasion.

Abstract: We consider a multi-agent Bayesian persuasion problem where an informed sender tries to persuade a group of agents to adopt a certain product. The sender is allowed to commit to a signalling policy where she sends a private signal to every agent. The payoff to the sender is a function of the subset of adopters. We characterize an optimal signalling policy and the maximal revenue to the sender for three di fferent types of payo ff functions: supermodular, symmetric submodular, and a supermajority function. Moreover, using tools from cooperative game theory we provide a necessary and sufficient condition under which public signalling policy is optimal.

(March-15 2016) Simina Brânzei, The Hebrew University of Jerusalem. 

Title: Recent developments in fair division for strategic agents

Abstract: I will talk about fair division for strategic agents and will start with the cake cutting problem, which models the division of a heterogeneous divisible good among players with different preferences. Here I will talk about a dictatorship theorem, where under mild technical conditions, we show that any deterministic strategy-proof protocol for two agents in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. For n > 2 agents, a similar impossibility holds, namely there always exists an agent that gets the empty piece (i.e. no cake). In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations. I will also talk about an algorithmic framework for strategic agents, where fair outcomes can be implemented in the equilibria of protocols.

If enough time I will also mention the problem of allocating multiple divisible goods for the fairness solution concept of Nash social welfare. When the preferences are known, this solution is achieved in the Fisher market equilibrium outcomes. However, with strategic agents the strong fairness guarantees of market equilibria can be destroyed. We find that for additive valuations, the Fisher market approximates the NSW within a factor of 2, but for Leontief utilities the approximation degrades linearly with the number of players. Surprisingly, a mechanism known as Trading Post not only retains the constant 2-approximation of Fisher for additive utilities, but approximately implements the NSW objective for Leontief valuations: its price of anarchy is 1 + epsilon for every epsilon > 0.

These are joint works with several people: Peter Bro Miltersen, Ioannis Caragiannis, David Kurokawa, Ariel Procaccia, Vasilis Gkatzelis, and Ruta Mehta.

(March-8 2016) Ron Peretz, Bar Ilan University. 

Title: Limits of Correlation with Bounded Complexity (joint with Gilad Bavly).

Abstract: While Peretz (2013) showed that, perhaps surprisingly, players whose recall is bounded can correlate in a long repeated game against a player of greater recall capacity, we show that correlation is already impossible against an opponent whose recall capacity is only linearly larger. This result closes a gap in the characterisation of minmax levels, and hence also equilibrium payoffs, of repeated games with bounded recall.

(March-1 2016) Sergiu Hart, the Hebrew University of Jerusalem. 

Title: Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics.

Abstract: We propose to smooth out the calibration score, which measures how good a forecaster is, by combining nearby forecasts. While regular calibration can be guaranteed only by randomized forecasting procedures, we show that smooth calibration can be guaranteed by deterministic procedures. As a consequence, it does not matter if the forecasts are leaked, i.e., made known in advance: smooth calibration can nevertheless be guaranteed (while regular calibration cannot). Moreover, our procedure has finite recall, is stationary, and all forecasts lie on a finite grid. We also consider related problems: online linear regression, weak calibration, and uncoupled Nash dynamics in n-person games.

(January-12 2016) Francis Bloch, Universite Paris 1. 

Title: Dynamic allocation of objects to queueing agents (joint with David Cantala).

Abstract: This paper analyzes the optimal assignment of objects which arrive sequentially to agents organized in a waiting list. Applications include the assignment of social housing and organs for transplants. We analyze the optimal design of probabilistic queuing disciplines, punishment schemes, the optimal timing of applications and information releases. We consider three efficiency criteria: the vector of values of agents in the queue, the probability of misallocation and the expected waste. Under private values, we show that the first-come first-served mechanism dominates a lottery according to the first two criteria but that lottery dominates first-come first-serve according to the last criterion. Under common values, the first-come first serve mechanism dominates all other mechanisms according to the first two criteria while the lottery dominates all other mechanisms according to the last one. Punishment schemes accelerate turnover in the queue at the expense of agents currently in the waiting list, application schemes with commitment dominate sequential offers and information release always increases the value of agents at the top of the waiting list.

(January-5 2016) Shiri Alon-Eron, Bar Ilan University. 

Title: Competitive equilibrium as a bargaining solution: an axiomatic approach.

Abstract: The paper introduces an axiomatic characterization of a solution to bargaining problems. The bargaining problems addressed are specifi.ed by: (a) the preference relations of the bargaining parties (b) resources that are the subject of bargaining, and (c) a pre-speci.fied disagreement bundle for each party that would result in case bargaining fails. The approach is ordinal, meaning that the solution is independent of the specifi.c utility indices chosen to represent parties' preferences. We propose axioms that characterize a solution that matches each bargaining problem with an exchange economy whose parameters are derived from the problem, and returns the set of equilibrium allocations corresponding to one equilibrium price vector of that economy. The axioms describe a solution that is the result of an impartial arbitration process, expressing the view that arbitration is a natural method to settle disputes in which agents have conflicting interests, but can all gain from a compromise.

(December-29 2015) Omer Tamuz, CalTech. 

Title: The Speed of Social Learning (Joint with Matan Harel, Elchanan Mossel, and Philipp Strack).

Abstract: We consider Bayesian agents who learn from exogenously provided private signals, as well as the actions of the others. We show that learning from actions is slower than learning from signals, that increased interaction between agents can lower the speed of learning, and that very large groups do not learn very quickly.

(December-22 2015) Rann Smorodinsky, Technion. 

Title: Perception Games and Privacy (joint with Ronen Gradwohl).

Abstract: Players (people, firms, states, etc.) have privacy concerns that may affect their choice of actions in strategic settings. We use a variant of signaling games to model this effect and study its relation to pooling behavior, misrepresentation of information, and inefficiency. We discuss these issues and show that common intuitions may lead to inaccurate conclusions about the implications of privacy.

(December-15 2015) Ron Holzman, Technion. 

Title: Strong equilibrium in network congestion games (joint work with Dov Monderer).

Abstract: A network congestion game is played on a directed, two-terminal network. Every player chooses a route from his origin to his destination. The cost of a route is the sum of the costs of the arcs on it. The arc cost is a function of the number of players who use it. Rosenthal proved that such a game always has a Nash equilibrium in pure strategies. Here we pursue a systematic study of the classes of networks for which a strong equilibrium is guaranteed to exist, under two opposite monotonicity assumptions on the arc cost functions. Our main results are: (a) If costs are increasing, strong equilibrium is guaranteed on extension-parallel networks, regardless of whether the players' origins and destinations are the same or may differ. (b) If costs are decreasing, and the players have the same origin but possibly different destinations, strong equilibrium is guaranteed on series-parallel networks. (c) If costs are decreasing, and both origins and destinations may differ, strong equilibrium is guaranteed on multiextension-parallel networks. In each case, the network condition is not only sufficient but also necessary in order to guarantee strong equilibrium. These results extend and improve earlier ones by Holzman and Law-Yone in the increasing case, and by Epstein et al. in the decreasing case.

(December-8 2015) Moshe Tennenholtz, Technion. 

Title: Sequential Commitment Games (joint work with Itai Arieli and Yakov Babichenko).

Abstract: A main social puzzle is how a set of participants finds its way to a Pareto-efficient outcome while each participant maximizes his own utility. In his seminal book Schelling introduced several concepts that may serve this purpose. Two of the main issues discussed in Schelling's book that led to central developments in game theory one may further exploit, are credible commitments and legitimate authority. Commitments can be used in order to promise cooperation orthreatening against deviation from cooperation by other participants, but must subscribe to sequential rationality. A legitimate authority, aka mediator, can be used to enforce commitment and in order to facilitate moving the society from one equilibrium to another. In this work we extend the above foundational literature, by introducing the use of sequentialunconditional voluntary commitments in extensive form games, where the main novel aspect is the design of proper ordering of commitments that will guarantee Pareto-optimal outcome, where the ordering is determined without knowing the utility structure. Our first main result demonstrates a family of depth first search commitment protocols for which Pareto efficiency is implementable in every two-player extensive form game. We further show that in general efficiency is not implementable if the number of players in the game is at least four. Lastly, we consider the class of quitting gamesand show that within this class Pareto efficiency is implementable for every number of players.

The work on sequential commitment games is joint work with Itai Arieli and Yakov Babichenko. Our study of sequentialcommitments games is part of a general agenda of mediator design. If time permits we will briefly discuss some additional recent results under this agenda.

(November-24 2015) Igal Milchtaich, Bar Ilan University. 

Title: Perfect Bayesian Polyequilibrium.

Abstract: Polyequilibrium is a generalization of Nash equilibrium that is applicable to any strategic game, whether finite or otherwise, and to dynamic games, with perfect or imperfect information. It differs from equilibrium in specifying strategies that players do not choose and by requiring an after-the-fact justification for the exclusion of these strategies rather than the retainment of the non-excluded ones. Specifically, for each excluded strategy of each player there must be a non-excluded one that responds to every profile of non-excluded strategies of the other players at least as well as the first strategy does. A polyequilibrium’s description of the outcome of the game may be more or less specific, depending on the number and the identities of the non-excluded strategy profiles. A particular property of the outcome is said to hold in a polyequilibrium if it holds for all non-excluded profiles. Such a property does not necessarily hold in any Nash equilibrium in the game. In this sense, the generalization proposed in this work extends the set of justifiable predictions concerning a game’s results.

(November-17 2015) Gaetan Fournier, Tel-Aviv University. 

Title: Market games.

Abstract: A market with asymmetric information can be viewed as a repeated game between informed and uniformed agents. We discuss several results in this literature, and in particular the case of a risk averse market (De Meyer and Fournier 2015) and the case of a multi-asset market (Fournier 2015). The main results of these papers are that the price processes in such markets should be, after a change of probability, a particular kind of Brownian martingale, called CMMV.

(November-10 2015) Dudu Lagziel, Tel-Aviv University. 

Title: Reward Schemes (joint with Ehud Lehrer).

Abstract: An investor has some funds invested through investment firms. She also has additional funds to allocate among these investment firms according to the firms' performance. While the investor tries to maximize her total expected earnings, each investment firm tries to maximize the overall amount of funds it will be allocated to manage. A reward scheme is a rule that determines how funds are to be allocated among the investment firms based on their past performance. A reward scheme is optimal if it induces the (self-interested) firms to act in accordance with the interests of the investor. We show that an optimal reward scheme exists under quite general conditions.

(November-3 2015) Yaron Azrieli, Ohio State University. 

Title: On the self-(in)stability of weighted majority rules (joint work with Semin Kim).

Abstract: A voting rule f is self-stable (Barber`a and Jackson [4]) if any alternative rule g does not have sufficient support in the society to replace f, where the decision between f and g is based on the rule f itself. While Barber`a and Jackson focused on anonymous rules in which all agents have the same voting power, we consider here the larger class of weighted majority rules. Our main result is a characterization of self-stability in this setup, which shows that only few rules of a very particular form satisfy this criterion. This result provides a possible explanation for the tendency of societies to use more conservative rules when it comes to changing the voting rule. We discuss self-stability in this latter case, where a different rule F may be used to decide between f and g.

Link to the paper: http://web.econ.ohio-state.edu/azrieli/papers/self-stable-web.pdf

(October-27 2015) Eilon Solan, TAU.

Title: Overtaking Optimality in Markov Decision Problems (Joint work with Janos Flesch and Arkadi Predtetchinski).

Abstract: We consider the notion of overtaking optimality as introduced in Meder et al. (2012) for Markov decision problems (MDP). For the class of deterministic MDPs, we prove the existence of pure stationary overtaking optimal strategies under both the discounted and the average payoff evaluations. Moreover, we examine logical connections between overtaking optimalilty and Blackwell optimality. In the class of non-deterministic MDPs, we give examples that admit no overtaking optimal strategy and discuss a number of alternative definitions of overtaking optimality.

2014 - 2015

The schedule for 2014-2015 was: 

(November-4 2014) Janos Flesch. 

(November-11 2014) Yakov Babichenko. 

(November-18 2014) Yannai Gonczarowski. 

(November-25 2014) Ran Spiegler. 

(December-2 2014) Rann Smorodinsky. 

(December-9 2014) Eilon Solan. 

(December-16 2014) David Lagziel. 

(December-30 2014) Dov Samet. 

(January-6 2015) Edi Karni. 

(January-13 2015) Gaetan Fournier. 

(March-10 2015) Nabil Al-Najjar. 

(March-15 2015) Wolfgang Kuhle. 

(March-24 2015) Yaron Azrieli. 

(April-14 2015) Marco Scarsini. 

(April-21 2015) Abraham Neyman. 

(April-28 2015) Steven Kou. 

(May-5 2015) Avinatan Hassidim. 

(May-19 2015) Artyom Jenov. 

(May-26 2015) Niv Buchbinder. 

(June-9 2015) Rafi Hassin.

(June-9 2015) Rafi Hassin, TAU.

Title: Non-price control of queueing systems.

Abstract: We present old and new results on controlling the equilibrium behavior in simple queueing systems. Replacing the common first-come first-served order by last-come first-served order can often increase welfare and profits and also enables simpler computation of the optimal control in the original first-come first-served queue.

(May-26 2015) Niv Buchbinder, TAU.

Title: A Primal-Dual Approach to Online Optimization Problems.

Abstract: The primal-dual method is one of the fundamental design methodologies in the areas of linear programming, combinatorial optimization, and approximation algorithms. In this talk I will provide an introduction to the area of online combinatorial optimization. I will then discuss the primal-dual method as a unified framework to the design and analysis of online algorithms. Examples for which this approach is applicable include central online problems such as paging, routing, scheduling, online set cover, and graph connectivity problems. Finally, I will show some connections between online combinatorial optimization and online learning.

(May-19 2015) Artyom Jenov, Department of Economics and Business Administration, Ariel.

Title: Attacking the Unknown Weapons of a Possible Provocateur: How Intelligence Affects the Strategic Interaction (joint with Y.Tauman and R.Zeckhauser).

Abstract: We consider the interaction of two enemy nations. Nation 1 wants to develop a nuclear bomb (or other weapons of mass destruction). Nation 2 wants to prevent such a development through the deterrence of a threatened attack, or an actual attack if it thought the bomb was produced. 2 has an intelligence system that imperfectly indicates the presence of a bomb. 1, if lacking the bomb, can open its facilities to prevent an attack. A further uncertainty is that nation 2 does not know nation 1's type. He could be a Deterrer, whose prime goal is to avoid an attack, or he could a Provocateur who prefers an unjustified attack if he does not possess the bomb, so as to build support from inside his nation and the outside world. The game has a unique sequential equilibrium. The qualitative nature of that equilibrium depends on parameters, on preferences and information conditions.

A number of initially counterintuitive results emerge. For example, it may sometimes be rational (an equilibrium strategy) for 2 to attack even though 1 does not have a bomb, and even though 2's high quality intelligence system indicates that a bomb is not present. Fortunately, intuitive explanations can be provided for all such results.

Illustrations of the model's implications are provided from the experiences of the West (as nation 2) with Saddam Hussein (as nation 1).

(May-5 2015) Avinatan Hassidim, Bar Ilan University and Google Israel.

Title: Submodular maximization under noise (joint with Yaron Singer).

Abstract: For the past decade there has been incredible progress in the theory and application of submodular optimization in computer science. In many applications however, we do not have access to the submodular function we aim to optimize, but rather some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a submodular function under noise, and show that: 1. If the noise is adversarial, no non trivial approximation guarantee can be given. 2. For general matroids, there is a constant factor approximation. We flesh a special case of this result for uniform matroids, and explain how to extend it 3. For uniform matroids with cardinality $k = \omega(\log n)$ there is a $1 - 1/e -\epsilon$ approximation algorithm. We show that no such algorithm can be obtained for the case $k = 1$.

(April-28 2015) Steven Kou, Columbia University.

Title: Separating Skilled and Unskilled Fund Managers by Contract Design (joint with Xuedong He and Sang Hu).

Abstract: Foster and Young (2010, Quarterly Journal of Economics) shows that it is very difficult to design performance fee contracts that reward skilled fund managers while screening out unskilled fund managers. In particular, none of the standard practices, such as postponing bonuses and claw back provisions, can separate skilled and unskilled managers. We show that if: (1) there is a liquidation boundary, meaning that the fund investors will close the fund if the fund return is bad enough to hit the boundary, and (2) the fund manager has to use his/her own money to set up a deposit to offset the potential losses from the fund investors, then the skilled and unskilled fund managers can be separated. The deposit can be a combination of cash or an equity stake in the fund.

(April-21 2015) Abraham Neyman, Hebrew University.

Title: Discounting-robust equilibria of Markov decision processes and stochastic games.

Abstract: A player's discounting valuation of a stream of stage payoffs is a weighted average of his stage payoffs, where the weights are nonincreasing in the stage. A stochastic game $\Gamma$ together with a profile of discounting valuations $w$ define a game $\Gamma_w$. We introduce the concept of discounting-robust equilibria of a discrete-time stochastic game. Its existence means that there exists approximate equilibria that are robust to small changes in the discounting valuations. It is proved that a stochastic game has a discounting-robust equilibrium if and only if it has a uniform equilibrium payoff. We show that if a stochastic game $\Gamma$ has discounting-robust equilibria then for every $\ve>0$ there is a finite list of strategies and payoffs such that for every profile $w$ of discounting valuations there is a member in the list that is an $\ve$-equilibrium of $\Gamma_w$.

(April-14 2015) Marco Scarsini (Luiss Guido Carl).

Title: On Information Distortions in Online Ratings.

Abstract: Consumer reviews and ratings of products and services have become ubiquitous on the Internet. This paper analyzes, given the sequential nature of reviews and the limited feedback of such past reviews, the information content they communicate to future customers. We focus on the informational setting in which customers only observe the sample mean of past reviews, and ask if customers can recover the true quality of the product based on the feedback they observe. We first analyze the benchmark setting, in which customers interpret the mean as the proxy of quality. In such a case, we show that in the long run, the sample mean of review stabilizes and two cases may arise. If customers are relatively homogeneous, then social learning takes place. If customers are sufficiently heterogeneous, then they consistently overestimate the underlying quality of the product in the long run. This bias stems from the selection associated with observing only reviews of customers who purchase. We show, however, that if customers are sophisticated, then there exists a simple quality inference and purchasing rule that corrects for the selection bias and leads to social learning. In addition, we show that the cumulative consumer surplus losses scale with the square root of the number of customers who have considered a purchase to date, which is of the same order as when customers observe the reviews of all preceding customers. In this framework, we also analyze the externality of sophisticated customers on more naïve ones and quantify the impact that manipulated reviews may have.

(March-24 2015) Yaron Azrieli (Ohio State University).

Title: The price of `One Person, One Vote’.

Abstract: The principle of `One Person, One Vote' is viewed by many as one of the cornerstones of Democracy. But in environments where agents have heterogenous stakes, a utilitarian social planner would typically prefer non-anonymous rules, i.e.\ rules that violate this principle. We consider a simple Bayesian voting environment in which agents have private valuations for the alternatives and a voting mechanism is used to determine the outcome. The price of `One Person, One Vote' is defined as the fraction reduction in expected welfare when the optimal anonymous mechanism is used relative to the optimal (not necessarily anonymous) mechanism. We analyze how this price behaves as a function of the environment (distribution of preferences). In particular, it is shown that if the inequality of stakes in the population increases, in a well-defined sense, then the price of `One Person, One Vote' is higher. A similar comparative statics holds if the uncertainty about agents' preferences increases. Our results may be useful for social planners who weigh the moral argument (or other arguments) in favor of `One Person, One Vote' with the loss of efficiency that may result by sticking to this principle.

(March-15 2015) Wolfgang Kuhle (Max Planck Institute).

Title: A Global Game with Heterogenous Priors.

(March-10 2015) Nabil Al-Najjar (Northwestern University).

Title: Uncertainty and Hedging in Large Populations (joint work with Luciano Pomatto).

(January-13 2015) Gaëtan Fournier (Paris-Sorbonne University).

Title: Efficiency of Equilibria in Hotelling Games. (joint work with Marco Scarsini)

Abstract: We consider a Hotelling game where a finite number of retailers choose a location, given that their potential customers are distributed on a network. Retailers do not compete on price but only on location. We show that when the number of retailers is large enough, the game admits a pure Nash equilibrium and we construct it. We then compare the equilibrium cost bore by the consumers with the cost that could be achieved if the retailers followed the dictate of a benevolent planner. We look at this efficiency of equilibrium asymptotically in the number of retailers.

(January-6 2015) Edi Karni (Johns Hopkins University).

Title: Awareness Of Unawareness.

Abstract: In the wake of growing awareness, decision makers anticipate that they might acquire knowledge that, in their current state of ignorance, is unimaginable. Supposedly, this anticipation manifests itself in the decision makers' choice behavior. In this paper we model the anticipation of growing awareness, lay choice-based axiomatic foundations to subjective expected utility representation of beliefs about likelihood of discovering unknown consequences, and assign utility to consequences that are not only unimaginable but may also be nonexistent. In so doing, we maintain the flavor of reverse Bayesianism of Karni and Vierø (2013, 2014).

(December-30 2014) Dov Samet (Tel-Aviv University).

Title: Cracking the mystery of weak dominance or Elementary game theory simplified.

Abstract: A common informal argument shows that if it is common knowledge that players do not play strongly dominated strategies then players can play only profiles that survive the iterative elimination of strongly dominated strategies. By providing a simple setup that formalizes this argument, we are able to state analogues result concerning weakly dominated strategies. We characterize the profiles that can be played when it is common knowledge that players do not play weakly dominated strategies. These characterizations lead us to study the notion of non-probabilistic correlated equilibrium which is a probability-free version of correlated equilibrium.

(December-16 2014) David Lagziel (Tel-Aviv University).

Title: Failures in Second-Price Auctions.

Abstract: We examine sealed-bid second-price auctions where, with a certain probability, the bidders fail to pay their debt to the seller. In such auctions, both the seller and the bidders might gain if the bidders lower their bids relative to the equilibrium bids. Given some assumptions on the probability to default, we show that an upper bound on the bids, induced by the seller, increases the expected payoff of all the parties involved.

(December-9 2014) Eilon Solan (Tel-Aviv University).

Title: Acceptable Strategy Profiles in Stochastic Games.

Abstract: I will present a new solution concept for multiplayer stochastic games, namely, \emph{$\ep$-acceptable} strategy profiles. Those are strategy profiles that, for every initial state, yield to each player at least his discounted max-min value up to $\ep$, simultaneously for every discount factor, provided the players' discount factors are sufficiently close to 1. We prove the existence of a stationary $\ep$-acceptable strategy profile in every multiplayer stochastic game. Such strategy profiles have two desirable features: they are simple (stationary) and yield to each player a reasonable payoff (though not the best payoff he can obtain).

(December-2 2014) Rann Smorodinsky (Technion).

Title: Job Security, Stability and Production Efficiency.

Abstract: We study a 2-sided matching market with a set of heterogeneous firms and workers in an environment where jobs are secured by regulation. Without job security Kelso and Crawford have shown that stable outcomes and efficiency prevail when all workers are (weak) gross substitutes to each firm, in the sense that increases in other workers’ salaries can never cause a firm to withdraw an offer from a worker whose salary has not risen. It turns out that by introducing job security, stability and efficiency may still prevail, and even for a significantly broader class of production functions.

(November-25 2014) Ran Spiegler (Tel-Aviv University).

Title: Behavioral imputation.

Abstract: A decision maker (DM) wishes to learn a joint probability distribution p over n variables. He obtains a large number of independent observations. However, in each observation the values of some of the variables are missing, according to some independent random process. The DM wishes to extend his incomplete dataset into a fully specified, "rectangular" dataset. To do so, he employs an intuitive iterative imputation procedure, which is somewhat related to the "stochastic regression" method from the literature on statistical inference with missing data. The frequencies in the completed dadaset constitute the DM's subjective belief. I characterize the subjective beliefs that emerge from this imputation procedure. When the support of the missing-values process satisfies the so-called "running intersection property", the imputation procedure always terminates succcessfully and produces a subjective belief with a "Bayesian network" representation, which factorizes the objective distribution p according to a perfect directed acyclic graph. When the running intersection property is violated, the procedure is aborted for some p. This result provides a foundation for various models of systematic belief distortions in the literature.

(November-18 2014) Yannai A. Gonczarowski (Hebrew University and Microsoft Research).

Title: Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games (Joint work with Moshe Tenneholtz).

Abstract: Drawing intuition from a (physical) hydraulic system, we present a novel framework, constructively showing the existence of a strong Nash equilibrium in resource selection games with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the invariance of the cost of each given resource across all Nash equilibria. Our proofs allow for explicit calculation of Nash equilibrium and for explicit and direct calculation of the resulting (invariant) costs of resources, and do not hinge on any fixed-point theorem, on the Minimax theorem or any equivalent result, on the existence of a potential, or on linear programming. A generalization of resource selection games, called resource selection games with I.D.-dependent weighting, is defined, and the results are extended to this family, showing that while resource costs are no longer invariant across Nash equilibria in games of this family, they are nonetheless invariant across all strong Nash equilibria, drawing a novel fundamental connection between group deviation and I.D.-congestion. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described.

(November-11 2014) Yakov Babichenko (Technion).

Title: Query complexity of approximate Nash equilibria.

Abstract: We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players. Our main result states that for n-player binary-action games and for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n. As a consequences of this result, we get an exponential lower bound on the rate of convergence of adaptive dynamics to approximate Nash equilibria.

(November-4 2014) Janos flesch (Maastricht University).

Title: Subgame-perfect equilibrium in a class of perfect information games, where each player controls one state (Joint work with Jeroen Kuipers, Gijs Schoenmakers and Koos Vrieze).

Abstract: We consider a class of multi-player games that are played as follows. Player 1 starts and he has two options: he can decide to stop the game or he can choose another player, possibly only from a subset of his opponents. In the latter case, the chosen player faces a similar decision: he can stop the game, or choose one of his opponents, maybe even player 1 again. This process is repeated until a player stops the game. A payoff to each player is determined as follows: If no one ever stops the game, then the payoff to each player is zero, and otherwise the payoff to each player only depends on the identity of the player who stopped the game.

We construct approximate subgame-perfect equilibria for these games. This is particularly challenging when the payoffs at stopping can be negative, because it makes the strategic situation fairly complex. The proof is combinatorial, and uses an iterative elimination procedure that terminates in a finite number of steps. We also discuss possible consequences of this result for the existence of approximate subgame-perfect equilibria in more general classes of games.

(June-24 2014) Paul Milgrom (Stanford University).

This week's seminar will be held in Room 309, Schreiber building, at 12:00 PM.

Title: Deferred-Acceptance Auctions and Radio Spectrum Reallocation.

Abstract: Deferred-acceptance auctions choose allocations by an iterative process of rejecting the least attractive bid. These auctions have distinctive computational and incentive properties that make them suitable for application in some challenging environments, such as the planned US auction to repurchase television broadcast rights. For any set of values, any deferred acceptance auction with “threshold pricing”is weakly group strategy-proof, can be implemented using a clock auction, and leads to the same outcome as the complete-information Nash equilibrium of the corresponding paid-as-bid auction. A paid-as- bid auction with a non-bossy bid-selection rule is dominance solvable if and only if it is a deferred acceptance auction.

(June-8 2014) Aloisio Araujo (IMPA, Rio de Janeiro, Brazil).

Title: General Equilibrium, Risk Loving, Ambiguity, and Volatility.

Abstract: What is the role of risk loving in "smooth" consumption at equilibrium? Can risk sharing be characterized at equilibrium? What is the role of rank-dependency and ambiguity loving? The difficulty in addressing these questions is in the lack of convexity that may prevent the existence of equilibrium. Related questions arise whether volatility tends to increase and whether regulation affects welfare and volatility. 

We prove that with sufficient aggregate risk, equilibrium exists, even with a finite number of agents, for a very large class of preferences. For rank-dependent preferences, there is risk-sharing for these equilibria.

We also provide robust examples in which:

1. Risk-taking decreases the volatility and improves welfare.

2. Regulation increases volatility and reduces welfare.

(May-29 2014) Fabien Gensbittel (Toulouse).

Title: Continuous-time limit of dynamic games with incomplete information and a more informed player.

Abstract: We study a model of two-player, zero-sum, dynamic game with incomplete information on one side in which the players receive exogenous information about the payoff-relevant state variable during the play. We assume that one of the players is always more informed than his opponent and that signals observed during the play correspond to the observation of some continuous-time Markov process at some fixed times on a finite grid. We show the existence of a limit value as the players play more and more frequently, and we provide two different characterizations for this value: through a stochastic optimization problem and through a variational inequality, related to some second-order Hamilton-Jacobi equation in some particular cases.

(May-20 2014) Roee Teper (University of Pittsburgh).

Title: Subjective independence and concave expected utility (joint with Ehud Lehrer).

Abstract: When a potential hedge between alternatives does not reduce the exposure to uncertainty as perceived by the decision maker, we say that she considers these alternatives as similar. While similarity in the current context seems like a subjective notion and should be different across decision makers, thus far it was treated in an objective manner. We take the former approach. Similarity of alternatives can be recovered through a property (axiom) of the individual’s preferences referred to as subjective codecomposable independence. This axiom characterizes a class of event-separable models and provides a behavioral foundation to Concave Expected Utility preferences. Stemming from subjective similarity, the flexibility of Concave Expected Utility allows it to accommodate recent paradoxes posed by Machina to Choquet expected utility, which is characterized by objective similarity.

(May-13 2014) Michal Feldman (Tel-Aviv University).

Title: A Unifying Hierarchy of Valuations with Complements and Substitutes (Joint work with Uriel Feige, Rani Iszak, Nicole Immorlica, Brendan Lucier, and Vasilis Syrgkanis).

Abstract: We introduce a new hierarchy over monotone set functions, that we refer to as $\MOPH$ (Maximum over Positive Hypergraphs), and study its applications to valuation functions for agents in multi-item markets. The highest level of the hierarchy, $\MOPH$-$m$ (where $m$ is the total number of items) captures all monotone functions. The lowest level, $\MOPH$-$1$, captures all monotone submodular functions, and more generally, the class of functions known as $\XOS$. Every monotone function that has a positive hypergraph representation of rank $k$ (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in $\MOPH$-$k$. Every monotone function that has supermodular degree $k$ (in the sense defined by Feige and Izsak [ITCS 2013]) is in $\MOPH$-$(k+1)$. In both cases, the converse direction does not hold, even in an approximate sense. We present additional results for the expressiveness of $\MOPH$-$k$, some of which can be regarded as surprising. We also present intriguing open questions in this respect.

One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the $\MOPH$ hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of $k+1$ if all players hold valuation functions in $\MOPH$-$k$. The other is an upper bound of $2k$ on the price of anarchy of simultaneous first price auctions.

Being in $\MOPH$-$k$ can be shown to involve two requirements -- one is monotonicity and the other is a certain requirement that we refer to as $\PLE$ (Positive Lower Envelope). Removing the monotonicity requirement, one obtains the $\PLE$ hierarchy over all non-negative set functions (whether monotone or not), which can be fertile ground for further research.

(April-1 2014) Yannai A. Gonczarowski (Hebrew University and Microsoft Research).

Title: Manipulation of Stable Matchings using Minimal Blacklists.

Abstract: Gale and Sotomayor [1985] have shown that in the Gale-Shapley matching algorithm [1962], the proposed-to side W (referred to as women there) can strategically force the W-optimal stable matching as the M-optimal one by truncating their preference lists, each woman possibly blacklisting all but one man. As Gusfield and Irving have already noted in 1989, no results are known regarding achieving this feat by means other than such preference-list truncation, i.e. by also permuting preference lists.

We answer Gusfield and Irving's open question by providing tight upper bounds on the amount of blacklists and their combined size, that are required by the women to force a given matching as the M-optimal stable matching, or, more generally, as the unique stable matching. Our results show that the coalition of all women can strategically force any matching as the unique stable matching, using preference lists in which at most half of the women have nonempty blacklists, and in which the average blacklist size is less than 1. This allows the women to manipulate the market in a manner that is far more inconspicuous, in a sense, than previously realized. When there are less women than men, we show that in the absence of blacklists for men, the women can force any matching as the unique stable matching without blacklisting anyone, while when there are more women than men, each to-be-unmatched woman may have to blacklist as many as all men. Together, these results shed light on the question of how much, if at all, do given preferences for one side a priori impose limitations on the set of stable matchings under various conditions. All of the results in this paper are constructive, providing efficient algorithms for calculating the desired strategies.

(March-25 2014) Yehuda John Levy (University of Oxford).

Title: Rational Learning Need Not Lead to Exact Equilibria.

Abstract: A long-standing open question raised in Kalai and Lehrer (1993) is whether or not the play of a subjective equilibrium of the infinitely repeated game, in the rational learning model introduced there, must eventually resemble play of an exact equilibria, and not just play of approximate equilibria as demonstrated there. This paper shows, by example, that play of subjective equilibria may remain distant - in fact, mutually singular - to play of exact equilibria.

(March-11 2014) Shai Vardi, Tel Aviv University.

Title: Local Computation Mechanism Design - Stable Matching (with Avinatan Hassidim and Yishay Mansour).

Abstract: We introduce the notion of Local Computation Mechanism Design - designing game theoretic mechanisms which run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. In addition, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanisms need to maintain incentive compatibility with respect to the allocation and payments.

We present local computation mechanisms for a variety of classical game-theoretical problems, focusing on stable matching.

We show that our local results have general implications. Specifically, we show that when the men’s preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.

(March-4 2014) Tai-Wei Hu, Nothwestern University.

Title: Information aggregation in a large two-stage market game (joint work with Neil Wallace).

Abstract: A market-game mechanism is studied in a two-divisible-good, pure-exchange setting with potential information-aggregation. The mechanism is simple: agents’ actions are quantities and outcomes are determined by simple algorithms that do not depend on the details of the economy. There are two stages. First, agents make offers, which are provisional for all but a small, randomly selected group. Then, those offers are announced, and everyone else gets to make new offers with payoffs determined by a Shapley-Shubik market game. For a finite and large number of players, there exists an almost ex-post efficient equilibrium. Conditions for uniqueness are provided.

(February-25 2014) Gilad Bavly, Tel Aviv University.

Title: How to Gamble Against All Odds (joint work with Ron Peretz).

Abstract: Player 0, the cousin of the casino owner, is allowed to bet sums of money only within a set A (a subset of the real numbers). The regular casino players 1,2,3,... (countably many players) are allowed to make bets only within another set B. Player 0 announces her betting strategy first; then the regular players announce theirs. Now the casino owner wants to fix an infinite sequence of Reds and Blacks, such that player 0 makes infinite gains, while every regular player gains only a finite amount. Can this be done when, e.g., A is the set of all even integers, and B the set of all odds? We present some sufficient and necessary conditions on the pair of sets A and B.

(January-12 2014, 14:00-15:00, Kaplun 324) Bruno Zilloto.

Title: Zero-sum repeated games: counterexamples to the existence of the asymptotic value and the conjecture maxmin=lim v(n).

Abstract: Mertens (1986) proposed two general conjectures about repeated games. First, in any two-person zero-sum repeated game, the asymptotic value exists, and second, when Player 1 is more informed than Player 2, in the long run Player 1 is able to guarantee the limit value of the n-stage game.

We disprove these two long-standing conjectures by providing an example of a zero-sum repeated game with public signals and perfect observation of the actions, where neither the value of the lambda-discounted game nor the value of the n-stage game converges, when lambda goes to 0 or n goes to infinity, respectively.

The aforementioned example involves seven states, two actions and two signals for each player. Remarkably, players observe the payoffs, and play in turn.

(January-5th 2014) Nabil Al-Najjar, Northwestern University.

The seminar will be held in Schreiber 209. 

Title: Aggregative utility in large populations (joint with Luciano Pomatto).

(December-31st 2013) Yaron Azrieli, Ohio State University.

Title: Incentives in experiments: A theoretical analysis (with Christopher Chambers and PJ Healy).

Abstract: The purpose of an experiment is to observe choice in a controlled setting. When subjects are given multiple decisions, however, subjects’ choices in one decision may be distorted by the choices made in others. This paper formulates a simple abstract model of an experiment and defines a notion of Incentive Compatibility (IC) of the associated payment mechanism. Assuming that preferences over lotteries satisfy first order stochastic dominance (and nothing else), we characterize the class of IC payment mechanisms. In particular, it follows from our characterization that in most experiments the only IC mechanism is the Random Problem Selection mechanism, in which one decision problem is randomly chosen for payment

(December-17th 2013) Eran Hanany, Tel Aviv University

Title: Subgame Perfect Farsighted Stability.

Abstract: Farsighted game theoretic solution concepts have been shown to provide insightful results in many applications. However, we provide simple examples demonstrating that the existing solution concepts are not sufficiently farsighted, and in this paper we propose a new farsighted solution concept, the Subgame Perfect Consistent Set (SPCS). Based on von Neumann Morgenstern type consistency and subgame perfect equilibrium, this solution is shown to lead to more satisfactory predictions in many situations as compared to existing myopic or farsighted solution concepts. Strikingly, the SPCS is shown to always achieve Pareto efficiency in farsighted normal form games. This result is demonstrated in various oligopolistic settings, and is shown to imply, for example, that in contrast with existing farsighted solution concepts, players who follow the SPCS reasoning are always able to share the monopolistic profit in Bertrand and Cournot competition negotiations, and are always able to achieve coordination and Pareto efficiency in decentralized supply chain contracting, even when they are unable to form coalitions.

(December-3rd 2013) Moshe Haviv, The Hebrew University.

Title: Regulating Arrivals to a Queue.

Abstract: Selfish customers do not necessarily join a queue at a socially optimal rate. Hence, queueing systems may call for regulation. For customers arriving to unobservable queue who are homogeneous with respect to waiting costs and service rewards, we show how queueing systems can be regulated by imposing an entry fee, a holding fee (i.e., a fee based on time in the system), or a service fee (i.e., a fee based on the required service time) in the case where customers know their service requirements. We start with a unified approach and state the socially optimal fees. We then show that customers are always worse off under a flat entry free in comparison with holding and service fees. As for holding vs. service fees, the answer depends on the queueing regime and/or the service length itself. For example, under the first-comes first-serve regime, service fees are preferred by all. We also review the case where customers know only the distribution of service times, but not their actual requirements

(November-26th 2013) Itai Arieli, The Technion.

Title: Inferring Beliefs from Actions (joint with M. Muller-Frank).

Abstract: This paper considers single-agent decision making under uncertainty and addresses the question to which degree the private information of an agent is revealed through his optimal action. We show that the agents optimal action reveals his posterior distribution for all but a negligible subset (formally, a meager subset) of the space of continuous utility functions if and only if the set of actions contains no isolated points. If the action set is uncountable (not necessarily perfect), then there exists a continuous utility function such that actions reveal beliefs. On the basis of the single-agent belief revelation result we establish information aggregation results in the framework of repeated interaction in social networks and in the sequential social learning model.

(November-19th 2013) Igal Milchtaich, Bar-Ilan University.

Title: Time-Differentiated Monopolies (joint with A. Glazer and R. Hassin)

Abstract: We consider sequential competition among sellers, with different consumers desiring the good at different times. Each consumer could buy from a later seller. Each seller recognizes that future sellers are potential competitors, and therefore does not necessarily set his monopoly price, which is the price he would set if consumers could only buy from the first seller they encounter. We show, however, that whether an equilibrium price is indeed lower than the monopoly price of each seller depends on the form of consumers’ impatience. With time discounting, this is so. But when impatience reflects decreasing valuations, the equilibrium price may (and, in certain cases, must) coincide with the sellers’ monopoly prices, which means that their market power is not diminished by competition with future sellers. Even in this case, however, prices below the monopoly price may exist if sellers are aware of the history of sales and may react to previous price changes.

(November-12th 2013) Victoria Kreps, St. Petersburg Institute for Econ. and Math.

Title: Repeated games with asymmetric information modeling financial markets with two risky assets (joint with Victor Domansky).

Abstract: We consider multistage bidding models where shares of two types of risky assets are traded between two agents that have different information on the liquidation prices of traded assets. These prices are random integer variables that are determined by the initial chance move according to a probability distribution p over the two-dimensional integer lattice that is known to both players. Player 1 is informed on the prices of both types of shares, but Player 2 is not. The bids may take any integer values.

The model of n-stage bidding is reduced to a zero-sum repeated game with lack of information on one side. We show that, if liquidation prices of shares have finite variances, then the sequence of values of n-step games is bounded. This makes it reasonable to consider the bidding of unlimited duration that is reduced to the infinite game G1(p). We give the solutions for these games. The optimal strategy of Player 1 generates a random walk of transaction prices. But unlike the case of one-type assets (Domansky, 2007), (Domansky, Kreps, 2009), the symmetry of this random walk is broken at the final stages of the game (Domansky, Kreps, 2013).

(November-5th 2013) Ezra Einy, Ben Gurion University.

Title: Tullock Contests with Asymmetric Information.

Abstract: We show that under standard assumptions a Tullock contest with incomplete (and possibly asymmetric) information has a pure strategy Bayesian Nash equilibrium. The existence result extends to a very broad class of generalized Tullock contests, characterized by certain mild assumptions on the success function. Next we study common-value Tullock contests. We show that in equilibrium the expected payoff of a player is greater or equal to that of any other player with less information, i.e., an information advantage is rewarded. Moreover, if there are only two players and one of them has an information advantage, then in the unique equilibrium both players exert the same expected effort, although the less informed player wins the prize more frequently. These latter properties do not extend to contests with more than two players. Interestingly, players may exert more effort in a Tullock contest than in an all-pay auction.

(October-29th 2013) Aviad Heifetz, Open University.

Title: Robust Multiplicity with a Grain of Naivite (joint work with Willemien Kets).

Abstract: Weinstein and Yildiz (2007) showed that, surprisingly, in games with incomplete information that satisfy a richness condition, players generically have a unique rationalizable action. We show that this result does not carry over to environments where players may have even a tiny "grain of naivite", i.e. with a (possibly transfinite) sequence of mutual suspicions that some player might eventually have a finite depth of reasoning. Our results demonstrate that both uniqueness and multiplicity are robust phenomena in this richer environment. In particular, if we do not insist on players having common belief in the event that players have an infinite depth of reasoning (as in standard Harsanyi type spaces), then there need not be a discontinuity in rationalizable behavior when perturbing a complete-information game to a game where payoffs are approximate common belief.

(October-22nd 2013) Isaac Meilijson, Tel Aviv University.

Title: Preference for safety under the Choquet model: in search of a characterization.

Abstract: Victor prefers safety more than Ursula if whenever Ursula prefers a constant to an uncertain act, so does Victor. This paradigm, whose Expected Utility (EU) version is Arrow & Pratt's more risk aversion concept, will be studied in Schmeidler’s Choquet Expected Utility (CEU) model. Unlike the EU case, preference for safety versus dichotomous acts does not imply preference for safety over general acts.

The treatment, by Michèle Cohen and the speaker, preserves the flavor of the "more pessimism than greediness" characterization of monotone risk aversion by Chateauneuf, Cohen & Meilijson in the Rank-Dependent Utility (RDU) model and its extension by Grant & Quiggin to CEU.

A connection with multiple-chip betting in Dubins & Savage roulette proves useful for the analysis.

(January-15th 2013) John Levy, The Hebrew University.

Title: A Cantor Set of Games with No Shift-Homogeneous Equilibrium Selection.

Abstract: We construct a continuum of games on a countable set of players that does not possess a measurable equilibrium selection that satisfies a natural homogeneity property. The explicit nature of the construction yields counterexamples to the existence of equilibria in models with overlapping generations and in games with a continuum of players.

(January-8th 2013) Xavier Venel, Tel Aviv University.

Title: A distance for probability spaces and long-term values in Markov Decision Processes.

Abstract: Given a finite set K, we denote by X the set of probabilities on K and by Z the set of Borel probabilities on X with finite support. Studying a Markov Decision Process with partial information on K naturally leads to a Markov Decision Process with full information on X. We introduce a new metric d* on Z such that the transitions become 1-Lipschitz from (X, ||.||_1) to (Z,d*). We prove several results about d_* and characterize the limit values in Partial Observation MDP with finitely many states. Moreover, we show an existence result of a generalized notion of uniform value when the number of stages is large enough.

(January-1st 2013) Ron Peretz, LSE.

Title: Effective betting with restricted wagers.

Abstract: A sequence of players enter the Casino. Player 1 declares her betting strategy, a function from finite histories of Heads and Tails to real-valued wagers. Then the rest of the players 2,3,... (countably many of them) declare their strategies, but they are restricted to integer-valued wagers. The Casino wants Player 1 to win while all the others lose. That is, the Casino should choose a sequence of Heads and Tails so that the limit of Player 1's capital is infinite while all others' is finite. Is it possible? Bienvenu et al (2012) show it is using Baire category theorem. Their proof applies even when Players 2,3,... are allowed to wager any real numbers from the set V={a: |a|>1 or a=0}. They ask whether or not it is possible to separate V and Z in a similar way? We answer "yes" to that question and address several similar problems.

(December-25th 2012) Roee Teper, University of Pittsburgh.

Title: Endowment as a Blessing (Joint with Sivan Frenkel and Yuval Heller).

Abstract: Experimental evidence and field data suggest that agents hold two seemingly unrelated biases: failure to account for the fact that the behavior of others reflects their private information (“winner’s curse”), and a tendency to value a good more once it is owned (“endowment effect”). In this paper we propose that these two phenomena are closely related: the biases fully compensate for each other in various economic interactions, and induce an “as-if rational” behavior. We pay specific attention to barter trade, of the kind that was common in prehistoric societies, and suggest that the endowment effect and the winner’s curse could have jointly survived natural selection together. Our results suggest that studying behavioral biases jointly rather than one at a time can deliver new insights about the role of behavioral biases in economic environments. 

(December-18th 2012) Ron Holzman, Technion.

Title: Impartial nominations for a prize (joint work with Herve Moulin).

Abstract: We consider rules that allow a set of agents to elect one of them to receive a prize (or undertake a task). The main requirement is impartiality: no agent should ever be able, by changing his message, to affect his own election. We construct such rules that are non-trivial and also obey some common social choice requirements. However, our main impossibility result states that if individual messages are nominations (every agent nominates one other agent for the prize), then no impartial rule exists that simultaneously respects positive unanimity (an agent nominated by everyone else always wins) and negative unanimity (an agent whom no one nominates never wins). 

(December-11th 2012) Gilad Bavly, Tel Aviv University.

Title: Elasticity of Games.

Abstract: We develop an elasticity index of a strategic game. The index measures the robustness of the set of rational outcomes of a game. The elasticity index of a game is the maximal ratio between the change of the rational outcomes and the size of an infinitesimal perturbation. The perturbation is on the players’ knowledge of the game. 

The elasticity of a strategic game is a nonnegative number. A small elasticity is indicative of the robustness of the rational outcomes (for example, if there is only one player the elasticity is 0), and a large elasticity is indicative of non-robustness. For example, the elasticity of the (normalized) n-stage finitely repeated prisoner’s dilemma is at least exponential in n, as is the elasticity of the n-stage centipede game and the n-ranged traveler’s dilemma. 

The concept of elasticity enables us to look from a different perspective at Neyman’s (1999) repeated games when the number of repetitions is not commonly known, and Aumann’s (1992) demonstration of the effect of irrationality perturbations. 

(December-4th 2012) Xu Zibo, The Hebrew University.

Title: Evolutionary stability in general extensive-form games of perfect information.

Abstract: We consider a basic dynamic evolutionary model with rare mutation and a best-reply (or better-reply) selection mechanism. A state is evolutionarily stable if its long-term relative frequency of occurrence is bounded away from zero as the mutation rate decreases to zero. We prove that, for all finite extensive-form games of perfect information, only Nash equilibria are evolutionarily stable. We show that, in games where a player may play at more than one node along some path, even when the populations increase to infinity, there may be some evolutionarily stable states which are not part of the backward induction equilibrium component. We give a sufficient condition for evolutionary stability and show how much extra value is needed in the terminal payoffs to make an equilibrium evolutionarily stable. 

(November-27th 2012) Anna Khmelnitskaya, Saint-Petersburg State University.

Title: Two solution concepts for TU games with directed communication structure.

Abstract: In classical cooperative game theory it is assumed that any coalition of players may form. However, in many practical situations the collection of feasible coalitions is restricted by some social, economical, hierarchical, communicational, or technical structure. The study of TU games with limited cooperation introduced by means of undirected communication graphs was initiated by Myerson (1977). 

In our study we consider directed graph games in which all players are partially ordered and possible communication via bilateral agreements between participants is presented by a directed graph (digraph). The approach to the solution for digraph games depends on the interpretation of a directed communication structure. If it is assumed that a digraph represents a flow situation when some links may merge while others split into several separate ones, we restrict our consideration to the class of cycle-free digraph games (only without directed cycles, undirected cycles are not excluded). We introduce web-type values, in particular the tree value, for cycle-free digraph games axiomatically, each one with respect to a chosen coalition of players that is assumed to be an anti-chain in the digraph and is considered as a management team. We provide the explicit formula representation and simple recursive algorithms to calculate these values and we study their efficiency and stability. We also define the average web value as the average of the web values over all management teams in the digraph. In general these values are not component efficient. As application we consider the water distribution problem of a river with multiple sources, a delta and possibly islands.

Another possible interpretation of a communication digraph is the assumption that a digraph represents the subordination of players such that after each player any of his subordinates may follow as long as this does not hurt the total subordination among the players prescribed by the digraph. In this case we define a covering tree for a digraph as a tree that keeps the subordination of players prescribed by the digraph but in general is not a spanning tree. We introduce the average covering tree value as the average of the tree values over all covering trees in the digraph. The average covering tree value appears to be component efficient.

(November-22nd 2012) Andrey Bernstein, Technion.

Title: Approachability in Repeated Games: Algorithms and Refinements.

Abstract: The theory of approachability, introduced by Blackwell (1956), provides fundamental results on repeated games with vector-valued payoffs, which proved useful in a variety of applications from repeated games with incomplete information to on-line learning algorithms. Given a repeated game with vector payoffs, a target set S is approachable by a designated player (the agent) if he can ensure that the average payoff vector converges to that set no matter what the opponent does. Blackwell provided two sets of necessary and sufficient conditions for a convex set to be approachable. The .first (primary) condition is a geometric separation condition, while the second (dual) condition requires that the set be non-excludable, namely that for every mixed action of the opponent there exists a mixed action of the agent (a response) such that the resulting expected payoff belongs to S. Existing approachability algorithms rely on the primal condition and require a projection direction from a given point to S to be computed at each stage. In the first part of the talk, we propose an approachability algorithm for convex target sets that uses Blackwell's dual condition. Thus, rather than projection, the algorithm requires to compute a response to a certain action of the opponent at each stage.

In the second part of the talk, we consider a refinement of the classical approachability problem. The notion of approachability accommodates a worst-case scenario with respect to the opponent’s strategy, as it requires the target set to be approachable for *any* strategy of the opponent. However, as the game unfolds, it may turn out that the opponent’s choices of actions are limited in some way. If these restrictions were known in advance, the agent could possibly ensure convergence of the average reward to some desired subset of the original set S, or even approach a set S that is not approachable in general. We formulate appropriate goals for opportunistic approachability algorithms, in the sense that they may exploit such limitations on the opponent’s action sequence in an on-line manner, without knowing them beforehand. In particular, we propose a class of algorithms that use a response to a calibrated forecast of the opponent’s actions, which are opportunistic in the above mentioned sense.

The utility of the proposed algorithms is demonstrated by applying it to some generalized regret minimization problems, in particular regret minimization with side constraints, where the computation of projections is generally complex but a response is readily obtainable. Moreover, in this problem, the best-reward-in-hindsight is not generally attainable, but only its convex relaxation. Our opportunistic algorithms applied to this problem does attain the best-reward-in-hindsight if the opponent’s play happens to be stationary (either in terms of its mixed actions, or the empirical frequencies of its pure actions). 

(November-6th 2012) Victor Domansky and Victoria Kreps.

Title: Repeated games with asymmetric information modeling multistage bidding for risky assets.

Abstract: We investigate a discrete variant of multistage bidding model for risky assets (shares) introduced by De Meyer and Moussa Saley (2002) to analyze the evolution of prices at finance markets with asymmetric information. Only integer prices and bids are admissible in contrast to De Meyer and Moussa Saley model. The zero-sum repeated games with incomplete information are considered modeling the bidding with countable sets of possible prices and bids. We show that, if the liquidation price of a share has a finite variance, then the sequence of total profits of Player 1 – the insider – in n-step games is bounded from above. This property distinguish the discrete model from the continuous De Meyer and Moussa Saley model and allows to consider the game with infinite number of steps without a beforehand given artificial restriction of the game duration. We construct explicitly the optimal strategies for this game. 

For constructing the optimal strategy of Player 1 (the insider) with arbitrary liquidation price of a share with finite variance we use the symmetric representation of distributions with fixed mean values as convex combinations of distributions with two-point supports and with the same mean values. The solutions for the games with two-point distributions was obtained in Domansky (2007). The optimal strategy of Player 1 generates a symmetric random walk of posterior expectations of liquidation price with absorption. The expected duration of this walk is equal to the initial variance of price. The guaranteed total gain of Player 1 (the value of the game) is equal to this expected duration multiplied with the fixed gain per step. The described results are contained in the preprint Domansky, Kreps (2009). 

(June-25th 2012) - Prof. Eilon Solan

Title: Repeated games with costly observations.

Abstract: In this seminar I will present a recent joint work with Ehud Lehrer on repeated games with costly observations. Those are two-player repeated games in which the players must pay a fixed cost in order to observe the action played by the other player. Our goal is to characterize the set of equilibrium payoffs in this model. Surprisingly the limit set of equilibrium payoffs, as the cost of observation goes to 0, is a strict subset of the set of feasible and individually rational payoffs. I will present all proofs and constructions.