Mechanism Design For Facility Location Games

Facility location is one of the classical combinatorial optimization problems.In the facility location problem,we need to determine the positions of one or more facilities to serve all clients while minimizing the cost.In the optimization problem setting,the location information of all clients is public.With the emergence of algorithmic game theory,how-ever,many centralized decision-maker optimization problems evolve into game models with multiple decision makers.This thesis studies the facility location games,which differ from the classical models as the clients' location information is private.The mechanism designer publishes an algorithm(mechanism)in advance,which can determine the facility location with the position profile of all clients as an input.Then,each client,who has learnt the algorithm,provides her location information that would be most advantageous,which may not necessarily be true.In the desirable facility location game,each client aims to min-imize the distance from the facility,while in the obnoxious facility game,each user prefers to be as far away from the facility as possible.Under the game problem setting,the clients'expectation is measured by their utility(cost).The mechanism designer wants to present a mechanism to elicit the true locations of all clients and optimize a certain social criterion(such as the sum of all users' utility),which is called the social utility function.Designing efficient and truthful mechanisms is the mission in mechanism design.In 2009,Procaccia and Tennenholtz published a seminal paper on facility location problem,which has attracted much attention.Although there has been quite a lot of work on mechanism design of facility location games in recent years,previous results mainly focus on the relatively simple models.Very little work is known for more sophisticated utility functions from the real-world scenarios.In this thesis,we will investigate the following new models and provide the theoretical analysis.In the literature,the client's utility is usually defined to be the distance from the client to the facility.In the real-world scenario,however,clients' utility functions often differ as the surrounding environment is diverse.Motivated by the relative satisfaction,we define the client's utility to be the ratio between the distance from the client to the facility and its farthest possible distance,which is called happiness factor.The social utility function is the sum of all the clients' happiness factors.For the desirable facility location problem,we prove that the approximation ratio of the Median Mechanism is 3/2.We then design a deterministic mechanism with approximation ratio 5/4 and point out that the lower bound of this problem is at least 5/2-(?).For the obnoxious facility location game,we show that the Majority Mechanism is of 2-approximation,which is the best possible that any truthful mechanism can achieve.In the real life,the client's preference to the facility may only change very slightly when the distance gets smaller(or larger)if the client is too close to(or too far away from)the facility.For the obnoxious facility location game,we consider the following utility function:Given two distance thresholds d1 and d2,the client becomes obnoxious toward the facility with utility 0 when the distance is below d1;when distance is at least d2,the client becomes completely desirable toward the facility with utility 1;when the distance is between d1 and d2,the utility of the client is a linear function between 0 and 1.For this model,we first discuss the case that there is only one threshold(d1=d2)and design an optimal mechanism.For the case of two thresholds,the problem becomes much harder.When the first threshold d1 ?1/2,the approximation ratio of any deterministic truthful mechanism is unbounded.Hence,we turn to randomized mechanisms in such a case.The upper bound and lower bound turn out to be 2 and 4/3.respectively.We then carry out the approximation ratio of the Majority Mechanism relevant to d1,d2 and prove that it is best possible in most cases.For the case d2?1/2,we design a family of deterministic mechanisms and figure out the approximation ratio for each.Finally,we consider the social utility function of the sum of squares(SOS for short)of the clients' utilities,which plays an important role in the economic environment.We study two models where each client has one location and multiple locations,respectively.In the first model,we establish a deterministic mechanism with approximation ratio 5,which is best possible for the SOS objective,while the upper bound and the lower bound of the ran-domized mechanisms are 5/3 and 1.0428,respectively.If each client has multiple locations,we design a 3/2-approximation randomized mechanism for the sum of all clients' utility ob-jective and the lower bound is at leastLgo For the SOS social utility,we show the upper bound and the lower bound of the randomized mechanisms are 5/3 and 1.0679,respectively.In conclusion,this thesis presents several new models of facility location games based on real-world applications.We propose the heterogeneous models where client's utility is characterized by a happiness factor to break the restriction of homogeneous utility func-tion common used in the previous research.We deal with the step function model with obnoxious effect to model the case where client's sensitivity to distance is invariable.In order to overcome the problem of homogeneity of social utility functions,we introduce the quadratic sum social utility function to mechanism design of the obnoxious facility location game.These well model various utility functions fitting the real-world scenario better.From the point of theoretical view,this paper gives several truthful mechanisms and theoretical analysis.