AbstractThe facility location problem is about how to decide the position of a facility, such as a hospital or a library, in a setting with selﬁsh agents and different goals. This has emerged as the benchmark problem in the study of the trade-off between incentive compatibility without transfers and approximation guarantee, a research area also known as approximate mechanism design without money. One limitation of the vast literature on the subject is the assumption that agents and facilities have to be located on the same physical space. We here initiate the study of constrained heterogeneous facility location problems, wherein selﬁsh agents can either like or dislike the facility and facilities, and be located on a given feasible region of the Euclidean plane.
In this thesis, research on this topic is carried out in two different manners. To be speciﬁc, in Chapters 2 and 3, agents are assumed to be located on a real segment, and their locations together with their preferences towards the facilities are not transparent to the mechanism designer, as well as each other, which are part of agents’ private type. The main difference between the two chapters is the objective function, that is, maximising the social welfare (the sum of agent’s utilities) and maximising the minimum utility of an agent respectively.
Our main result of Chapter 2 is a characterization of the feasible regions for which the optimum is incentive-compatible in the settings wherein agents can only lie about their preferences or about their locations (but not both). The stark contrast between the two ﬁndings is that in the former case any feasible region can be coupled with incentive compatibility, whilst in the second, this is only possible for feasible regions where the optimum is constant.
In Chapter 3, we prove a similar dichotomy. When locations are public information (only preferences are private) no matter the shape of the feasible region, the optimum max-min mechanism is strategyproof; on the contrary, if locations are unknown (whilst preferences are known) the optimum is strategyproof only in very limited cases.
In Chapter 4, we allow the agents to be placed in a metric space, introduce a new scenario of alternative facilities, and adopt an empirical methodology, agent-based model. More speciﬁcally, we switch our research from mechanism design perspective to a study of equilibrium of dynamics, so as to observe and estimate the quality of algorithms in these more general settings.
|Date of Award
|1 Mar 2022
|Carmine Ventre (Supervisor) & Maria Polukarov (Supervisor)