ACiD WORKSHOP: Games and Graphs II

Date: Tuesday 27 May 2025
Venue: Scott Logic Theatre (Mathematical Sciences & Computer Science Building)
Organisers: Felicia Lucke, Riccardo Mogre and Daniel Paulusma

The workshop is about problems in the areas of economics, operations research and game theory that can be modelled as problems defined on graphs / networks. The previous edition took place on 1 May 2024.

Schedule

10.30-11.00		Arrival with Coffee and Tea
11.00-11.30	Frances Rosamond, Mike Fellows	Games That Cannot Go On Forever
11.30-12.00	Rachael Colley	International Kidney Exchange Programmes with Country-Specific Parameters
12.00-12.30	Anastasiia Parakhoniak	Beyond Connectivity: Stock Market Participation in a Network
12.30-13.00		Open problems
13.00-14.00		Lunch
14.00-14.30	Nihal Berktas	Team Formation on Social Networks
14.30-15.00	Márton Benedek	Computing the Nucleolus for Cooperative Games: Misconceptions, Efficiency and Applications
15.00-15.30	Xin Ye	Computing Balanced Solutions for International Kidney Exchange Schemes
15.30-16.00		Coffee break
16.00-17.00		Open problems & discussions

Speakers and Abstracts

Frances Rosamond, Mike Fellows —
Games That Cannot Go On Forever

University of Bergen

Natural and amusing classes of games centered on well quasi-orderings, that we call Harvey Games, arise in considering combinatorial convergence issues of “encountered instance” learning algorithms for beyond-worst-case FPT. These charming games may have value: (1) as entertainment, (2) in math sciences outreach and communication, and (3) in encouraging and developing thinking skills relevant to marketing and design.

Rachael Colley — International Kidney Exchange Programmes with Country-Specific Parameters

University of Glasgow

Abstract: Kidney Exchange Programs (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the proposal of international KEPs (IKEPs). However, as studied by Mincu et al. (2021), practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, in this talk, we present IKEPs with country-specific parameters, represented by a tuple Γ, restricting the selected transplants to be feasible for the countries to conduct, e.g., imposing an upper limit on the number of consecutive exchanges within a country’s borders. We present a complete complexity dichotomy for the problem of finding a feasible (according to the constraints given by Γ) cycle packing with the maximum number of transplants for every possible Γ. Following this, we explain the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we introduce a novel individually rational and incentive compatible mechanism M-order. We first give a theoretical approximation ratio for M-order in terms of the number of transplants and then show that the approximation ratio of M-order is asymptotically optimal. We then use simulations to demonstrate that, in practice, the performance of M-order is significantly better than this worst-case ratio.

Joint work with David Manlove, Daniel Paulusma, and Mengxiao Zhang

We thank Durham’s Institute for Data Science and Flourish at Durham – Research Culture for their support.