12th Day(s) on Computational Game Theory

September 29-30, 2022, University of Bremen

The 12th Day(s) on Computational Game Theory took place on Thursday, September 29 and Friday, September 30, at the University of Bremen. The workshop brought together researchers in Mathematics, Computer Science, Operations Research and Economics who were interested in algorithmic or computational aspects of game theory, social choice and related areas. It provided an opportunity to foster collaboration, present research and exchange ideas in an informal and relaxed atmosphere.

Keynote Talks

Efficient Algorithms for Information Design

Martin Hoefer, Goethe University Frankfurt, Germany

Collecting and sharing information is a key challenge for major service providers, including search engines, recommendation engines, and two-sided market platforms. In these domains, there is usually an informed "sender" (often a company or platform) who shares information in order to motivate uninformed "receivers" (e.g., potential customers) to take actions that are beneficial to the sender. Information design, also known as Bayesian persuasion, studies how the sender can disclose information optimally while accounting for the incentives that govern the behavior of the receivers.

Over the last decade, ideas from information design have found many applications in economics. The area offers interesting challenges for algorithmic work. In this talk, we outline our recent advances on efficient algorithms for basic pesuasion problems. We also touch upon extensions to restricted communication, dynamic arrival, and applications in selfish routing. Along the way, we mention open problems and opportunities for future research.

What is a Quantum Game?

Michael McGettrick, National University of Ireland, Galway, Ireland

We will present an overview of quantum games from its initial formulation (David Meyer, 1999, arXiv:quant-ph/9804010) to current developments. In much the same way that quantum computing has revolutionized (parts of) classical computing, quantum game theory is rapidly revolutionizing (classical) game theory. In our (non-exhaustive) presentation, we will describe in some detail some specific examples, so that it is hoped the audience will get an appreciation of what is fundamentally different about the quantum approach. Specifically, we will describe the PQ Penny Flip game, the quantum Prisoners Dilemma, and the celebrated CHSH game. We identify in each case the quantum nature of the game, the role of quantum operations (Unitary matrices), and the use of entangled quantum states as a resource. We see in some cases the quantum version of the classical game has different (Nash) equilibria, while in other cases the use of shared entanglement can increase the winning probability (in cooperative games). In the talk, no assumption is made of familiarity with quantum mechanics / physics, we present the theory mathematically. (In any case - essentially quantum mechanics is (arguably) probability theory using the L2 norm….)

Resource Buying Games with Load-Dependent Costs

Tami Tamir, Reichman University, Herzliya, Israel

In the basic setting of cost-sharing games, every resource has a fixed cost that is shared equally by its users. The talk will consider a more general setting: resource buying games with load-dependent costs and arbitrary cost-sharing. Under arbitrary cost-sharing, players do not only declare the resources they select to use, but they also declare a payment for each such resource. If the total payments declared for a resource cover its cost, then the resource is activated; otherwise it remains unavailable to the players. We will analyze the equilibrium existence and computation in various classes of these games. In addition, we will see how a simple natural constraint on the declared payments can be used to significantly reduce the equilibrium inefficiency.
Based on joint work with Eirini Georgoulaki and Kostas Kollias

Program

Thursday, September 29, MZH 1470

12:30	Women's Lunch
13:45	Welcome
13:55	Session Chair: Alexander Skopalik
	First Keynote Talk Efficient Algorithms for Information Design Martin Hoefer, Goethe University Frankfurt, Germany
14:40	Coffee Break, Group Photo
15:25	Session Chair:
	d-fine Presentation
	Best of Both Worlds: Agents with Entitlements Marco Schmalhofer, Goethe-University Frankfurt, Germany
	Nash Social Welfare for 2-value Instances Golnoosh Shahkarami, Max Planck Institute for Informatics, Saarbruecken, Germany
16:15	Coffee Break
16:35	Session Chair: Pascal Lenzner
	Seniorities and Minimal Clearing in Financial Network Games Lisa Wilhelmi, Goethe University Frankfurt, Germany
	Public Signals in Network Congestion Games Tim Koglin, Goethe University Frankfurt, Germany
	Price of Anarchy for Parallel Link Networks with Generalized Mean Objective Pieter Kleer, Tilburg University, The Netherlands
17:35	Coffee Break
17:50	Session Chair: Anja Schedel
	Creation Games for Undirected Wireless Networks Merlin de la Haye, Hasso Plattner Institute, Potsdam, Germany
	Topological Distance Games Martin Bullinger, Technical University of Munich, Germany
18:30	Ending / Transfer to Restaurant Ristorante Pizzeria Luigi, Martinistraße 12-16, 28195 Bremen
19:30	Dinner

Friday, September 30, MZH 1470

8:45	Session Chair: Daniel Schmand
	Second Keynote Talk What is a Quantum Game? Michael McGettrick, National University of Ireland, Galway, Ireland
9:30	Coffee Break
9:45	Session Chair: Marc Schröder
	Impartial Selection with Additive Guarantees via Iterated Deletion Javier Cembrano, Technische Universität Berlin, Germany
	Rejection-Proof Mechanisms for Multi-Agent Kidney Exchange Danny Blom, Eindhoven University of Technology, The Netherlands
	Strategic Facility Location with Clients that Minimize Total Waiting Time Simon Krogmann, Hasso Plattner Institute, Potsdam, Germany
10:45	Coffee Break
11:00	Session Chair: Tim Oosterwijk
	Multilinear Formulations for Computing Nash Equilibria of n-person Noncooperative Games Akshay Gupte, School of Mathematics, Edinburgh, United Kingdom
	Generalized Nash Equilibrium Problems with Mixed-Integer Variables Julian Schwarz, University of Augsburg, Germany
11:40	Coffee Break
11:55	Session Chair: Ruben Hoeksma
	Machine-Learned Prediction Equilibrium for Dynamic Traffic Assignment Michael Markl, University of Augsburg, Germany
	The Secretary Problem with Independent Sampling Tim Oosterwijk, Vrije Universiteit Amsterdam, The Netherlands
12:35	Lunch
13:35	Session Chair: Marc Uetz
	Third Keynote Talk Resource Buying Games with Load-Dependent Costs Tami Tamir, Reichman University, Herzliya, Israel
14:20	Ending

Venue

The workshop took place in the MZH Building of the University of Bremen, Bibliothekstraße 5, room 1470. The best way to reach it is by public transport to the station "Universität/Zentralbereich" or "Universität-Süd". From the central station, you can take the tram lines 6 and 6E and the bus lines 630 and 670.

Acommodation

The 7things hotel is located directly at the campus. Note: At 7things, you are eligible for a cheaper university rate for the purpose of visiting the workshop. For that, you just need a confirmation of participation (e.g. our response mail). This is only available when booking by phone.

Other than that, you can choose one of the many hotel options near the city center.

With the friendly support of