Facility Location Games: Groups and Fairness

Abstract

Approximate mechanism design without money is a research field integrating economics and computer science, which includes a well-established area, facility location games. Facility location games study how to locate some facilities to serve agents on a network. In most settings, agents are on a real line and aim to make the facility as close as possible. The goal is to design mechanisms that elicit true locations from the agents and place a facility to approximately optimize a given objective based on agents' costs/utilities to the facility. Many extensions to classic facility location games have been proposed and studied recently [20]. The thesis is inspired by the following observations: 1) people in real-life scenarios are always in groups divided by certain criteria, where people in the same group have similar characteristics and behaviors; 2) besides social welfare, governments or policymakers are increasingly concerned about fairness among social groups. Hence, this thesis focuses on group and fairness and mainly considers the following four scenarios.

In Chapter 2, facility location games with thresholds are considered, which are motivated by the scenario where an agent cost may not increase linearly with the distance from the facility. In particular, agents are divided into groups corresponding to different thresholds. This thesis mainly introduces two types of thresholds for the agent's cost. For the model with lower thresholds, the agent's cost is 0 if the distance is within the threshold. Otherwise, it increases linearly until the value is 1. Similarly, for the model with upper thresholds, the cost is 1 if the distance is beyond the threshold. Otherwise, it is a linear function with a value from 0 to 1. For the first model, a strategyproof mechanism is presented, which is optimal for the social cost objective, and another strategyproof mechanism with an approximation ratio of 3 is presented for the maximum cost objective. For the second model, the median mechanism is leveraged for the social cost with a threshold-based approximation ratio. A new mechanism is proposed for the maximum cost with tight bounds. Lower bounds are also shown for both models. Finally, the setting where each agent has both thresholds is studied.

In Chapter 3, facility location games with group externalities are studied, which is motivated by the scenario where agents in the same group may interact. Hence, the utility of an agent is obtained by not only using the facility but also interacting with their group members. Group externalities capture the effect of the interactions within a group. Three types of manipulation are considered: misreporting only the location, misreporting only the group membership, and misreporting both, under two social objectives, the social utility and the minimum utility. For both objectives, Nearly tight bounds are achieved by either designing new mechanisms or extending the existing mechanisms in terms of the first two types of manipulation. As a negative result, strategyproofness and unanimity are incompatible when each agent can misreport the location and the group membership, which is independent of the objective functions.

In Chapter 4, multi-winner facility location games are proposed, where k of m facilities will be located. A formal model of multi-winner facility location with approval preferences in one dimension is developed: there is a set of facilities and a set of potential locations, and the goal is to build k facilities at these locations. Agents have approval preferences over 'facility, location' pairs. Both unit-demand agents and agents with additive demands are considered, under the social objectives of coverage and utilitarian welfare. This part answers whether these social objectives can be satisfied in a computationally efficient and strategyproof way. The study of proportional representation in the context of facility location is also initialized. The axiom of justified representation, which is used to capture proportionality/fairness in multi-winner voting with approval preferences, is shown that not well-suited for the facility location setting. Hence, a relaxation of this axiom is provided to handle incompatibilities.

In Chapter 5, both groups and fairness are considered, i.e., group-fair facility location games. Two well-motivated group-fair objectives are explored, and many natural group-fair objectives are shown to have an unbounded approximation ratio. Hence, this thesis focuses on minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, existing classical mechanisms (e.g., median) and new group-based mechanisms are provided with bounded approximation ratios, where the group-based mechanisms can achieve better ratios. Lower bounds are also provided for both objectives. A new notion of intergroup and intragroup fairness (IIF) is proposed to measure fairness between groups and within each group, including new mechanisms with tight approximation ratios for two IIF objectives. Moreover, altruistic agents are also considered, where agents care about not only themselves but also their group members.

Date of Award	2 May 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor)