We consider the problem of locating a single facility on a vertex in a given graph based on agents' preferences, where the domain of the preferences is either single-peaked or single-dipped. Our main interest is the existence of deterministic social choice functions (SCFs) that are Pareto efficient and false-name-proof, i.e., resistant to fake votes. We show that regardless of whether preferences are single-peaked or single-dipped, such an SCF exists (i) for any tree graph, and (ii) for a cycle graph if and only if its length is less than six. We also show that when the preferences are single-peaked, such an SCF exists for any ladder (i.e., 2-by-m grid) graph, and does not exist for any larger hypergrid.
Moulin @cite_9 proposed generalized median voter schemes, which are the only deterministic, truthful, PE, and anonymous SCFs. Procaccia and Tennenholtz @cite_10 proposed a general framework of approximate mechanism design, which evaluates the worst case performance of truthful SCFs from the perspective of competitive ratio. Recently, some models for locating multiple heterogenous facilities have also been studied @cite_16 @cite_20 @cite_1 . @cite_5 considered the agents who dynamically arrive and depart. Some research also considered facility location on grids @cite_28 @cite_7 and cycles @cite_13 @cite_14 @cite_6 . @cite_11 overviewed applications in practical decision making.
@cite_13 @cite_14 @cite_7 @cite_28 @cite_9 @cite_1 @cite_6 @cite_5 @cite_16 @cite_10 @cite_20 @cite_11
2155975756 2015555360 1918562889 318376482 2083397025 2808656711 2106615115 2807889088 2408343736 2108957189 2116725038
We consider the problem of locating a facility on a network represented by a graph. A set of strategic agents have different ideal locations for the facility; the cost of an agent is the distance between its ideal location and the facility. A mechanism maps the locations reported by the agents to the location of the facility. We wish to design mechanisms that are strategyproof (SP) in the sense that agents can never benefit by lying and, at the same time, provide a small approximation ratio with respect to the minimax measure. We design a novel “hybrid” strategyproof randomized mechanism that provides a tight approximation ratio of 3 2 when the network is a circle (known as a ring in the case of computer networks). Furthermore, we show that no randomized SP mechanism can provide an approximation ratio better than 2 - o (1), even when the network is a tree, thereby matching a trivial upper bound of two. Consider the unit circle S^1 with distance function d measured along the circle. We show that for every selection of 2n points x"1,...,x"n,y"1,...,y"[email protected]?S^1 there exists [email protected]? 1,...,n such that @?"k"="1^nd(x"i,x"k)@[email protected]?"k"="1^nd(x"i,y"k). We also discuss a game theoretic interpretation of this result. This paper is devoted to the location of public facilities in a metric space. Selfish agents are located in this metric space, and their aim is to minimize their own cost, which is the distance from their location to the nearest facility. A central authority has to locate the facilities in the space, but she is ignorant of the true locations of the agents. The agents will therefore report their locations, but they may lie if they have an incentive to do it. We consider two social costs in this paper: the sum of the distances of the agents to their nearest facility, or the maximal distance of an agent to her nearest facility. We are interested in designing strategy-proof mechanisms that have a small approximation ratio for the considered social cost. A mechanism is strategy-proof if no agent has an incentive to report false information. In this paper, we design strategyproof mechanisms to locate n - 1 facilities for n agents. We study this problem in the general metric and in the tree metric spaces. We provide lower and upper bounds on the approximation ratio of deterministic and randomized strategy-proof mechanisms. We consider the mechanism design problem for agents with single-peaked preferences over multi-dimensional domains when multiple alternatives can be chosen. Facility location and committee selection are classic embodiments of this problem. We propose a class of percentile mechanisms, a form of generalized median mechanisms, that are strategy-proof, and derive worst-case approximation ratios for social cost and maximum load for L1 and L2 cost models. More importantly, we propose a sample-based framework for optimizing the choice of percentiles relative to any prior distribution over preferences, while maintaining strategy-proofness. Our empirical investigations, using social cost and maximum load as objectives, demonstrate the viability of this approach and the value of such optimized mechanisms vis-a-vis mechanisms derived through worst-case analysis. This paper investigates one of the possible weakening of the (too demanding) assumptions of the Gibbard-Satterthwaite theorem. Namely we deal with a class of voting schemes where at the same time the domain of possible preference preordering of any agent is limited to single-peaked preferences, and the message that this agent sends to the central authority is simply its ‘peak’ — his best preferred alternative. In this context we have shown that strategic considerations justify the central role given to the Condorcet procedure which amounts to elect the ‘median’ peak: namely all strategy-proof anonymous and efficient voting schemes can be derived from the Condorcet procedure by simply adding some fixed ballots to the agent's ballots (with the only restriction that the number of fixed ballots is strictly less than the number of agents). We study heterogeneous k -facility location games on a real line segment. In this model there are k facilities to be placed on a line segment where each facility serves a different purpose. Thus, the preferences of the agents over the facilities can vary arbitrarily. Our goal is to design strategy proof mechanisms that locate the facilities in a way to maximize the minimum utility among the agents. For @math , if the agents' locations are known, we prove that the mechanism that locates the facility on an optimal location is strategy proof. For @math , we prove that there is no optimal strategy proof mechanism, deterministic or randomized, even when @math and there are only two agents with known locations. We derive inapproximability bounds for deterministic and randomized strategy proof mechanisms. Finally, we provide strategy proof mechanisms that achieve constant approximation. All of our mechanisms are simple and communication efficient. As a byproduct we show that some of our mechanisms can be used to achieve constant factor approximations for other objectives as the social welfare and the happiness. We study strategyproof (SP) mechanisms for the location of a facility on a discrete graph. We give a full characterization of SP mechanisms on lines and on sufficiently large cycles. Interestingly, the characterization deviates from the one given by Schummer and Vohra (2004) for the continuous case. In particular, it is shown that an SP mechanism on a cycle is close to dictatorial, but all agents can affect the outcome, in contrast to the continuous case. Our characterization is also used to derive a lower bound on the approximation ratio with respect to the social cost that can be achieved by an SP mechanism on certain graphs. Finally, we show how the representation of such graphs as subsets of the binary cube reveals common properties of SP mechanisms and enables one to extend the lower bound to related domains. Facility location is a well-studied problem in social choice literature, where agents' preferences are restricted to be single-peaked. When the number of agents is treated as a variable (e.g., not observable a priori), a social choice function must be defined so that it can accept any possible number of preferences as input. Furthermore, there exist cases where multiple choices must be made continuously while agents dynamically arrive leave. Under such variable and dynamic populations, a social choice function needs to give each agent an incentive to sincerely report her existence. In this paper we investigate facility location models with variable and dynamic populations. For a static, i.e., one-shot, variable population model, we provide a necessary and sufficient condition for a social choice function to satisfy participation, as well as truthfulness, anonymity, and Pareto efficiency. The condition is given as a further restriction on the well-known median voter schemes. For a dynamic model, we first propose an online social choice function, which is optimal for the total sum of the distances between the choices in the previous and current periods, among any Pareto efficient functions. We then define a generalized class of online social choice functions and compare their performances both theoretically and experimentally. The study of facility location in the presence of self-interested agents has recently emerged as the benchmark problem in the research on mechanism design without money. Here we study the related problem of heterogeneous 2-facility location, that features more realistic assumptions such as: (i) multiple heterogeneous facilities have to be located, (ii) agents' locations are common knowledge and (iii) agents bid for the set of facilities they are interested in. We study the approximation ratio of both deterministic and randomized truthful algorithms when the underlying network is a line. We devise an (n - 1)-approximate deterministic truthful mechanism and prove a constant approximation lower bound. Furthermore, we devise an optimal and truthful (in expectation) randomized algorithm. The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on payments. In this article, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We explicitly argue for the first time that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are almost ubiquitous and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity. We present a case study in approximate mechanism design without money. In our basic setting, agents are located on the real line and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. We establish tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost and the maximum cost. We then extend our results in two natural directions: a domain where two facilities must be located and a domain where each agent controls multiple locations. Facility location decisions play a critical role in the strategic design of supply chain networks. In this paper, a literature review of facility location models in the context of supply chain management is given. We identify basic features that such models must capture to support decision-making involved in strategic supply chain planning. In particular, the integration of location decisions with other decisions relevant to the design of a supply chain network is discussed. Furthermore, aspects related to the structure of the supply chain network, including those specific to reverse logistics, are also addressed. Significant contributions to the current state-of-the-art are surveyed taking into account numerous factors. Supply chain performance measures and optimization techniques are also reviewed. Applications of facility location models to supply chain network design ranging across various industries are presented. Finally, a list of issues requiring further research are highlighted.