M.Sc Thesis

M.Sc StudentFilimonov Alina
SubjectStrategyproof Facility Location Mechanisms on
Discrete Trees
DepartmentDepartment of Industrial Engineering and Management
Supervisor ASSOCIATE PROF. Reshef Meir


In facility location problems, a central planner has to determine the location of a public facility to serve a group of agents, based on their reported locations. Once the facility is located, each agent incurs some cost. Importantly, in non-cooperative settings, agents may have an incentive to misreport their locations to decrease their distance to the facility. One key objective of the planner, therefore, is to design a mechanism that incentivizes agents to report their true locations, i.e., a mechanism that is strategyproof.

 In this research, we address the problem of strategyproof facility location mechanisms on discrete trees. Our main result is a full characterization of onto, strategyproof mechanisms, generalizing previous works on discrete lines. We show that when a single agent significantly affects the outcome, the trajectory of the facility is almost contained in the trajectory of the agent, and both move in the same direction on the common edges. We then characterize strategyproof and onto mechanisms on continuous trees. In contrast to previous results, which describe the valid outcomes of SP mechanisms depending on the input location profile, our characterization describes the possible moves of the facility that follow an agent's misreport. In particular, we show that in the continuous case, the trajectory of the facility is fully contained in the trajectory of the agent. Additionally, we derive further implications of the main result for infinite discrete lines. A mechanism on a discrete line is called "shift-invariant" if the shift in output equals to the shift in the input. We show that every strategyproof, onto, anonymous and shift-invariant mechanism is necessarily a k-th order statistic mechanism.