Algorithms for matching problems involving preferences

This research project involves investigating coalition formation from an algorithmic perspective. According to https://www.coalitiontheory.net/research-areas/coalition-formation-theory, coalition formation theory involves "the analysis of one or more groups of agents, called coalitions, who become assigned to one another in order to carry out some action". Coalition formation problems encompass the computational problems that relate to the formation of coalitions that may satisfy certain constraints and optimality objectives, given exogenous information such as ordinal preferences over other agents.

Coalition formation is a branch of game theory and includes the study of matching problems, which involve assigning agents to commodities on the basis of ordinal preferences or cardinal utilities. Matching problems and coalition formation problems have been widely studied by computer scientists and economists, but often the terminology and precise nature of research varies between the two fields. For example economists are often interested in strategy-proof mechanisms, whereas computer scientists may instead be inclined to focus more on the computational complexity of algorithms.

The aim of this research project is to develop new algorithmic results for coalition formation problems and, through experimental studies, to investigate the performance of coalition formation algorithms. The specific objectives are as follows:

- to develop an understanding of the state of the art in the area of coalition formation problems, allowing for the fact that certain problems may be studied using different terminology depending on the discipline;
- to derive new efficient algorithms and NP-hardness results for specific variants of coalition formation problems, for example involving the allocation of agents into coalitions taking into account agents' preferences, where there may be constraints on the coalition sizes or the maximum lengths of preference lists;
- to derive techniques for coping with NP-hard coalition formation problems, including exponential-time exact algorithms, approximation algorithms, FPT algorithms, and algorithms based on integer and constraint programming;
- to implement algorithms and analyse their behaviour experimentally on real and randomly-generated data, with respect to runtime and various measures of optimality.

Coalition formation problems have a range of real-world applications, and hence the research proposed above has the potential to lead to impact in a range of areas. For example matching problems arise most famously in the allocation of junior doctors to hospitals, students to high schools and kidney patients to donors. More generally, coalition formation problems can also model the allocation of students to teams to carry out group work, based on students' preferences over one another.

There are many open problems in this area: these may be obtained by placing restrictions on the nature of the coalitions, or by identifying appropriate optimality criteria (such as "stability") with respect to the coalitions that are to be constructed. The research techniques will involve proving structural results that can be exploited by algorithms, deriving efficient optimal and approximation algorithms, proving NP-hardness and inapproximability results, constructing integer and constraint programming models, and carrying out experimental analyses of algorithm implementations.

This research belongs to the area of Theoretical Computer Science within the Information and Communications Technology theme of EPSRC. It is expected that there will be opportunities to collaborate with other members of the Formal Analysis, Theory and Algorithms research section within the School of Computing Science, and also with members of the Economics and Microtheory group at the Adam Smith Business School.