Skip to main content
Research and Business
A purple illustration of the planet with virtual connections

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

 

Please register for this workshop  by 13.00 on Tuesday 13 May by contacting Daniel Paulusma at daniel.paulusma@durham.ac.uk. Late registration is not possible.

 

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.