ACiD WORKSHOP: Games and Graphs

ACiD WORKSHOP: Games and Graphs

Date: Wednesday 1 May 2024

Venue: MCS 2068 (Mathematical Sciences & Computer Science Building)

Organisers: Daniel Paulusma and Michelle Zhang

---

Schedule

11.30-12.15	Péter Biró	Stable solutions for kidney exchanges
12.15-13.00	Gergely Csáji	Computational complexity of k-stable matchings
13.00-14.00		Lunch
14.00-14.45	William Pettersson	Cops and robbers on multi-layer graphs
14.45-15.30	Michelle Zhang	Meta-mechanisms for combinatorial auctions over social networks
15.30-17.00		Discussion and open problems

---

Stable solutions for kidney exchanges

Abstract: In this talk we will survey the main results of three recent papers on stable solutions for kidney exchange programmes (KEPs). These programmes have been established in most of the developed countries in the world during the last two decades to facilitate the exchange of living kidney donors for those recipients who have willing but immunologically incompatible donors. The UK has the largest KEP in Europe, where optimal solutions with 2-cycles, 3-cycles and altruistic chains are computed for about 300-400 registered pairs in every three months. The concept of stability (or core in the corresponding cooperative game) is an alternative approach, that can provide group fairness and good incentives for the recipients to bring more valuable donors or multiple registered donors to the pool. In this talk, besides some new theorems on the so-called respecting improvement property, we will present novel IP techniques for computing stable (core) solutions for bounded and unbounded exchanges. Furthermore, we will show simulation results on the price of stability, and on the question to what extend the respecting improvement property holds for various solution concepts regarding the stability and optimality requirements.

Computational Complexity of k-Stable Matchings

Abstract: We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching k-stable if no other matching exists that is more beneficial to at least k out of the n agents. The concept generalizes the recently studied majority stability (Thakur, 2021). We prove that whereas the verification of k-stability for a given matching is polynomial-time solvable in all three models, the complexity of deciding whether a k-stable matching exists depends on k/n  and is characteristic to each model (joint work with Haris Aziz and Ágnes Cseh).

Multi-layer cops and robbers

Abstract: We generalise the popular cops and robbers} game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuition about the best way to allocate cops to layers is not always correct, and prove that the multi-layer cop number is neither bounded from above nor below by any increasing function of the cop numbers of the individual layers. Additionally, we investigate a question of worst-case divisions of a simple graph into layers: given a simple graph G, what is the maximum number of cops required to catch a robber over all multi-layer graphs where each edge of G is in at least one layer and all layers are connected? For cliques, suitably dense random graphs, and graphs of bounded treewidth, we determine this parameter up to multiplicative constants. Lastly we consider a multi-layer variant of Meyniel’s conjecture, and show the existence of an infinite family of graphs whose multi-layer cop number is bounded from below by a constant times n log n, where n is the number of vertices in the graph.

Meta-mechanisms for combinatorial auctions over social networks

Abstract: Recently there has been a large amount of research designing mechanisms for auction scenarios where the bidders are connected in a social network. Different from the existing studies in this field that focus on specific auction scenarios e.g. single-unit auction and multi-unit auction, this paper considers the following question: is it possible to design a scheme that, given a classical auction scenario and a mechanism M suited for it, produces a mechanism in the network setting that preserves the key properties of M? To answer this question, we design meta-mechanisms that provide a uniform way of transforming mechanisms from classical models to mechanisms over networks and prove that the desirable properties are preserved by our meta-mechanisms. Our meta-mechanisms provide solutions to combinatorial auction scenarios in the network setting:  (1) combinatorial auction with single-minded buyers and (2) combinatorial auction with general monotone valuation.