Strategyproof Facility Location and Committee Selection with Mixed Max and Sum Agent Types

Yue Gruszecki, Elliot Anshelevich · 2026

Read Strategyproof Facility Location and Committee Selection with Mixed Max and Sum Agent Types by Yue Gruszecki, Elliot Anshelevich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26074.txt.

Introduction

Yue Gruszecki and Elliot Anshelevich design honest mechanisms for placing facilities among strategic agents. Agents sit in a metric space, and k facilities must be chosen to cut total cost. Agents come in two flavours. Max-type agents care about their farthest chosen facility. Sum-type agents care about their average distance to all facilities. Locations and types can both be private, so agents might lie to pull facilities closer.

Deterministic strategyproof mechanisms are the deliverable. Lying never pays under their rules. When types are private but locations are known, a stated approximation always holds. Knowing just the mix of types improves the guarantee further. Private locations get a line-metric treatment instead. A generalized median rule reaches an approximation ratio of three there. The ratio holds for large k and any mix of types. Results highlight a lesson for planners: learning agent types buys more than learning their locations.

Catalog record

CREATORYue Gruszecki, Elliot Anshelevich
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26074

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strategyproof Facility Location and Committee Selection with Mixed Max and Sum Agent Types Yue Gruszecki, Elliot Anshelevich Abstract We study strategic facility location, in which n n agents are located in an arbitrary metric space, and the goal is to choose k 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 ( 3 − 2 k ) \left(3-\frac{2}{k}\right) is always possible, and a better approximation of ( 2 1 − k + k 2 − k + 1 − 1 ) \left(\frac{2}{1-k+\sqrt{k^{2}-k+1}}-1\right) is achievable when we know the fraction of the agents with each type, but not necessarily the type of each individual agent. These bounds hold for arbitrary k 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 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. 1 Introduction Strategic facility location captures the essence of many types of problems, including those in social choice, clustering, and placing actual physical facilities. Because of this, facility location with self-interested agents has been studied extensively; see, for example, [ 2 ] for a survey. In a classic strategic facility location setting, we are given a metric space containing a set of n agents \mathcal{C} (sometimes called “clients”), and a set of possible facility locations \mathcal{F} . The goal is to select a set of k facilities from \mathcal{F} such that they optimize some objective function. This setting also captures many problems in spatial voting, where voters can be represented as agents and candidates can be represented as facilities [ 19 , 7 ] . In the strategic version, agents are self-interested, meaning that they may misreport their information (e.g., their personal cost function, or their true location). Then, the goal becomes to form a strategyproof mechanism, meaning that no agent can improve their cost by misreporting their private information, such that this mechanism always chooses facilities which are a good approximation for the optimal solution. Much of the existing work on this topic focused on forming strategyproof mechanisms for a line metric (e.g., [ 16 , 25 , 21 , 20 , 5 ] ), and for either k=1 [ 3 , 4 , 15 ] or k=2 [ 6 , 17 , 26 ] . In this paper, we are instead interested in results for arbitrary k . The case when k\geq 2 , so that multiple facilities must be chosen, can be used to represent committee selection, where the goal is to choose a committee A\subseteq\mathcal{F} of size k that minimizes some objective function (e.g., social cost, maximum of all agent costs, etc). The most commonly used objective is the social cost, which is to minimize \sum_{i\in\mathcal{C}}cost_{i}(A) , where cost_{i}(A) is the individual cost of agent i for the chosen set of facilities A . For example, cost_{i}(A) could be the maximum distance from i to any location in A , the average distance from i to locations in A , or something else. Previous work has looked at forming good committees when all the agents have the same type of cost function (e.g., all max or all sum). In this work, however, we want to form good outcomes when agents may have different types of cost functions . 1.1 Individual Costs of Different Types For the simpler case when k=1 , the commonly used social cost objective asks to select a facility a\in\mathcal{F} which minimizes \sum_{i\in\mathcal{C}}d(i,a) , with d(i,a) here being the distance from agent i ’s true location to facility a . In other words, the individual cost of agent i (which we denote by cost_{i} ) is assumed to be the distance from agent i to the facility, capturing the fact that the agent prefers facilities which are closer to them (or candidates which are more similar to them in the given ideological metric space). For our setting with k\geq 2 , however, there are many different individual cost functions that can be considered. For a set A\subseteq\mathcal{F} of size k , how happy would agent i be if this set of facilities were chosen? How should we define cost_{i}(A) ? One commonly considered individual cost for each agent i is the minimum distance from i to each of the facilities in A , i.e, cost_{i}(A)=\min_{a\in A}d(i,a) [ 18 , 21 , 10 , 24 , 26 ] . This is used, for example, in the k- center and k- median problem objectives. However, using the minimum distance may not necessarily capture the case where facilities are heterogeneous , such that agents need to access all of the chosen facilities instead of just one of them. This occurs when agents need to get different resources from different facilities, when facilities are different types (e.g., a park and a post office, and i wants to use both), or when A represents a committee and i wants all members on the committee to be similar to them, not just a single member. See [ 23 ] for more discussion of such heterogeneous facilities. In this paper, we focus on choosing multiple heterogeneous facilities, and thus consider two different types of individual costs. The first cost is defined as cost_{i}(A)=\max_{a\in A}d(i,a) , also known as the max-variant [ 4 , 17 , 27 ] . The second is defined as cost_{i}(A)=\frac{1}{k}\sum_{a\in A}d(i,a) , also known as the sum-variant [ 28 , 23 , 26 ] . To see why these two cost functions make sense for our setting, note that in both variants the agent cares about minimizing their distance to all the chosen facilities; in the first case it cares about the maximum distance (all facilities should be at most x away from i ), and in the second case it wants to minimize the average distance. Agents with max-variant or sum-variant costs have been studied in numerous previous works; most of this existing work only looks at the simpler case of k=2 , although there are some notable exceptions (see Related Work). More importantly, all of this previous work assumes that all agents have the same type, i.e., they are either all max-type agents, or sum-type agents. 1 1 1 To the best of our knowledge, the only existing work in strategic facility location which simultaneously allows agents to have different individual costs is [ 12 ] , see Related Work for

Read the complete text