We study various models for the one-dimensional multi-stage facility location problems with transient agents, where a transient agent arrives in some stage and stays for a number of consecutive stages. In the problems, we need to serve each agent in one of their stages by determining the location of the facility at each stage. In the first model, we assume there is no cost for moving the facility across the stages. We focus on optimal algorithms to minimize both the social cost objective, defined as the total distance of all agents to the facility over all stages, and the maximum cost objective, defined as the max distance of any agent to the facility over all stages. For each objective, we give a slice-wise polynomial (XP) algorithm (i.e., solvable in mf(k) for some fixed parameter k and computable function f, where m is the input size) and show that there is a polynomial-time algorithm when a natural first-come-first-serve (FCFS) order of agent serving is enforced. We then consider the mechanism design problem, when the agents' locations and arrival stages are private, and design a group strategy-proof mechanism that achieves good approximation ratios for both objectives and settings with and without FCFS ordering. In the second model, we consider the facility's moving cost between adjacent stages under the social cost objective, which accounts for the total moving distance of the facility. Correspondingly, we design XP (and polynomial time) algorithms and a group strategy-proof mechanism for settings with or without the FCFS ordering.
|Title of host publication||AAAI-23 Technical Tracks 5|
|Editors||Brian Williams, Yiling Chen, Jennifer Neville|
|Place of Publication||Washington|
|Number of pages||8|
|Publication status||Published - 27 Jun 2023|
|Event||37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States|
Duration: 7 Feb 2023 → 14 Feb 2023
|Name||Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023|
|Conference||37th AAAI Conference on Artificial Intelligence, AAAI 2023|
|Period||7/02/23 → 14/02/23|
Bibliographical noteFunding Information:
We gratefully acknowledge funding from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. UGC/FDS13/E01/20), and by NSFC No.62202100. Hau Chan is supported by the National Institute of General Medical Sciences of the National Institutes of Health [P20GM130461] and the Rural Drug Addiction Research Center at the University of Nebraska-Lincoln. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health or the University of Nebraska.
Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
- GTEP: Social Choice / Voting
- GTEP: Game Theory
- GTEP: Mechanism Design
- Mechanism Design