4th Day on Computational Game Theory

February 16-17, 2017, ETH Zurich

This workshop will bring together researchers in Computer Science, Operations Research, and Economics who are interested in algorithmic or computational aspects of game theory, social choice, and related areas. It provides an opportunity to foster collaboration, present research, and exchange ideas at an informal level.


  • February 16, 5:00pm-late: Reception and lightning talks (with open problems), afterwards dinner
  • February 17, 9:00am-4:50pm: Two keynote talks, 12 contributed talks

Confirmed keynote speakers



The registration is now closed.

Keynote Talks

On the Tradeoff Between Efficiency and Strategyproofness, Felix Brandt, TUM

Two fundamental notions in microeconomic theory are efficiency–no agent can be made better off without making another one worse off–and strategyproofness–no agent can obtain a more preferred outcome by misrepresenting his preferences. The conflict between these two notions is already apparent in Gibbard and Satterthwaite’s seminal theorem, which states that the only single-valued social choice functions that satisfy non-imposition–a weakening of efficiency–and strategyproofness are dictatorships. This talk will be concerned with efficiency and strategyproofness in the context of social decision schemes, i.e., functions that map a preference profile to a probability distribution (or lottery) over a fixed set of alternatives. Depending on how preferences over alternatives are extended to preferences over lotteries, there are varying degrees of efficiency and strategyproofness. I will dicuss positive results for random serial dictatorship and maximal lotteries as well as a number of impossibility theorems, one of which was recently shown using computer-aided solving techniques.

Metric Matching: Cheap or Stable … or Fast?, Roger Wattenhofer, ETH

My talk is about matchings in a metric space. In the first part, we connect two classic approaches in matching, (i) a global optimization angle à la Edmonds, and (ii) a local selfish angle à la Gale and Shapley. We analyze the price of anarchy of metric matching when combining the two. The second part of the talk deals with an online version of metric matching. Consider an online gaming platform supporting two-player games such as Chess or Street Fighter 4. The platform tries to find a suitable opponent for each player, minimizing two criteria: (i) matching similar players, so that the game is challenging for both players; and (ii) the waiting time until a player is matched and can start playing since waiting is boring. It turns out that these two minimization criteria are often conflicting. To cope with this challenge, we must allow the platform to delay its service in a rent-or-buy manner.

The first part of my talk is based on an ESA 2015 paper with Yuval Emek and Tobias Langner. The second part is based on an STOC 2016 paper with Yuval Emek and Shay Kutten, and on unpublished work with Yuyi Wang and others.

Confirmed program

Thursday Feb 16 (ETH Zurich, CAB Building, Room H52, Click here for a map)

17:00-17:30 Apero
17:30-18:30 Lightning Talks (with Open Problems)
18:45-19:20 Transfer to Restaurant (At 19:00 Tram 6 to Kirche Fluntern, then at 19:15 Bus 751 to Tobelhof)
19:30-??? Dinner at Restaurant Chaesalp

Friday Feb 17 (ETH Zurich, CAB Building, Room G56, Click here for a map) [Program as PDF]

9:00-9:05 Opening
9:05-09:50 First Keynote Talk
On the Tradeoff between Strategyproofness and Efficiency
Felix Brandt, TUM
09:50-10:10 A Characterization of Serial Dictatorship Mechanisms with Reservation Prices
Bettina Klaus, UNIL
10:10-10:40 Coffee Break
10:40-11:00 Online Contention Resolution Schemes: A Framework for Online Selection Problems
Rico Zenklusen, ETH
11:00-11:20 Posted Prices, Smoothness, and Combinatorial Prophet Inequalities
Thomas Kesselheim, MPI
11:20-11:40 Decentralized Dynamics and Fast Convergence in the Assignment Game
Barry Pradelski, ETH
11:40-12:00 Best-response Dynamics in Combinatorial Auctions with Item Bidding
Paul Dütting, LSE
12:00-13:15 Lunch Break (on your own)
13:15-14:00 Second Keynote Talk
Metric Matching: Cheap or Stable … or Fast?
Roger Wattenhofer, ETH
14:00-14:20 Competitive Packet Routing with Priority Lists
Laura Vargas Koch, RWTH
14:20-14:40 Equilibrium Computation in Atomic Splittable Congestion Games
Veerle Timmermans, Maastricht
14:40-15:00 Congestion Games with Complements
Matthias Feldotto, Paderborn
15:00-15:30 Coffee Break
15:30-15:50 Behavioural Foundations of Dynamics
Heinrich Nax, ETH
15:50-16:10 Efficient Best-response Computation for Strategic Network Formation
Pascal Lenzner, Potsdam
16:10-16:30 Smoothness for Risk Averse Players
Bojana Kodric, MPI
16:30-16:50 Reasoning Agents in Decision Making
Erman Acar, Mannheim


The workshop will take place in the CAB Building of ETH Zurich. The best way to reach ETH/CAB is by public transport. From the airport you can either take a train to the main station or the tram (line 10) to ETH/Universitaetsspital. From the train station you can walk to Central and then take the Polybahn up to ETH.


Previous Workshops

The 3rd German Day on Computational Game Theory took place on March 3-4, 2016 at RWTH Aachen.
The 2nd German Day on Computational Game Theory took place on February 10-11, 2015 at TU Berlin.
The 1st German Day on Computational Game Theory took place on February 13, 2014 at the Heinz-Nixdorf-Institute at Paderborn University.