3rd German Day on Computational Game Theory

 

March 3-4, 2016, RWTH Aachen

Urheberrecht: © OMS

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.

 

Registration

There was no registration fee.

 

Venue

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.

 

Schedule

Thursday

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

Friday

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

 

Keynote Speakers

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.

 

History

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.

 

Organizers