SAGT 2009

Yesterday I returned from the Symposium on Algorithmic Game Theory (SAGT) that was held in Cyprus.   This is the second year of SAGT which is the newest addition to the set of conferences that are targeted at the interface between computer science and game theory and economics: EC and WINE (as well as the related and more specific COMSOC).  SAGT differentiates itself from the others in two respects.  First there is the geographic dimension: SAGT is European, while EC is North-American, and WINE rotates between America, Europe, and Asia.  Second, SAGT is unashamedly theoretical: even its name has the theoretical “algorithmic” and “game theory” while the others have applied leanings,  “Internet” for WINE and “electronic commerce” for EC, despite their dominant theoretical flavor.  SAGT dates are strategically chosen with respect to this eco-system of conferences, in particular its submission deadline is slightly after EC acceptance notifications.  Given that EC has turned into quite a strong conference with very low acceptance rates, this opens the way for SAGT to develop into a strong conference as well.  I understand from people who have been in both the first and second SAGT that indeed the scientific level this year seems significantly higher than last year.

I have to admit that at first I feared that I’ll find weak papers that answered un-interesting questions in un-illuminating ways.  While I can’t say that non of the talks that I’ve heard falls into this category,  I was quite positively surprised.  It seems that many of the papers were specialized rather than weak, targeted quite properly at Algorithmic Game Theorists.

As an example, take the session on “solution concepts” in which several alternatives to Nash equilibrium were explored:

• The Computational Complexity of Weak Saddles (by Felix Brandt, Markus Brill, Felix Fischer and Jan Hoffmann)  which explored Shapely’s alternative  to mixed-Nash equilibrium, a solution concept that leaves sets of strategies for each player.
• Partition Equilibrium (by Michal Feldman and Moshe Tennenholtz) that explores deviations by coalitions where the  coalition structure is exogenously given.
• Learning and Approximating the optimal strategy to commit to (by Joshua Letchford, Vincent Conitzer and Kamesh Munagala) that considers a Stackelberg version of a game, where one player may commit in advance to a mixed strategy.
• On the Complexity of iterated weak dominance in constant sum games (by Felix Brandt, Markus Brill, Felix Fischer and Paul Harrenstein) that studied iterated removal of dominated strategies, but using the tricky notion of weak dominance rather than the more robust notion of strict dominance.

These variants may all be too specialized for someone who just wants to plainly use game theory, but for people working inside the field they are illuminating.  Personally, as a fan of alternative notions of equilibrium, all of these papers seemed well motivated to me, and while I can’t say that I found any of the results to be earth-shattering, I did find them interesting.

Invited talks were given by Elias Koutsoupias (Approximate price of anarchy and stability), Mihalis Yannakakis (Computational aspects of equilibria), and myself (Google’s auction for TV ads).  Unfortunately due to my travel constraints, I missed these talks (well, except mine).  The social program included an excursion to several tourist attractions, braving an unusual heat wave (35 degrees Celsius on the bus).  The banquet compensated  for the heat with an excellent seafood meze.  The whole conference was very well organized by PC chair Marios Mavronicolas, and local arrangements chair Vicky Papadopoulou.

Next year, SAGT is scheduled to be in Athens around the same time of year (mid October), with its submission deadline shortly after EC acceptance notifications.

Advertisement