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, 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 management programs with this intriguing, interdisciplinary area.

The seminar will take place on Wednesday, February 22nd, in Melamed Hall, Shenkar building, Tel-Aviv University. For the campus map, click here.

9:30 - 10:00: Coffee

10:00 - 10:45: Gil Kalai. "Social Choice: from Collective Irrationality to Indeterminacy, Noise Sensitivity and Chaos".

10:50 - 11:35: Uri Nadav. "Efficient Contention Resolution Protocols for Selfish Agents".

11:35 - 12:05: Coffee break

12:05 - 12:50: Gal Oestreicher-Singer . "Recommendation Networks and the Long Tail of Electronic Commerce".

12:50 - 14:00: Lunch

14:00 - 14:45: Ittai Abraham. "Distributed Computing Meets Game Theory: Lower Bounds on Implementing Robust and Resilient Mediators".

14:50 - 15:35: Ron Lavi. "Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity".

"Social Choice: from Collective Irrationality to Indeterminacy, Noise Sensitivity and Chaos". Gil Kalai
We will consider social welfare functions (SWFs) for N individuals (voters) and M alternatives. Those are functions which associate to every profiles of individual order preference-relations on the alternatives, a social preference relation. We will consider a hierarchy of properties, the first is well known. 1) Irrationality of the social preference: "Undesirable outcomes can happen" When there are more than 3 alternatives and the SWF is given by the pairwise majority rule the social outcome can be cyclic: This goes back to Condorcet and a famous result by Arrow asserts that the conclusion cannot be avoided under very general conditions. We will continue by informally describing stronger properties: 2) Indeterminacy: "Everything can happened". Every preference relation can occur as the social preferences, when there are sufficiently many voters. It turns out that this property holds if the maximum individual Shapley value tends to zero. 3) Stochastic indeterminacy: "Everything will happen." If the voters profile is random (chosen uniformly) then every social preference has a probability to occur which is bounded away from zero. It turns out that this property holds if the maximum individual Banzhaf values tends to zero. Next we describe a dichotomy between noise stable and noise sensitive SWFs. Majority is an example of a noise stable SWF. Noise sensitive SWFs can be described in several equivalent ways one of which is an extreme form of indeterminacy: 4) Social chaos : "Everything is equally likely to happen." For random voter profiles when the number of voters tends to infinity all preference relations occur with the same probability.

"Efficient Contention Resolution Protocols for Selfish Agents". Uri Nadav

We seek to understand behavior of selfish agents accessing a broadcast channel. In particular, we consider the natural agent utility where costs are proportional to delay. Access to the channel is modeled as a game in extensive form with simultaneous play. Standard protocols such as Aloha are vulnerable to manipulation by selfish agents. We analyze the symmetric equilibrium strategy in such a setting and show that the appropriate transmission probabilities are O(1/\sqrt{n}), when n agents are competing. This clearly implies exponentially long delays. We give a very simple protocol for the agents that is in Nash equilibrium and --- other than with exponentially negligible probability - all n agents will successfully transmit within O(n) steps.
Joint work with Amos Fiat and Yishay Mansour.

"Recommendation Networks and the Long Tail of Electronic Commerce". Gal Oestreicher-Singer

My research program studies how network structures affect demand and revenue patterns in electronic commerce. The results I will present are based on 28 daily observations of an evolving recommendation network on Amazon.com comprising between 220,000 and 260,000 products. I associate the distribution of demand and revenue for over 200 product categories with the average influence of the recommendation network on each category’s products. The influence of the network on every product is quantified using an adapted version of Google's PageRank algorithm; the demand and revenue distributions of each category are characterized by constructing Lorenz curves and measuring their associated Gini coefficients. My first set of results demonstrates that categories whose products are more central in the recommendation network consistently feature more evenly distributed demand between popular and niche products. These empirical results provide a new explanation for the widely documented "long tail" of electronic commerce. In addition, I establish how specific network properties which include the degree of clustering and assortative mixing within categories are related to demand and revenue patterns. My second set of results, based on a structural peer-effects model, isolate the extent to which the explicit presence of recommendation hyperlinks alters demand at the individual product level. This model separates this direct effect from other endogenous variation caused by product complementarity and shared characteristics, and shows how the influence of a product’s local network varies across categories and by vintage. My research highlights the importance of a product’s “network position” as a determinant of outcomes in electronic markets, and provides the first scientific evidence of its impact on ecommerce demand and revenue trends.

"Distributed Computing Meets Game Theory: Lower Bounds on Implementing Robust and Resilient Mediators". Ittai Abraham

A mediator can help non-cooperative agents obtain an equilibrium that may otherwise not be possible. We prove lower bounds that match upper bounds on the ability of rational agents to obtain the same equilibrium without a mediator, simply by engaging in non-binding pre-play communication, known as ``cheap talk''. In this talk I will focus on our lower bounds results. Our results expose an intricate reciprocal relation between game theory, cryptography and distributed computing.
Joint work with Danny Dolev and Joe Halpern

"Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity ". Ron Lavi

We consider job scheduling for makespan minimization on $m$ unrelated machines, in the context of algorithmic mechanism design. This is a multidimensional domain, and the only currently known truthful mechanisms for this domain are VCG-based. Unfortunately, these manage to provide only an $O(m)$ approximation guarantees. (even the existence of a near-optimal truthful mechanism is not known). We study a special case of this problem, where the processing time of a job on each machine may either be ``low'' or ``high'', and the low and high values are public and job-dependent. This preserves the multidimensionality of the domain, and generalizes the "restricted-machines" setting in scheduling. We obtain two results. First, we give a general technique to convert {\em any} $c$-approximation algorithm to a $3c$-approximation truthful-in-expectation mechanism. Second, when the low and high values are the same for all jobs (which is still a multidimensional domain), we devise a deterministic $2$-approximation truthful mechanism. These are the first truthful mechanisms with non-trivial performance guarantees for a multidimensional scheduling domain. Our constructions do not utilize or rely on explicit price definitions to prove truthfulness; instead we design algorithms that satisfy cycle monotonicity, which may be viewed as the parallel of value monotonicity for multidimensional domains. Although value monotonicity has been used extensively and successfully to design truthful mechanisms in single-dimensional domains, we are not aware of works that leverage cycle monotonicity in the multidimensional setting, and our methods and analyses may shed new light on its potential usefulness.
Joint work with Chaitanya Swamy.

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

Noam Nisan. Hebrew University. email: noam at cs.huji.ac.il

Moshe Tennenholtz. Technion - Israel Institute of Technology. email: moshet@ie.technion.ac.il