The 4th Symposium on Algorithmic Game Theory
October 17-19, 2011, Salerno - Amalfi Coast, Italy


SAGT 2011 Programme

Sunday, 16 October

19:00 Welcome Cocktail / Registration

Monday, 17 October

Invited talk

09:00 - 10:00 Bruno Codenotti. Computational Game Theory

10:00 - 10:30 Coffee break

Session 1: Auctions & Advertising

10:30 - 10:55 Asaph Arnon and Yishay Mansour. Repeated Budgeted Second Price Ad Auction
10:55 - 11:20 Yossi Azar and Ety Khaitsin. Prompt Mechanism for Ad Placement Over Time
11:20 - 11:45 Patrick Jordan, Mohammad Mahdian, Sergei Vassilvitskii and Erik Vee. The Multiple Attribution Problem in Pay-Per-Conversion Advertising
11:45 - 12:10 Marco Comi, Bhaskar Dasgupta, Michael Schapira and Venkatakumar Srinivasan. On Communication Protocols that Compute Almost Privately

12:10 - 14.00 Lunch

Session 2: Quality of Solutions

14:00 - 14:25 Noam Berger, Michal Feldman, Ofer Neiman and Mishael Rosenthal. Dynamic Inefficiency: Anarchy without Stability
14:25 - 14:50 Orit Arzi, Yonatan Aumann and Yair Dombb. Throw One's Cake --- and Eat It Too
14:50 - 15:15 Bruno Escoffier, Laurent Gourves and Jerome Monnot. The price of optimum in a matching game
15:15 - 15:40 Haris Aziz, Felix Brandt and Paul Harrenstein. Pareto Optimality in Coalition Formation

15:40 - 16:10 Coffee break

Session 3: Externalities

16:10 - 16:35 Dimitris Fotakis, Piotr Krysta and Orestis Telelis. Externalities among Advertisers in Sponsored Search
16:35 - 17:00 Elizabeth Bodine-Baron, Christina Lee, Anthony Chong, Babak Hassibi and Adam Wierman. Peer Effects and Stability in Matching Markets
17:00 - 17:25 Oskar Skibski. Steady Marginality: A Uniform Approach to Shapley Value for Games with Externalities

Tuesday, 18 October

Invited talk

09:00 - 10:00 Xiaotie Deng. Computation and Incentives of Competitive Equilibria in a Matching Market

10:00 - 10:30 Coffee break

Session 4: Mechanism Design

10:30 - 10:55 Elias Koutsoupias. Scheduling without payments
10:55 - 11:20 Shaili Jain and David Parkes. Combinatorial Agency of Threshold Functions
11:20 - 11:45 Zhenghui Wang and Lisa Fleischer. Lower Bound for Envy-free and Truthful Makespan Approximation on Related Machines
11:45 - 12:10 Navendu Jain, Ishai Menache, Joseph Naor and Jonathan Yaniv. A Truthful Mechanism for Value-Based Scheduling in Cloud Computing

12:10 - 14:00 Lunch

Session 5: Complexity

14:00 - 14:25 Panagiota Panagopoulou and Paul Spirakis. Random Bimatrix Games are Asymptotically Easy to Solve (A Simple Proof)
14:25 - 14:50 Vittorio Bilo' and Marios Mavronicolas. Complexity of Rational and Irrational Nash Equilibria
14:50 - 15:15 Krzysztof Apt and Evangelos Markakis. Diffusion in Social Networks with Competing Products

15:15 - 15:45 Coffee break

Session 6: Network games

15:45 - 16:10 Michael Brautbar and Michael Kearns. A Clustering Coefficient Network Formation Game
16:10 - 16:35 Long Tran-Thanh, Maria Polukarov, Archie Chapman, Alex Rogers and Nicholas R. Jennings. On the Existence of Pure Strategy Nash Equilibria in Integer-Splittable Weighted Congestion Games
16:35 - 17:00 Pascal Lenzner. On Dynamics in Basic Network Creation Games

17:00 Social Tour
20:30 Social Dinner

Wednesday, 19 October

Session 7: Pricing

09:30 - 09:55 Eyal Gofer and Yishay Mansour. Pricing Exotic Derivatives Using Regret Minimization
09:55 - 10:20 Ameya Hate, Elliot Anshelevich and Koushik Kar. Strategic Pricing in Next-hop Routing with Elastic Demands

10:20 - 10:45 Coffee break

Session 8: Routing games

10:45 - 11:10 Michael Schapira and Roee Engelberg. Weakly-Acyclic (Internet) Routing Games
11:10 - 11:35 Vincenzo Bonifaci, Mahyar Salek and Guido Schäfer. Efficiency of Restricted Tolls in Non-atomic Network Routing Games
11:35 - 12:00 Evdokia Nikolova and Nicolas Stier-Moses. Stochastic Selfish Routing