Impressions from SAGT 2011
I just came back a few days ago, after spending 10 days in Italy and attending SAGT 2011, the fourth Symposium on Algorithmic Game Theory. As for Italy — the stories of its beauty and of its delicious food (and great cheap wine) turned out to be very true; in addition, we (that is Ety Khaitsin from TAU, who traveled with me, and myself) enjoyed really excellent weather throughout our stay, which made things even nicer.
The conference itself was located in Amalfi, a small and beautiful town on the coast a little southeast of Naples (called Amalfi Coast), and consisted of two and a half days of lectures, including two invited talks. The first invited talk, given by Bruno Codenotti and opening the first day of lectures, concentrated mainly on the very basics of GT and AGT, touching upon more advanced complexity issues towards the end. The second, given in the second day by Xiaotie Deng, was concerned with equilibria in matching markets, and compared this setting to the more studied (at least in AGT) setting of auctions. Besides these talks, 26 papers were presented. As seems to be the tradition, the papers in SAGT tend more to the theoretical perspective (i.e. studying things mainly through percise mathematical models and their analysis, rather than conducting experiments) compared to other similar conferences like WINE. My impression, which (at least judging by my conversations with some of the other attendees) was shared by many others as well, was that despite of the somewhat-small venue, the level of the accepted works was quite high. To mention but a few out of the many papers and presentations that I found interesting:
- Ety Khaitsin’s work on Prompt Mechanism for Ad Placement Over Time, co-authored with Yossi Azar, concerned with the problem of scheduling ads publishing in a series of publication dates so as to maximize welfare, while dealing with deadlines and size constraints.
- Paul Harrenstein’s work on Pareto Optimality in Coalition Formation, co-authored with Haris Aziz and Felix Brandt, concerned mainly with the problem of finding Pareto optimal divisions to coalitions in several classes of hedonic coalition formation games.
- Jonathan Yaniv’s work on A Truthful Mechanism for Value-Based Scheduling in Cloud Computing, co-authored with Navendu Jain, Ishai Menache and Joseph (Seffi) Naor, that shows such a schdueling mehanism that maximizes the total value and deals with parallelism bounds and different values for different completion times.
- Vangelis Markakis’s work on Diffusion in Social Networks with Competing Products, co-authored with Krzysztof Apt, that describes an interesing model of how people choose products in social networks, with characterization of networks in which a universal adoption of a product is possible or inevitable.
- Ameya Hate’s work on Strategic Pricing in Next-Hop Routing with Elastic Demands, co-authored with Elliot Anshelevich and Koushik Kar which considers a network with a single sink, to which players want to send traffic, and in which players charge each other for transferring traffic.
In the evening of the second day of lectures, we went on a social tour in Amalfi, visiting the museum and the duomo — St. Andrew’s cathedral — guided by a local and very lively tour guide. The town of Amalfi turns out to have a long and rich history, once being one of the most important port cities in Italy, and its cathedral (including a very impressive crypt, said to have relics of St. Andrew himself) is strikingly beautiful. The evening ended with a social dinner, which seemed to have quickly gained the concensus of being a very strong candidate for the best conference dinner ever. 
After the seemingly-endless line of excellent (mostly fish-based) courses, arrived the amazing dessert shown on the right, which was made complete with great italian coffee and some local limoncello.
The conference officially closed at noon of the next day, where it was announced that the next SAGT will be held in Spain. So if you missed SAGT this time around, there is certainly something to look forward to in the next year.
(And just to add a shameless promotion of my own paper from the conference: Throw One’s Cake — and Eat It Too)