Algorithms and hardness results for resource allocation and facility location problems

Many real-life scenarios involve making decisions based on agent preferences, for example, electing leaders, developing public facilities, and allocating resources in market. In this thesis, we consider two such problems where we want to make decisions based on agent preferences. In our first problem, we study a variant of the classic housing markets model. Each agent is initially assigned a unique house, and the houses form a graph. Each agent has strict preferences over the houses. Two agents can swap houses if the swap is Pareto-improving and the houses are adjacent. We study three reachability questions in the context of various graph structures. In our second problem, we study a variant of the facility location game. In this setting, a central planner has to build a set of heterogeneous facilities. Every agent reports the set of facilities that they consider "obnoxious". The goal is to design strategyproof and group-strategyproof mechanisms that maximize either the total utility of agents or the minimum utility of agents.