3rd German Day on Computational Game Theory
March 3-4, 2016, RWTH AachenOMS
The 3rd German Day on Computational Game Theory took place on Friday, March 4th, 2016, at RWTH Aachen University. This international event was preceded by a reception and an open problems session in the afternoon of Thursday 3rd. Keynote speakers were
- Paul Dütting (ETH Zürich), and
- Rahul Savani (University of Liverpool).
The aim was to bring together researchers who are interested in algorithmic or computational aspects of game theory, social choice, and related areas. The aim of this event was to provide an opportunity to foster collaboration, present research and exchange ideas at an informal level.
There was no registration fee.
The open problems session on Thursday and the workshop on Friday took place in Kackertstraße 7, 52072 Aachen (see here). Talks took place in room B037 (ground floor). The reception, open problems session and coffee breaks were located in room B234 (second floor). There was a shuttle-service from Aachen Hbf (the main station) and RWTH Guesthouse to Kackertstraße 7 leaving the main station at 16:15 and 16:30. If you wish to utilize the shuttle service please write a short note to Daniel Schmand. If you use public transport, best is to get off at "Aachen West"(10-15 min walk to the venue, local trains from Mönchengladbach/Düsseldorf), "Wildbach" (5min walk, a lot of buses) or "Kackertstraße" (diretly in front of the venue, occational bus service). For more information see here.
|16:45 - 17:15||Reception - Room B234|
|17:15 - 18:45||Open Problem Session - Room B234 / B227|
|18:45 - 19:15||Walk / Drive to Restaurant Macaroni, Schmiedstraße 24|
|19:15 - ???||Dinner - Restaurant Macaroni|
|9:30 - 9:40||Opening - Room B037|
|9:40 - 10:30||Rahul Savani||University of Liverpool||The Computational Power of Pivoting and Local Improvement Algorithms|
|10:30 - 11:00||Coffee Break - Room B234|
|11:00 - 11:25||Jasper de Jong||University of Twente||Efficiency of Equilibria in Uniform Matroid Congestion Games|
|11:25 - 11:50||Daniel Schmand||RWTH Aachen University||Competitive Packet Routing with Priority Lists|
|11:50 - 12:15||Thomas Kesselheim||MPI Saarbrücken and Saarland University||Mechanisms with Unique Learnable Equilibria|
|12:15 - 13:30||Lunch Break - Room B234|
|13:30 - 13:50||Alexander Skopalik||Paderborn University||On the SFB 901 and the Market for Service Compositions|
|13:50 - 14:40||Paul Dütting||ETH Zürich||Algorithms against Anarchy|
|14:40 - 15:10||Coffee Break - Room B234|
|15:10 - 15:35||Matthias Feldotto||Paderborn University||Towards Approximate Nash Equilibria in Cost Sharing Games|
|15:35 - 16:00||Oliver Schaudt||University of Cologne||
Revenue maximization in Stackelberg Pricing Games: Beyond the combinatorial setting
|16:00 - 16:25||Marc Schroeder||Maastricht University||Optimal Price Caps in Congested Networks|
Paul Dütting: Algorithms against Anarchy
Which algorithms when combined with simple payment rules, such as first-price payments, yield mechanisms whose equilibria are close to optimal? We address this question by providing a tight characterization of a (possibly randomized) mechanism's Price of Anarchy provable via smoothness that applies in single-parameter settings. The characterization assigns a unique value to each allocation algorithm; this value provides an upper and a matching lower bound on the Price of Anarchy of a derived mechanism provable via smoothness. The characterization also applies to the sequential or simultaneous composition of single-para meter mechanisms. Importantly, the factor that we identify is typically not in one-to-one correspondence to the approximation guarantee of the algorithm. Rather, it is usually the product of the approximation guarantee and the degree to which the mechanism is loser independent.
We apply our characterization to show the optimality of greedy mechanisms for single-minded combinatorial auctions, whether these mechanisms are polynomial-time computable or not. We also use it to establish the optimality of a non-greedy, randomized mechanism for independent set in interval graphs and show that it is strictly better than any other deterministic mechanism.
Joint work with Thomas Kesselheim
Rahul Savani: The Computational Power of Pivoting and Local Improvement Algorithms
We will discuss three algorithms for solving games. All three algorithms tend to be work well in practice, but actually can solve any problem in PSPACE. Two of the algorithms are pivoting methods: the simplex method for solving LPs (and thus zero-sum games) and the Lemke-Howson algorithm for finding an equilibrium of a bimatrix game. The last algorithm is strategy improvement, which is a local improvement algorithm that can be used to solve a number of two-player infinite games used in verification, such as parity games. The talk will introduce the games, algorithms, and relevant complexity classes, and then give a high-level overview of the PSPACE-hardness results.
Based on joint work with John Fearnley, Paul Goldberg, and Christos Papadimitriou.
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.
The workshop is jointly organized by
- Britta Peis (Management Science, RWTH Aachen University)
- Alexander Skopalik (Heinz Nixdorf Institut, Universität Paderborn)
and is supported by the CRC 901 "On-The-Fly Computing" (see here).