In recent decades, there has been a notable surge of applicational and theoretical interests in facility location problems within the "elds of mechanism design and social choice. For instance, the increased interest in these problems is due to their potential ability to capture and model various real-world preference aggregation scenarios (e.g., voting [4,5,15] and site locations [6,16]). In the most general setting of facility location problems in these "elds, a social planner aims to locate facilities to serve agents that have preferences on the facility locations within a given region in order to optimize the total or maximum cost objective, which measures the total or maximum distances of the agents to their allocated facilities, respectively.
While most existing studies have focused on the static aspects of facility location problems, recent studies [7-9, 11, 17-19] have started to consider the multi-period aspects of the problems that often deal with locating or reallocating some forms of mobile facilities (e.g., mobile health clinic services or blood donation centers) within some regions over multiple periods. For example, consider a mobile vaccination vehicle that provides certain medical services for residents, who may choose di!erent time periods to be vaccinated at preferred locations. Therefore, the health providers need to decide where to locate several vehicles over di!erent time periods. Beyond health services, the problems can also be applied to determining the locations of polling centers at di!erent periods by taking into consideration agent location preferences and availabilities [10,12]. Finally, the multi-period mobile settings can also model problems that are not geographical in nature (e.g., general preference aggregation [1][2][3]15]). We refer the readers to other related work [17] for more relevant motivations and examples of mobile facilities.
However, there has been a lack of consideration of group fairness in multi-period mobile studies. As a result, existing models and approaches can lead to certain groups of agents incurring signi"cantly higher costs than other groups of agents. Such a lack of consideration is often not ideal in modern society, especially when providing medical, polling, and education services to groups of agents from di!erent social and economic backgrounds. Therefore, we examine group fairness in multi-period facility location problems, focusing on locating facilities to serve groups of agents fairly over multiple periods subject to group-fair cost objectives over multiple periods.
In a group-fair multi-period mobile facility location problem (GF-MPMFLP), we have a set 𝑀 = {1, . . . , 𝑁} of 𝑁 agents, where each agent will be served once over 𝑂 → 1 periods. The agents are partitioned into 𝑃 → 1 disjoint groups based on their associations (e.g., ages, ethnicities, and needs). Let 𝑄 = {𝑄 1 , . . . , 𝑄 𝐿 } be the set of disjoint groups of the agents. We use |𝑄 𝑀 | to denote the total number of agents in group 𝑄 𝑀 . Without loss of generality, we assume |𝑄 𝑀 | > 0 for each 𝑅 = 1, . . . ,𝑃.
Each agent 𝑆 ↑ 𝑀 has a pro"le 𝑇 𝑁 = (𝑈 𝑁 , 𝑉 𝑁 , 𝑅 𝑁 ) where the agent location preference is 𝑈 𝑁 ↑ R, the arrival period is 𝑉 𝑁 ↑ {1, . . . ,𝑂 }, and the group membership is 𝑅 𝑁 ↑ {1, . . . ,𝑃}. A tuple 𝑇 = (𝑇 1 , . . . , 𝑇 𝑂 ) is a collection of locations, arrival periods, and group memberships.
𝐿 facilities are located to serve all the agents arriving at each period. We denote the facility 𝑊's location in period 𝑋 as 𝑌 𝑃 𝑄 ↑ R, and let 𝑌 𝑃 = (𝑌 𝑃 1 , . . . , 𝑌 𝑃 𝑅 ) ↑ R 𝑅 be the locations of 𝐿 facilities in period 𝑋. A deterministic algorithm (resp. mechanism) is a function 𝑍 that maps each tuple 𝑇 to the facility locations of all periods, i.e., 𝑍 (𝑇 ) = (𝑌 1 , . . . , 𝑌 𝑆 ) ↑ R 𝑆 ↓𝑅 . Given 𝑍 and a tuple 𝑇 , the cost of an agent 𝑆 is the distance between their preferred location and the closest facility in their arrival period, i.e., 𝑎𝑏𝑐𝑋 (𝑍 (𝑇 ), 𝑈 𝑁 , 𝑉 𝑁 ) = min 1↔ 𝑄 ↔𝑅 |𝑌 𝑇 𝐿 𝑄 ↗ 𝑈 𝑁 |. Following the existing studies of facility location problems with group fairness [13,14,20], we aim to minimize two group-fair cost objectives: the maximum total group cost (𝑃𝑋𝑅𝑎) and maximum average group cost (𝑃𝑉𝑅𝑎). Given a tuple 𝑇 and a function 𝑍 , 𝑃𝑋𝑅𝑎 is de"ned as
Moreover, 𝑃𝑉𝑅𝑎 is de"ned as
From the mechanism design perspective, because the agents' locations and arrival periods are private, our goal is to design strategyproof mechanisms to elicit their true information while simultaneously determining facility locations to optimize 𝑃𝑋𝑅𝑎 and 𝑃𝑉𝑅𝑎 objectives. Denote (𝑇 ↘ 𝑁 , 𝑇 ↗𝑁 ) as the tuple 𝑇 with 𝑇 ↘ 𝑁 in place of 𝑇 𝑁 .
A deterministic mechanism 𝑍 is strategyproof if for any tuple 𝑇 , any agent 𝑆 can never bene!t by misreporting their location or arrival period regardless of the pro!les of other agents. That is, for all agents, 𝑇 and 𝑇 ↘ 𝑁 = (𝑈 ↘ 𝑁 , 𝑉 ↘ 𝑁 , 𝑅 𝑁 ), we have, 𝑎𝑏𝑐𝑋 (𝑍 (𝑇 ), 𝑈 𝑁 , 𝑉 𝑁 ) ↔ 𝑎𝑏𝑐𝑋 (𝑍 ((𝑇 ↘ 𝑁 , 𝑇 ↗𝑁 )), 𝑈 𝑁 , 𝑉 𝑁 ).
An algorithm (resp. mechanism) 𝑍 achieves an approximation ratio of 𝑑 for minimizing the 𝑃𝑋𝑅𝑎 (resp. 𝑃𝑉𝑅𝑎) in the o#ine setting, if for any pro"le 𝑇 , 𝑃𝑋𝑅𝑎 (𝑇, 𝑍 ) ↔ 𝑑 • 𝑃𝑋𝑅𝑎 (𝑇, 𝑒𝑓𝑂 ) (resp. 𝑃𝑉𝑅𝑎 (𝑇, 𝑍 ) ↔ 𝑑 • 𝑃𝑉𝑅𝑎 (𝑇, 𝑒𝑓𝑂 )) where 𝑒𝑓𝑂 is the optimal algorithm that minimizes the 𝑃𝑋𝑅𝑎 (resp. 𝑃𝑉𝑅𝑎) in the o#ine setting, i.e., with complete knowledge of the agents' information at all periods. Similarly, an algorithm (resp. mechanism) 𝑍 achieves a competitive ratio of 𝑑 for minimizing the 𝑃𝑋𝑅𝑎 (resp. 𝑃𝑉𝑅𝑎) in the online setting, if for any pro"le 𝑇 , 𝑃𝑋𝑅𝑎 (𝑇, 𝑍 ) ↔ 𝑑 • 𝑃𝑋𝑅𝑎 (𝑇, 𝑒𝑓𝑂 ) (resp. 𝑃𝑉𝑅𝑎 (𝑇, 𝑍 ) ↔ 𝑑 • 𝑃𝑉𝑅𝑎 (𝑇, 𝑒𝑓𝑂 )) where 𝑒𝑓𝑂 is the optimal algorithm that minimizes the 𝑃𝑋𝑅𝑎 (resp. 𝑃𝑉𝑅𝑎) in the o#ine setting.
We study the group-fair multi-period mobile facility location problems (GF-MPMFLPs) from both algorithmic and mechanism design perspectives. We summarize our contributions below for di!erent settings from both perspectives. • From the algorithmic perspective, the locations and arrival periods of the agents are publicly known. Our contributions are as follows.
-For the single facility setting (𝐿 = 1), we show that GF-MPMFLPs can be solved in polynomial time using linear programming for both 𝑃𝑋𝑅𝑎 and 𝑃𝑉𝑅𝑎 objectives. -For the setting with 𝐿 facilities, we give a slice-wise polynomial (𝑔𝑓) algorithm (i.e., solvable in time 𝑁 𝑉 (𝑅 ) for some "xed parameter 𝐿 and computable function 𝑌 , where 𝑁 is the input size) to solve the GF-MPMFLPs for both 𝑃𝑋𝑅𝑎 and 𝑃𝑉𝑅𝑎 objectives. • From the mechanism design perspective, the location and arrival period preferences of the agents are privately known to the agents themselves. We design several mechanisms that elicit the true locations and arrival periods of the agents while simultaneously optimizing the 𝑃𝑋𝑅𝑎 and 𝑃𝑉𝑅𝑎 objectives based on the agents' reported information. Table 1 summarizes our mechanism design results. • We additionally consider the online GF-MPMFLPs from mechanism design perspective, where the agent arrival information is only known at each period. For the single facility setting (𝐿 = 1), we establish almost tight bounds for the 𝑃𝑋𝑅𝑎 objective. We also show that our deterministic strategyproof mechanism has a competitive ratio of 2(𝑁 ↗𝑃 +1) for the 𝑃𝑉𝑅𝑎 objective, and complement this result with a lower bound of 𝑁 ↗ 𝑃 + 1 for the 𝑃𝑉𝑅𝑎 objective. For the setting with more facilities, we show that our previous results can all be extended to the online version.
We refer readers to the full paper for complete results and proofs.