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.

Please register for this workshop by 13.00 on Tuesday 13 May by contacting Felicia Lucke at [email protected]. Late registration is not possible.

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

Anastasiia Parakhoniak — Beyond Connectivity: Stock Market Participation in a Network

Durham University

What are the aggregate and distributional consequences of the relationship between an individual’s social network and financial decisions? Motivated by several well-documented facts about the influence of social connections on financial decisions, we build and calibrate a model of stock market participation with a social network that emphasizes the interplay between connectivity and network structure. Since connections to informed agents influence peers through utility and learning, there is a pivotal role for homophily. An increase in the average number of connections raises the average participation rate, mostly due to richer agents. Higher homophily benefits richer agents by creating clusters where information spreads more efficiently. We also show that social utility is crucial for matching stock market participation among poorer agents. Finally, we provide empirical evidence consistent with the importance of connectivity and sorting.

Nihal Berktas — Team Formation on Social Networks

Durham University

The Team Formation Problem on social networks aims to identify a group of individuals who collectively possess the required skills for a given task and can communicate effectively. Typically, the communication effectiveness between two individuals is modelled as a cost assigned to the edge connecting them in a graph. While defining the communication cost between two individuals is straightforward, aggregating these into a meaningful communication cost for the whole team is more challenging. Various definitions of team communication cost—such as diameter, minimum Steiner tree, sum of pairwise distances, and bottleneck measures—have been proposed, each leading to problems with different combinatorial structures and computational complexities. In this talk, we will explore how different communication cost definitions influence the problem’s structure, leading to different algorithmic approaches, e.g., greedy, approximation, and exact methods. I will conclude by briefly presenting a branch-and-bound algorithm designed to find optimal solutions for a specific version of the problem.

Márton Benedek — Computing the Nucleolus for Cooperative Games: Misconceptions, Efficiency and Applications

Budapest University of Technology and Economics

We briefly introduce cooperative games with transferable utilities (TU-games for short), focusing the way they can model benefits of cooperation in various (mainly, but not exclusively economics related) settings and lead to stable and/or fair allocation problems. We provide a very brief overview of certain solution concepts and some of their fundamental properties, then focusing on a particular widely known concept called the nucleolus: it is a solution of a lexicographical optimisation problem, that is notoriously difficult to compute but have very good properties. Computing the nucleolus of a TU-game is traditionally being done by solving the lexicographical problem via a series of large linear programs (LPs). We provide an overview of the state-of-the-art method to solve this series of large LPs, the so-called lexicographical descent method (LDM) and provide numerical results to underline its efficiency. Meanwhile we touch on typical misconceptions that occur in the literature regarding computing the nucleolus and highlight some of the application possibilities that have become available thanks to the efficiency of LDM, as well as identifying some of the open problems still to be solved in this area.

Xin Ye — Computing Balanced Solutions for International Kidney Exchange Schemes

Durham University

In a kidney exchange programme (KEP), patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, to improve the total social welfare, countries may try to merge their national patient-donor pools leading to an international kidney exchange program (IKEP). To ensure fairness for participating countries in the long term while maximizing the total number of transplants, IKEPs may use a credit-based system. Such a system prescribes, in each round, a target number of kidney transplants for each country, which is determined by an initial “fair” allocation and adjusted by credits. The goal is to find, in each round, an optimal solution for the participating countries that closely approximates the target allocation. We perform large-scale simulations for IKEPs with maximum cycle lengths 2, 3 and ∞, respectively. To obtain the initial allocations, we use seven different solution concepts from cooperative game theory. In this way we are able to give a clear picture on how the stability and total social welfare of an IKEP is affected by the choice of solution concept and the maximum cycle length. This is joint work with Márton Benedek, Péter Biró, Gergely Csáji, Matthew Johnson and Daniel Paulusma.

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