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.
Program
- 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
- Felix Brandt, TU Munich
- Roger Wattenhofer, ETH Zurich
Organizers
- Paul Duetting, London School of Economics
- Sven Seuken, University of Zurich
- Peter Widmayer, ETH Zurich
- Paolo Penna, ETH Zurich
Registration
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 |
Venue
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.