Social Choice And Utility In Coalition Formation PDF Download

Collective decision making arises in many real life situations, such as elections, matching applicants to job openings, and partitioning students into working groups. Over the past three decades, computer scientists have used techniques from the design and analysis of algorithms and complexity theory to develop social choice theory from a computational perspective, leading to the new research area of computational social choice theory. Broadly speaking, this dissertation makes two kinds of contributions to this new research area. First, we provide new algorithms and hardness results for two settings. In our first setting, we revisit the classical housing markets model in which we seek to compute a suitable reallocation of n houses to n agents, each of whom initially owns a particular house and has strict preferences over the set of n houses. In the variants of this model that we study, graph-based restrictions are imposed on the exchange of houses. More specifically, we consider two cases. In the first case, we are given a graph where the vertex set corresponds to the set of agents, and we assume that two agents can only swap houses if they are adjacent in the graph and the swap is Pareto-improving; thus, in this case, the locations of the agents remain fixed in the graph, while the houses can move around. The second case is similar except we assume that the locations of the houses remain fixed (i.e., each vertex now corresponds to a house) and the agents move around. In our second setting, we consider a variant of the classical coalition formation game, the fractional hedonic game. Such a game can be represented by a directed weighted graph where the set of vertices corresponds to the set of players, and where the weight of an edge (i,j) from player i to player j denotes the value that player i has for player j. Given a partitioning of the players into coalitions, the utility of player i is defined to be the average value that player i assigns to the members of their coalition. We assume that there is a limit on the number of coalitions that can be formed. In this setting, we study the problem of computing a social welfare maximizing partition and the problem of computing a Nash stable partition. We study these two problems for a variety of different graph classes. Second, we design mechanisms without money for new games related to facility location and resource sharing. In the facility location game that we consider, a central planner plans to build a heterogeneous set of facilities (e.g., a school, a water treatment plant) and each agent reports which of these facilities they consider to be “obnoxious”. The location of each agent is assumed to be fixed, and the utility of an agent is based on the minimum distance of the agent to an obnoxious facility. The goal is to design strategyproof mechanisms that maximize either the sum of the agent utilities or the minimum utility of any agent. In the resource sharing game that we consider, agents pool their computational resources in order to better accommodate fluctuations in individual demand over a sequence of rounds, and the agents specify their demand for each round at the outset. We present a group-strategyproof and non-wasteful mechanism that guarantees each agent at least half of the utility they could achieve without sharing their resources