Algorithmic Complexity of Matching and Games

Abstract

We study various problems relating to computational social choice (COMSOC) and algorithmic game theory (AGT). Many of the problems we study are NP-hard or beyond. To tackle this complexity, we turn to parameterized complexity and restricted preference domains. Both of these attempt to capture properties of problem instances that make the problems more tractable. In parameterized complexity, we aim to construct algorithms whose exponential components depend only on a specific parameter of the input size. We take a deeper look at a restricted preference domain called d-Manhattan preferences. These preferences arise if the voters and alternatives are located in the d-dimensional real space where the distance is measured using Manhattan distance (aka. l1-norm), and every voter prefers an alternative that is closer to her to one that is further from her. We determine the smallest – in terms of the number of voters and alternatives – preference profiles (collection of voters and alternatives) that are not d-Manhattan, and provide some guarantees on when a preference profile is d-Manhattan. We also study how d-Manhattan preferences relate to other restricted preference domains, such as single-peaked and single-crossing preferences. In the field of matching under preferences, we study the parameterized complexity of refugee resettlement. In this many-to-one matching setting, refugee families must be assigned to places where they can live. The families also have requirements for services, and the places have upper and lower quotas on how much of the services they can provide. We study the parameterized complexity of finding or determining assignments with desirable properties, and obtain a fairly complete picture for multiple natural parameters. Further, we study hedonic games, which can be seen as an extension of matchings. In hedonic games, agents have preferences over coalitions (subsets of agents) containing them. The agents need to be partitioned into disjoint coalitions so that the resulting partition satisfies selected stability constraints. We focus on two compact preference encodings: the model of friends and enemies, and the model of friends, enemies, and neutrals. For both of these models, the preferences can be either friend-oriented or enemy-oriented. We provide a fairly complete parameterized complexity picture for the above-mentioned preference encodings under multiple stability concepts for both friend- and enemy-oriented preferences. Finally, we move to non-cooperative games and study the game implementation problem. In this problem, we are given a normal-form game, some desired outcomes (strategy profiles) of the game, and a budget. The goal is to pay the agents so that they play strategies resulting in the desired outcomes, while we stay within the budget. The problem is already known to be NP-hard; we show that this remains the case in multiple restricted cases, such as when the budget is zero, and there are only two players. We additionally fix a flaw in an earlier exponential-time algorithm for a variant of the problem.