Multi-Stage Facility Location Problems with Transient Agents

Xuezhen WANG, Vincent CHAU*, Hau CHAN, Ken C. K. FONG, Minming LI

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Referred Conference Paperpeer-review


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.

Original languageEnglish
Title of host publicationAAAI-23 Technical Tracks 5
EditorsBrian Williams, Yiling Chen, Jennifer Neville
Place of PublicationWashington
PublisherAAAI press
Number of pages8
ISBN (Electronic)9781577358800
Publication statusPublished - 27 Jun 2023
Event37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States
Duration: 7 Feb 202314 Feb 2023

Publication series

NameProceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023


Conference37th AAAI Conference on Artificial Intelligence, AAAI 2023
Country/TerritoryUnited States

Bibliographical note

Funding 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.

Publisher Copyright:
Copyright © 2023, Association for the Advancement of Artificial Intelligence ( All rights reserved.


  • GTEP: Social Choice / Voting
  • GTEP: Game Theory
  • GTEP: Mechanism Design
  • MAS
  • Mechanism Design


Dive into the research topics of 'Multi-Stage Facility Location Problems with Transient Agents'. Together they form a unique fingerprint.

Cite this