Author name cluster

Xingchen Sha

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Large Language Models for Designing Participatory Budgeting Rules

Nguyen Thach
Xingchen Sha
Hau Chan

Participatory budgeting (PB) is a democratic paradigm for deciding the funding of public projects given the residents’ preferences, which has been adopted in numerous cities across the world. The main focus of PB is designing rules, functions that return feasible budget allocations for a set of projects subject to some budget constraint. Designing PB rules that optimize both utility and fairness objectives based on agent preferences had been challenging due to the extensive domain knowledge required and the proven trade-off between the two notions. Recently, large language models (LLMs) have been increasingly employed for automated algorithmic design. Given the resemblance of PB rules to algorithms for classical knapsack problems, in this paper, we introduce a novel framework, named LLMRule, that addresses the limitations of existing works by incorporating LLMs into an evolutionary search procedure for automating the design of PB rules. Our experimental results, evaluated on more than 600 real-world PB instances obtained from the U. S. , Canada, Poland, and the Netherlands with different representations of agent preferences, demonstrate that the LLM-generated rules generally outperform existing handcrafted rules in terms of overall utility while still maintaining a similar degree of fairness.

PDF

AAAI Conference 2025 Conference Paper

Facility Location Games with Optional Preferences: A Revisit

Xingchen Sha
Shuyu Bao
Hau Chan
Vincent Chau
Ken C. K. Fong
Minming Li

We study the k-facility location games with optional preferences on the line. In the games, each strategic agent has a public location preference on the k facility locations and a private optional preference on the preferred/acceptable set of facilities out of the k facilities. Our goal is to design strategyproof mechanisms to elicit agents’ optional preferences and locate k facilities to minimize the social or maximum cost of agents based on their facility preferences and public agent locations. We consider two variants of the facility location games with optional preferences: the Min variant and the Max variant where the agent’s cost is defined as their distance to the closest acceptable facility and the farthest acceptable facility, respectively. For the Min variant, we present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost with k ≥ 3 facilities, achieving approximation ratios of 3 and 2n+1 respectively. We complement the results by establishing lower bounds of 3/2 and n/4 for the approximation ratios achievable by any deterministic strategyproof mechanisms for the maximum cost and social cost, respectively. We then improve our results in a special setting of the Min variant where there are exactly three facilities and present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost. For the Max variant, we present an optimal deterministic strategyproof mechanism for the maximum cost and a k-approximation deterministic strategyproof mechanism for the social cost.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Group Fairness in Multi-period Mobile Facility Location Problems

Haris Aziz
Hau Chan
Xingchen Sha
Toby Walsh
Lirong Xia

We study the group-fair multi-period mobile facility location problems, where agents from different groups are located on a real line and arrive in different periods. Our goal is to locate 𝑘 mobile facilities at each period to serve the arriving agents in order to minimize the maximum total group-fair cost and the maximum average group-fair cost objectives that measure the costs or distances of groups of agents to their corresponding facilities across all periods. We first consider the problems from the algorithmic perspective for both group-fair cost objectives. We then consider the problems from the mechanism design perspective, where the agents’ locations and arrival periods are private. For both objectives, we design deterministic strategyproof mechanisms to elicit the agents’ locations and arrival periods truthfully while optimizing the group-fair cost objectives and show that our mechanisms have almost tight bounds on the approximation ratios for certain periods and settings. Finally, we discuss the extensions of our results to the online setting where agent arrival information is only known at each period.

PDF

ECAI Conference 2025 Conference Paper

Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space

Xingchen Sha
Hau Chan
Vincent Chau
Ken C. K. Fong
Minming Li
Wai Lun Lo

We consider the k-facility location problems with capacity constraints in bounded location space from the mechanism design perspective. In this problem, we seek to locate k capacity constrained facilities in a bounded interval (i. e. , B=[bl, br]) to serve agents, who have preferences on the ideal locations of the facilities in the interval. Our goal is to design strategyproof mechanisms to elicit agents’ true ideal locations and locate facilities that minimize the social cost and maximum cost, which are defined to be the sum and the maximum of the agents’ costs (i. e. , agents’ distances to their facilities), respectively. For the equal capacity setting without spare capacity (i. e. , all the agents can be served exactly), we provide a deterministic strategyproof mechanism. For any bounded interval (i. e. , bl, br∈R), our mechanism has approximation ratios of n-1 for the social cost and 4 for the maximum cost with k≥3 facilities and n≥3 agents. We also establish lower bounds of n/2 for the social cost by a common class of deterministic mechanisms that order agents from left to right, and 2 for the maximum cost by any deterministic mechanism. Our mechanism also achieves tight bounds for both costs with k<3 facilities. We then consider the equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity. For these two settings and any bounded interval, we provide randomized strategyproof mechanisms with approximation ratios of n/2 for the social cost and 2 for the maximum cost with any number of facilities. We complement this result by establishing lower bounds of 5/3 for the social cost and 3/2 for the maximum cost.

Details