Strategyproof Facility Location and Committee Selection with Mixed Max and Sum Agent Types
For researchers in algorithmic game theory and mechanism design, this work provides the first strategyproof mechanisms for mixed agent types in facility location, with tight approximation bounds.
This paper studies strategyproof facility location with agents having max-type or sum-type cost functions, where both location and type may be private. They provide deterministic mechanisms achieving approximation ratios of 3-2/k (with known locations) and 3 (with private locations on a line), showing good outcomes are possible without full information.
We study strategic facility location, in which $n$ agents are located in an arbitrary metric space, and the goal is to choose $k$ facilities to minimize the total agent cost. The agents can have two types of individual cost functions: max-type where the agent wants to minimize the maximum distance from themselves to any chosen facility, or sum-type where the agent wants to minimize the average distance to the chosen facilities. The agents are self-interested, however, and both the agent location and the agent type may be private information. We provide deterministic strategyproof mechanisms for this setting, and prove bounds on their approximation ratio as compared with the solution minimizing the total agent cost. When agent types are private but their locations are known, we prove that an approximation of $\left(3 -\frac{2}{k}\right)$ is always possible, and a better approximation of $\left(\frac{2}{1-k+\sqrt{k^2-k+1}}-1\right)$ is achievable when we know the {\em fraction} of the agents with each type, but not necessarily the type of each individual agent. These bounds hold for arbitrary $k$ and arbitrary metric distances. When agent locations are private, we instead focus on the line metric, and show that a simple generalization of the median mechanism results in an approximation ratio of 3, even for large $k$ and arbitrary mixes of agent types. Our results show the importance of collecting information about agent types vs about their locations, and show that it is possible to produce good outcomes even without such information.