Algorithms for matching problems involving preferences

这个研究项目涉及从算法的角度来研究联盟的形成。根据https://www.coalitiontheory.net/research-areas/coalition-formation-theory的说法，联盟形成理论涉及“对一个或多个被称为联盟的行动者群体的分析，这些行动者为了执行某些行动而被分配给另一个群体”。联盟形成问题包括与联盟形成相关的计算问题，这些问题可能满足某些约束和最优目标，给定外生信息，如对其他代理的顺序偏好。联盟形成是博弈论的一个分支，包括对匹配问题的研究，这涉及到根据顺序偏好或基本效用为商品分配代理人。匹配问题和联盟形成问题已被计算机科学家和经济学家广泛研究，但通常术语和研究的精确性质在两个领域之间有所不同。例如，经济学家通常对策略验证机制感兴趣，而计算机科学家可能更倾向于关注算法的计算复杂性。本研究项目的目的是为联盟形成问题开发新的算法结果，并通过实验研究，调查联盟形成算法的性能。具体目标如下：-了解联盟形成问题领域的最新技术，考虑到某些问题可能会根据学科使用不同的术语进行研究；-为联盟形成问题的特定变体导出新的有效算法和np -硬度结果，例如，考虑到代理的偏好，将代理分配到联盟中，其中可能存在对联盟大小或偏好列表的最大长度的约束；-导出处理NP-hard联盟形成问题的技术，包括指数时间精确算法、近似算法、FPT算法以及基于整数和约束规划的算法；-实现算法并在真实和随机生成的数据上实验分析其行为，涉及运行时间和各种优化措施。联盟形成问题在现实世界中有着广泛的应用，因此上面提出的研究有可能在一系列领域产生影响。例如，最著名的匹配问题出现在将初级医生分配给医院、将学生分配给高中以及将肾病患者分配给捐赠者等问题上。更普遍的是，联盟形成问题也可以根据学生对彼此的偏好，对学生进行小组工作的分配进行建模。在这个领域有许多悬而未决的问题：这些问题可以通过对联盟的性质施加限制，或者通过确定关于将要构建的联盟的适当的最优性标准（例如“稳定性”）来获得。研究技术将包括证明可被算法利用的结构结果，推导有效的最优和近似算法，证明np -硬度和不可逼近性结果，构建整数和约束规划模型，以及对算法实现进行实验分析。本研究属于EPSRC信息与通信技术主题下的理论计算机科学领域。预计将有机会与计算科学学院形式分析、理论和算法研究部门的其他成员以及亚当·斯密商学院经济学和微观理论小组的成员合作。

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.