Program


The program is available in pdf form here.

The registration, coffee breaks and lunches will take place on the ground floor of the MPI-INF building (E1.4) and the talks will be held in the Computer Science building of Saarland University (E1.3).


Sunday, September 27


19:00 Welcome Reception at Motel One



Monday, September 28


08:30 Commencement of registration

09:00 - 09:05 Opening Remarks

Session 1: Matching under Preferences (Chair: Paul Goldberg)
09:05 ­- 09:30
Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints

Naoyuki Kamiyama
09:30 ­- 09:55
Stable marriage and roommates problems with restricted edges: complexity and approximability

Ágnes Cseh and David F. Manlove
09:55 ­- 10:20
Pareto Optimal Matchings in Many-to-Many Markets with Ties

Katarina Cechlarova, Pavlos Eirinakis, Tamas Fleiner, Dimitrios Magos, David Manlove, Ioannis Mourtos, Eva Ocelakova and Baharak Rastegari
10:20 ­- 10:30
Effect of Strategic Grading and Early Offers in Matching Markets

Hedyeh Beyhaghi, Eva Tardos and Nishanth Dikkala
10:30 ­- 10:40
New Mechanisms for Pairwise Kidney Exchange

Hossein Esfandiari and Guy Kortsarz

10:40 ­- 11:10
Coffee break

11:10 - 12:10
Invited Talk: Herve Moulin

One dimensional mechanism design

12:10 - 14:00
Lunch break with warm buffet

Session 2: Cost Sharing (Chair: Alex Skopalik)
14:00 ­- 14:25
Cost-sharing Models in Participatory Sensing

Georgios Birmpas, Costas Courcoubetis, Ioannis Giotis and Evangelos Markakis
14:25 ­- 14:50
Further Results on Capacitated Network Design Games

Thomas Erlebach and Matthew Radoja
14:50 ­- 15:15
Cost-Sharing Scheduling Games on Restricted Unrelated Machines

Guy Avni and Tami Tamir
15:15 ­- 15:25
Resource Allocation Games with Multiple Resource Classes

Roy Ofer and Tami Tamir

15:25 ­- 16:00
Coffee break

Session 3: Auctions and Social Choice (Chair: Dimitris Fotakis)
16:00 ­- 16:25
Algorithmic Signaling of Features in Auction Design

Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell and Li-Yang Tan
16:25 ­- 16:50
Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design

Khaled Elbassioni, Kurt Mehlhorn and Fahimeh Ramezani
16:50 ­- 17:15
Equilibria of Plurality Voting: Lazy and Truth-biased Voters

Edith Elkind, Evangelos Markakis, Svetlana Obraztsova and Piotr Skowron
17:15 ­- 17:25
On Effective Affirmative Action in School Choice

Yun Liu



Tuesday, September 29


Session 4: Algorithmic Mechanism Design (Chair: Dov Monderer)
09:00 ­- 9:25
Auction Design with a Revenue Target

Paul Goldberg and Bo Tang
09:25 ­- 9:50
Efficient Money Burning in General Domains

Dimitris Fotakis, Dimitris Tsipras, Christos Tzamos and Emmanouil Zampetakis
09:50 ­- 10:15
Commitment in First-price Auctions

Yunjian Xu and Katrina Ligett
10:15 ­- 10:40
The Combinatorial World (of Auctions) According to GARP

Shant Boodaghians and Adrian Vetta

10:40 ­- 11:10
Coffee break

11:10 - 12:10
Invited Talk: Elias Koutsoupias

Multidimensional auctions: duality and virtual values

12:10 - 14:00
Lunch break with warm buffet

Session 5: Networking (Chair: Max Klimm)
14:00 ­- 14:25
On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

George Christodoulou, Alkmini Sgouritsa and Bo Tang
14:25 ­- 14:50
On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games

Maximilian Drees, Matthias Feldotto, Sören Riechers and Alexander Skopalik
14:50 ­- 15:15
Can Bandwidth Sharing Be Truthful?

Yukun Cheng, Xiaotie Deng, Yifan Pi and Xiang Yan
15:15 ­- 15:40
The Web Graph as an Equilibrium

Georgios Kouroupas, Evangelos Markakis, Christos Papadimitriou, Vasileios Rigas and Martha Sideri

15:40 - 16:10
Coffee break

Session 6: Routing and Fairness (Chair: Tobias Harks)
16:10 ­- 16:35
Excluding Braess's Paradox in Nonatomic Selfish Routing

Xujin Chen, Zhuo Diao and Xiaodong Hu
16:35 ­- 17:00
“Beat-Your-Rival” Routing Games

Gideon Blocq and Ariel Orda
17:00 ­- 17:25
Characterization and Computation of Equilibria for Indivisible Goods

Simina Brânzei, Hadi Hosseini and Peter Bro Miltersen
17:25­ - 17:35
On the Fair Subset Sum Problem

Gaia Nicosia, Andrea Pacifici and Ulrich Pferschy

19:30
Conference Dinner at Ratskeller




Wednesday, September 30


09:00 - 10:00
Invited Talk: Tim Roughgarden

Complexity Theory and Algorithmic Game Theory: Some New Connections

10:00 ­- 10:30
Coffee break

Session 7: Equilibrium Computation (Chair: Evangelos Markakis)
10:30 ­- 10:55
When Can Limited Randomness Be Used in Repeated Games?

Pavel Hubacek, Moni Naor and Jonathan Ullman
10:55 ­- 11:20
Settling Some Open Problems on 2-Player Symmetric Nash Equilibria

Ruta Mehta, Vijay Vazirani and Sadra Yazdanbod
11:20 - 11:45
Approximating Nash Equilibria in Tree Polymatrix Games

Siddharth Barman, Katrina Ligett and Georgios Piliouras
11:45 - 11:55
Computation of Fisher-Gale equilibrium by auction

Yurii Nesterov and Vladimir Shikhman

11:55 - 14:00
Lunch break with warm buffet