Recent years have seen a flurry of research activity on problems on the border of computer science and game-theory / economics. Research in this area includes (but is not limited to): algorithmic mechanism design, computational issues in games, and incentives in computer networks and the Internet. This field has been of particular interest to quite a few Israeli research groups, encompassing several universities throughout the country.

This seminar seeks to bring together active researchers in this developing field. The goals of the seminar are to promote the exchange of ideas between local researchers, to encourage further collaboration between the different groups, and to familiarize researchers from computer science, economics, mathematics, and business programs with this intriguing, interdisciplinary area.

We hope that this seminar will be the first in a series of meetings to be held during the upcoming academic year, 2006-2007.

The seminar will take place on Wednesday, October 18th, in the Schreiber building, room #6, at Tel-Aviv University.

9:30 - 10:00: Coffee

10:00 - 10:45: Noam Nisan. "Approximation Mechanisms and Characterizations of Implementable Functions".

10:45 - 11:30: Moshe Tennenholtz. "Programs and Mediators".

11:30 - 12:00: Coffee break

12:00 - 12:45: Ron Holzman. "Aggregation of Binary Evaluations".

12:45 - 14:00: Lunch

14:00 - 14:45: Yishay Mansour. "Learning, Regret Minimization, and Equilibria".

14:45 - 15:30: Michal Feldman. "Strong Equilibrium and the Price of Anarchy".

"Approximation Mechanisms and Characterizations of Implementable Functions". Noam Nisan
The clash between computational constraints and incentive constraints is at the center of algorithmic mechanism design. This clash appears whenever one wishes to implement a computationally-hard allocation rule (or, more generally, social choice function). In such cases, approximations or heuristics are computationally required, but it is not at all clear whether these can be made incentive compatible.

This talk will demonstrate many of the issues involved by looking at depth at a representative problem: multi-unit auctions.

The talk will have the favor of a survey and is based on my previous joint work with Amir Ronen, Ilya Segal, Ahuva Mu'alem, Ron Lavi, and Shahar Dobzinski.

"Programs and Mediators".Moshe Tennenholtz
Programs and Mediators This talk is a brief introduction to our work on program equilibrium and mediated equilibrium. We show that when agents' strategies are computer programs which are executed on a given computing device, one can exploit the Von-Neumann dual role of computer programs. We show that this idea implies that the set of program equilibrium payoffs of a game coincides with the set of feasible and individually rational payoffs of it. Computers which run such computer programs can be seen as action mediators, who can act on behalf of agents based on their instructions. We develop a theory of action mediators and show that they significantly enrich the set of situations where we can obtain stability against correlated deviations by coalitions. Moreover, we introduce the study of routing mediators, in which the above mediators may possess information also about the behavior of agents who do not give the mediator the right of play. We study the relationships between the power of different routing mediators in establishing correlated strong equilibrium. We show a natural class of routing mediators that allow to implement fair and efficient outcomes as a correlated super-strong equilibrium in a very wide class of games.

Based on joint work with Dov Monderer and Ola Rozenfeld.
The talk refers to the following papers.
M. Tennenholtz , Program Equilibrium, Games and Economic Behavior, 2004.
D. Monderer and M. Tennenholtz, Strong Mediated Equilibrium, AAAI 2006.
O. Rozenfeld and M. Tennenholtz, Routing Mediators, to appear in IJCAI 2007.

"Aggregation of Binary Evaluations". Ron Holzman
We study a general aggregation problem in which a society has to determine its position (yes/no) on each of several issues, based on the positions of the members of the society on those issues. There is a prescribed set of feasible evaluations, i.e., permissible combinations of positions on the issues. This framework for the theory of aggregation was introduced by Wilson and further developed by Rubinstein and Fishburn. Among other things, it admits the modelling of preference aggregation (where the issues are pairwise comparisons and feasibility reflects rationality), and of judgment aggregation (where the issues are propositions and feasibility reflects logical consistency). We characterize those sets of feasible evaluations for which the natural analogue of Arrow's impossibility theorem holds true in this framework.

(Joint work with Elad Dokow)

"Learning, Regret Minimization, and Equilibria". Yishay Mansour

"Strong Equilibrium and the Price of Anarchy". Michal Feldman
A strong equilibrium (Aumann 1959) is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy to be the ratio of the worst case strong equilibrium to the social optimum. In contrast to the traditional price of anarchy, which quantifies the loss incurred due to both selfishness and lack of coordination, the strong price of anarchy isolates the loss originated from selfishness from that obtained due to lack of coordination. We study the strong price of anarchy in two settings, one of job scheduling and the other of network creation. In the job scheduling game we show that for unrelated machines the strong price of anarchy can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the strong price of anarchy is at most $2$. In both cases we show that a strong equilibrium always exists, except for a well defined subset of network creation games.

(Joint work with Nir Andelman and Yishay Mansour)

Michal Feldman. Hebrew University of Jerusalem. email: mfeldman at cs.huji.ac.il

Yishay Mansour. Tel-Aviv University. email: mansour at cs.tau.ac.il