The Fifth Israeli Computational Game Theory Seminar was held today in Microsoft R&D center in Herzliya. This was a pretty large affair with about 140 registered participants from all over Israel (and a few from abroad), but with quite a friendly feeling as the Israeli community is pretty closely knit. There were five talks that were chosen by the organizers (Moshe Tennenholtz, Michal Feldman, and myself) in an attempt to optimize interest to the audience while maintaining some diversity in terms of research areas, speaker affiliation, etc.
The first talk was by Dov Samet, a game-theorist/economist/decision-theorist, who talked about a knowledge-based formalization of “the sure thing principle“. This principle states that if you will do X if you know Y and will do X if you know not(Y) then you will do X without knowing about Y. This was formalized and shown to be equivalent to another formalization in terms of “kens” (a formal notion capturing bodies of knowledge). Most interesting, a generalization of the latter turns out to be equivalent to not being able to “agree to disagree” in a knowledge-based abstraction a-la Aumann’s classical paper. This talk was somewhat out of the usual scope of the AGT community who, like most of the TCS community, are not really into the “knowledge” formalisms.
The second talk was by Seffi Naor who talked about best-response dynamics in network creation games. He studied a game in which each player needs to acquire a path in a graph from his origin node to a common root, where each edge has a cost, and if several players share an edge then they split its cost evenly between them. It is known that this game has a price of anarchy of n but price of stability 1 (i.e. there are both extremely good and extremely bad Nash equilibria, in terms of the total social cost). Seffi asked how good is the equilibrium that the best-response dynamics will converge to? This of course depends on the starting point and he considered the “empty” starting point for which he was able to show a polylog loss of efficiency relative to the optimum.
The third talk was by Noga Alon who considered what happens in a win-loose zero-sum game when one player gets to play after seeing some information regarding the realization of the mixed strategy of the other. Two models were considered, and in both of them (different) sharp thresholds were shown: when the number of bits of information leaked is small, there is mild loss of value, and at a certain point the loss becomes severe.
The forth talk, by Svetlana Olonetsky, considered mechanisms that are both incentive compatible and envy-free. Her model considered allocations of heterogeneous items among agents whose valuations are additive over the items, but only as long as at most k items are obtained. While each of these two requirements (incentive compatibility and envy-freeness) can be achieved separately it is still open whether they can be achieved by the same mechanism, and partial results leading to this open problem were shown.
The final talk was by Joe Halpern who suggested several new equilibrium concepts that go beyond the Nash equilibrium to address issues motivated by computational game theory. The first takes into account not just selfish deviations by the players but also worst-case deviations by some players (in coalition), in which model he can apply the secure multi-party computation cryptographic protocols. (He also suggested to think about the fact that sometimes we have some “obedient” non-rational players who just do as told, perhaps helping the whole system function well.) The second concept provides a rather general framework for capturing the complexity of computation as cost within the game. The third, which he only mentioned briefly, models the fact that players may not even be fully aware of the game when they play it.
While these talks are hardly a representative sample of AGT research, I was still left with a feeling that the research area is widening. While just a few years ago much of the AGT research used a rather small number of categories and models (e.g. price of anarchy; complexity of equilibrium computation, incentive-compatible mechanism design), the scope is now widening with an influx of new models and issues. I like this exploration trend, but at some point the community will likely need to re-focus on a small set of basic and robust notions.
Turing's Invisible Hand 
Leave a Reply