Hau Chan

AAAI Conference 2026 Conference Paper

Centralized Group Equitability and Individual Envy-Freeness in the Allocation of Indivisible Items

• Ying Wang
• Jiaqian Li
• Tianze Wei
• Hau Chan
• Minming Li

We study the fair allocation of indivisible items to groups of agents from the perspectives of both the agents and a centralized allocator. In our setting, the centralized allocator aims to ensure that the allocation is fair both among the groups and between individual agents. This setting applies to many real-world scenarios, such as when a school administrator allocates resources (e.g., office spaces and supplies) to staff members within departments or when a city council allocates limited housing units to families in need across different communities. To ensure fairness between agents, we consider the classical notion of envy-freeness (EF). To ensure fairness among groups, we introduce the notion of centralized group equitability (CGEQ), which captures fairness for groups from the centralized allocator’s perspective. Because an EF or CGEQ allocation does not always exist in general, we consider their natural relaxations: envy-freeness to one item (EF1) and centralized group equitability up to one item (CGEQ1). For different classes of valuation functions of the agents and the centralized allocator, we show that allocations satisfying both EF1 and CGEQ1 always exist, and we design efficient algorithms to compute such allocations. We also consider the centralized group maximin share (CGMMS) from the centralized allocator's perspective as a group-level fairness objective with EF1 for agents, and present several results.

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.

AAMAS Conference 2026 Conference Paper

Obnoxious Facility Location Problems: Strategyproof Mechanisms Optimizing L p -Aggregated Utilities and Costs

• Hau Chan
• Jianan Lin
• Chenhao Wang

We study the problem of locating a single obnoxious facility on the normalized line segment [0, 1] with strategic agents from a mechanism design perspective. Each agent has a preference for the undesirable location of the facility and would prefer the facility to be far away from their location. We consider the utility of the agent, defined as the distance between the agent’s location and the facility location, and the cost of each agent, equal to one minus the utility. Given this standard setting of obnoxious facility location problems, our goal is to design (group) strategyproof mechanisms to elicit agent locations truthfully and determine facility location approximately optimizing the 𝐿𝑝-aggregated utility and cost objectives, which generalizes the 𝐿𝑝-norm (𝑝 ≥ 1) of the agents’ utilities and agents’ costs to any 𝑝 ∈ [−∞, ∞], respectively. We establish upper and lower bounds on the approximation ratios of deterministic and randomized (group) strategyproof mechanisms for maximizing the 𝐿𝑝-aggregated utilities or minimizing the 𝐿𝑝-aggregated costs across the range of 𝑝-values. While there are gaps between upper and lower bounds for randomized mechanisms, our bounds for deterministic mechanisms are tight.

JAAMAS Journal 2026 Journal Article

Strategyproof facility location with prediction: minimizing the maximum cost

• Hau Chan
• Jianan Lin
• Chenhao Wang

Abstract We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to imperfect predictions of the optimal facility locations. Our objective is to design strategyproof (SP) mechanisms that truthfully elicit agents’ preferences over facility locations and, using the given prediction, select a facility location that approximately minimizes the maximum cost among all agents. In particular, we seek SP mechanisms whose approximation guarantees depend on the prediction error: they should achieve improved performance when the prediction is accurate (the property of consistency ) while still ensuring strong worst-case guarantees when the prediction is arbitrarily inaccurate (the property of robustness ). On the real line, we characterize all deterministic SP mechanisms with consistency strictly better than 2 and bounded robustness for the maximum cost. We show that any such mechanism must coincide with the MinMaxP mechanism, which returns the prediction if it lies between the two extreme agent locations and otherwise returns the agent location closest to the prediction. For any prediction error \(\eta \ge 0\), we prove that MinMaxP achieves a \((1+\min (1, \eta ))\) -approximation and that no deterministic SP mechanism can obtain a better approximation ratio. In addition, for two-dimensional spaces with the \(\ell ^p\) distance, we analyze the approximation guarantees of a deterministic mechanism that applies MinMaxP independently on each coordinate, as well as a randomized mechanism that selects between two deterministic mechanisms with carefully chosen probabilities. We further extend these results to the \(L_p\) -norm social cost objective on the line metric and the maximum cost objective on the tree metric. Finally, we examine the group strategyproofness of the mechanisms.

IJCAI Conference 2025 Conference Paper

Distance Preservation Games

• Haris Aziz
• Hau Chan
• Patrick Lederer
• Shivika Narang
• Toby Walsh

We introduce and analyze distance preservation games (DPGs). In DPGs, agents express ideal distances to other agents and need to choose locations in the unit interval while preserving their ideal distances as closely as possible. We analyze the existence and computation of location profiles that are jump stable (i. e. , no agent can benefit by moving to another location) or welfare optimal for DPGs, respectively. Specifically, we prove that there are DPGs without jump stable location profiles and identify important cases where such outcomes always exist and can be computed efficiently. Similarly, we show that finding welfare optimal location profiles is NP-complete and present approximation algorithms for finding solutions with social welfare close to optimal. Finally, we prove that DPGs have a price of anarchy of at most 2.

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.

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.

AAAI Conference 2025 Conference Paper

Mechanism Design for Connecting Regions Under Disruptions

• Hau Chan
• Jianan Lin
• Zining Qin
• Chenhao Wang

Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.

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.

ICLR Conference 2025 Conference Paper

MuHBoost: Multi-Label Boosting For Practical Longitudinal Human Behavior Modeling

• Nguyen T. Thach
• Patrick Habecker
• Anika R. Eisenbraun
• Alex Mason
• Kimberly Tyler
• Bilal Khan 0002
• Hau Chan

Longitudinal human behavior modeling has received increasing attention over the years due to its widespread applications to patient monitoring, dietary and lifestyle recommendations, and just-in-time intervention for at-risk individuals (e.g., problematic drug users and struggling students), to name a few. Using in-the-moment health data collected via ubiquitous devices (e.g., smartphones and smartwatches), this multidisciplinary field focuses on developing predictive models for certain health or well-being outcomes (e.g., depression and stress) in the short future given the time series of individual behaviors (e.g., resting heart rate, sleep quality, and current feelings). Yet, most existing models on these data, which we refer to as ubiquitous health data, do not achieve adequate accuracy. The latest works that yielded promising results have yet to consider realistic aspects of ubiquitous health data (e.g., containing features of different types and high rate of missing values) and the consumption of various resources (e.g., computing power, time, and cost). Given these two shortcomings, it is dubious whether these studies could translate to realistic settings. In this paper, we propose MuHBoost, a multi-label boosting method for addressing these shortcomings, by leveraging advanced methods in large language model (LLM) prompting and multi-label classification (MLC) to jointly predict multiple health or well-being outcomes. Because LLMs can hallucinate when tasked with answering multiple questions simultaneously, we also develop two variants of MuHBoost that alleviate this issue and thereby enhance its predictive performance. We conduct extensive experiments to evaluate MuHBoost and its variants on 13 health and well-being prediction tasks defined from four realistic ubiquitous health datasets. Our results show that our three developed methods outperform all considered baselines across three standard MLC metrics, demonstrating their effectiveness while ensuring resource efficiency.

AAAI Conference 2025 Conference Paper

Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu
• Long Tran-Thanh

We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy, Granularity-based Pricing (GAP), which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln B) on the alpha-regret where n, v_{max}, c_{min}, and B are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its alpha-regret is at most O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln2 B). We also provide an alpha-regret lower bound Omega(v_{max}sqrt{Bn/c_{min}}) of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms.

UAI Conference 2025 Conference Paper

Pure and Strong Nash Equilibrium Computation in Compactly Representable Aggregate Games

• Jared Soundy
• Mohammad T. Irfan
• Hau Chan

Aggregate games model interdependent decision making when an agent’s utility depends on their own choice and the aggregation of everyone’s choices. We define a compactly representable subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We study computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE). We show that PNE existence is NP-complete for very simple cases of additive aggregate games. We devise an efficient algorithmic scheme for deciding the existence of a PNE and computing one (if it exists) for bounded aggregate space. We also give an approximation algorithm for a special type of additive aggregate games. For SNE, we show that SNE recognition is co-NP-complete and SNE existence is $\Sigma^P_2$-complete, even for simple types of additive aggregate games. For broad classes, we provide several novel and efficient aggregate-space algorithms for recognizing an SNE and deciding the existence of an SNE. Finally, we connect our results to several popular classes of games and show how our computational schemes can shed new light on these games.

AAMAS Conference 2025 Conference Paper

Pure Nash Equilibrium and Strong Nash Equilibrium Computation in Additive Aggregate Games

• Jared Soundy
• Mohammad T. Irfan
• Hau Chan

Aggregate games, first conceptualized by Nobel laureate Reinhard Selten in 1970, model the decision-making of interdependent agents where each agent’s utility depends on their own action and the aggregation of everyone’s actions. We consider computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE) for aggregate games. On the way, we define a new subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We show that PNE existence is NPcomplete for very simple cases of additive aggregate games. We devise an efficient aggregate-space algorithm for determining the existence of a PNE and computing one (if exists) for bounded aggregate space. For SNE, we show that SNE recognition is co-NPcomplete and SNE existence is Σ𝑃 2 -complete, even for simple types of additive aggregate games. For large classes of aggregate games, we provide several novel and efficient aggregate-space algorithms for recognizing an SNE and deciding the existence of an SNE. Finally, we connect our results to several well-studied subclasses of aggregate games and show how our computational schemes can shed new light into these games.

ECAI Conference 2025 Conference Paper

Strategyproof Mechanisms for Facility Location with Prediction Under the Maximum Cost Objective

• Hau Chan
• Jianan Lin 0001
• Chenhao Wang 0001

We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to an imperfect prediction of optimal facility locations. Our goal is to design strategyproof (SP) mechanisms to elicit agent preferences on the facility locations truthfully and, leveraging the given imperfect prediction, determine the facility location that approximately minimizes the maximum cost among all agents. In particular, we seek SP mechanisms whose approximation guarantees depend on the prediction errors — achieve improved guarantees when the prediction is accurate (known as the consistency), while still ensuring robust worst-case performance when the prediction is arbitrarily inaccurate (known as the robustness). When the metric space is the real line, we characterize all deterministic SP mechanisms with consistency strictly less than 2 and bounded robustness: such mechanisms must be the MinMaxP mechanism, which returns the prediction location if it lies between the two extreme agent locations and, otherwise, returns the closest agent location to the prediction. We further show that, for any prediction error η ≥ 0, while MinMaxP is (1 + min(1, η))-approximation, no deterministic SP mechanism can achieve a better approximation. In two-dimensional spaces with the l_p metric, we analyze the approximation guarantees of a deterministic mechanism that runs MinMaxP independently on each coordinate, as well as a randomized mechanism that selects between two deterministic ones with specific probabilities. Finally, we discuss the group strategyproofness of the considered mechanisms.

IJCAI Conference 2024 Conference Paper

A Novel GAN Approach to Augment Limited Tabular Data for Short-Term Substance Use Prediction

• Nguyen Thach
• Patrick Habecker
• Bergen Johnston
• Lillianna Cervantes
• Anika Eisenbraun
• Alex Mason
• Kimberly Tyler
• Bilal Khan

Substance use is a global issue that negatively impacts millions of persons who use drugs (PWUDs). In practice, identifying vulnerable PWUDs for efficient allocation of appropriate resources is challenging due to their complex use patterns (e. g. , their tendency to change usage within months) and the high acquisition costs for collecting PWUD-focused substance use data. Thus, there has been a paucity of machine learning models for accurately predicting short-term substance use behaviors of PWUDs. In this paper, using longitudinal survey data of 258 PWUDs in the U. S. Great Plains collected by our team, we design a novel GAN that deals with high-dimensional low-sample-size tabular data and survey skip logic to augment existing data to improve classification models' prediction on (A) whether the PWUDs would increase usage and (B) at which ordinal frequency they would use a particular drug within the next 12 months. Our evaluation results show that, when trained on augmented data from our proposed GAN, the classification models improve their predictive performance (AUROC) by up to 13. 4% in Problem (A) and 15. 8% in Problem (B) for usage of marijuana, meth, amphetamines, and cocaine, which outperform state-of-the-art generative models.

AAAI Conference 2024 Conference Paper

Altruism in Facility Location Problems

• Houyu Zhou
• Hau Chan
• Minming Li

We study the facility location problems (FLPs) with altruistic agents who act to benefit others in their affiliated groups. Our aim is to design mechanisms that elicit true locations from the agents in different overlapping groups and place a facility to serve agents to approximately optimize a given objective based on agents' costs to the facility. Existing studies of FLPs consider myopic agents who aim to minimize their own costs to the facility. We mainly consider altruistic agents with well-motivated group costs that are defined over costs incurred by all agents in their groups. Accordingly, we define Pareto strategyproofness to account for altruistic agents and their multiple group memberships with incomparable group costs. We consider mechanisms satisfying this strategyproofness under various combinations of the planner's objectives and agents' group costs. For each of these settings, we provide upper and lower bounds of approximation ratios of the mechanisms satisfying Pareto strategyproofness.

IJCAI Conference 2024 Conference Paper

Budget Feasible Mechanisms: A Survey

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu

In recent decades, the design of budget feasible mechanisms for a wide range of procurement auction settings has received significant attention in the Artificial Intelligence (AI) community. These procurement auction settings have practical applications in various domains such as federated learning, crowdsensing, edge computing, and resource allocation. In a basic procurement auction setting of these domains, a buyer with a limited budget is tasked with procuring items (\eg, goods or services) from strategic sellers, who have private information on the true costs of their items and incentives to misrepresent their items' true costs. The primary goal of budget feasible mechanisms is to elicit the true costs from sellers and determine items to procure from sellers to maximize the buyer valuation function for the items and ensure that the total payment to the sellers is no more than the budget. In this survey, we provide a comprehensive overview of key procurement auction settings and results of budget feasible mechanisms. We provide several promising future research directions.

AAMAS Conference 2024 Conference Paper

Computing Nash Equilibria in Multidimensional Congestion Games

• Mohammad T. Irfan
• Hau Chan
• Jared Soundy

We study pure-strategy Nash equilibrium (PSNE) computation in 𝑘-dimensional congestion games (𝑘-DCGs) where the weights or demands of the players are 𝑘-dimensional vectors. We first show that deciding the existence of a PSNE in a 𝑘-DCG is NP-complete even for games when players have binary and unit demand vectors. We then focus on computing PSNE for 𝑘-DCGs and their variants with general, linear, and exponential cost functions. For general cost functions (potentially non-monotonic), we provide the first configuration-space framework to find a PSNE if one exists. For linear and exponential cost functions, we provide potential functionbased algorithms to find a PSNE. These algorithms run in polynomial time under certain assumptions. We also study structured demands and cost functions, giving polynomial-time algorithms to compute PSNE for several cases. For general cost functions, we give a constructive proof of existence for an (𝛼, 𝛽)-PSNE (for certain 𝛼 and 𝛽), where 𝛼 and 𝛽 are multiplicative and additive approximation factors, respectively.

ICML Conference 2024 Conference Paper

Configurable Mirror Descent: Towards a Unification of Decision Making

• Pengdeng Li
• Shuxin Li 0001
• Chang Yang
• Xinrun Wang
• Shuyue Hu
• Xiao Huang 0001
• Hau Chan
• Bo An 0001

Decision-making problems, categorized as single-agent, e. g. , Atari, cooperative multi-agent, e. g. , Hanabi, competitive multi-agent, e. g. , Hold’em poker, and mixed cooperative and competitive, e. g. , football, are ubiquitous in the real world. Although various methods have been proposed to address the specific decision-making categories, these methods typically evolve independently and cannot generalize to other categories. Therefore, a fundamental question for decision-making is: Can we develop a single algorithm to tackle ALL categories of decision-making problems? There are several main challenges to address this question: i) different decision-making categories involve different numbers of agents and different relationships between agents, ii) different categories have different solution concepts and evaluation measures, and iii) there lacks a comprehensive benchmark covering all the categories. This work presents a preliminary attempt to address the question with three main contributions. i) We propose the generalized mirror descent (GMD), a generalization of MD variants, which considers multiple historical policies and works with a broader class of Bregman divergences. ii) We propose the configurable mirror descent (CMD) where a meta-controller is introduced to dynamically adjust the hyper-parameters in GMD conditional on the evaluation measures. iii) We construct the GameBench with 15 academic-friendly games across different decision-making categories. Extensive experiments demonstrate that CMD achieves empirically competitive or better outcomes compared to baselines while providing the capability of exploring diverse dimensions of decision making.

UAI Conference 2024 Conference Paper

Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches

• Mohammad T. Irfan
• Hau Chan
• Jared Soundy

We present algorithms of two flavors{—}one rooted in constraint satisfaction problems (CSPs) and the other in learning dynamics{—}to compute pure-strategy Nash equilibrium (PSNE) in k-dimensional congestion games (k-DCGs) and their variants. The two algorithmic approaches are driven by whether or not a PSNE is guaranteed to exist. We first show that deciding the existence of a PSNE in a k-DCG is NP-complete even when players have binary and unit demand vectors. For general cost functions (potentially non-monotonic), we devise a new CSP-inspired algorithmic framework for PSNE computation, leading to algorithms that run in polynomial time under certain assumptions while offering exponential savings over standard CSP algorithms. We further refine these algorithms for variants of k-DCGs. Our experiments demonstrate the effectiveness of this new CSP framework for hard, non-monotonic k-DCGs. We then provide learning dynamics-based PSNE computation algorithms for linear and exponential cost functions. These algorithms run in polynomial time under certain assumptions. For general cost, we give a learning dynamics algorithm for an (\ensuremath{(\alpha, \beta)})-approximate PSNE (for certain \ensuremath{\alpha} and \ensuremath{\beta}). Lastly, we also devise polynomial-time algorithms for structured demands and cost functions.

AAMAS Conference 2024 Conference Paper

Grasper: A Generalist Pursuer for Pursuit-Evasion Problems

• Pengdeng Li
• Shuxin Li
• Xinrun Wang
• Jakub Čern&yacute;
• Youzhi Zhang
• Stephen McAleer
• Hau Chan
• Bo An

Pursuit-evasion games (PEGs) model interactions between a team of pursuers and an evader in graph-based environments such as urban street networks. Recent advancements have demonstrated the effectiveness of the pre-training and fine-tuning paradigm in Policy-Space Response Oracles (PSRO) to improve scalability in solving large-scale PEGs. However, these methods primarily focus on specific PEGs with fixed initial conditions that may vary substantially in real-world scenarios, which significantly hinders the applicability of the traditional methods. To address this issue, we introduce Grasper, a GeneRAlist purSuer for Pursuit-Evasion pRoblems, capable of efficiently generating pursuer policies tailored to specific PEGs. Our contributions are threefold: First, we present a novel architecture that offers high-quality solutions for diverse PEGs, comprising critical components such as (i) a graph neural network (GNN) to encode PEGs into hidden vectors, and (ii) a hypernetwork to generate pursuer policies based on these hidden vectors. As a second contribution, we develop an efficient three-stage training method involving (i) a pre-pretraining stage for learning robust PEG representations through self-supervised graph learning techniques like graph masked auto-encoder (Graph- MAE), (ii) a pre-training stage utilizing heuristic-guided multi-task pre-training (HMP) where heuristic-derived reference policies (e. g. , through Dijkstra’s algorithm) regularize pursuer policies, and (iii) a fine-tuning stage that employs PSRO to generate pursuer policies on designated PEGs. Finally, we perform extensive experiments on synthetic and real-world maps, showcasing Grasper’s significant superiority over baselines in terms of solution quality and generalizability. We demonstrate that Grasper provides a versatile ∗Equal contribution. †Corresponding author. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J. S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). approach for solving pursuit-evasion problems across a broad range of scenarios, enabling practical deployment in real-world situations.

ECAI Conference 2024 Conference Paper

Mechanism Design for Extending the Accessibility of Facilities

• Hau Chan
• Jianan Lin 0001
• Chenhao Wang 0001
• Yanxi Xie

We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In such a variation, agents have preferences on the ideal locations of the facility on a real line, and the facility’s location is fixed in advance where (re)locating the facility is not possible due to various constraints (e. g. , limited space and construction costs). To improve the accessibility of agents to facilities, existing mechanism design literature in FLPs has proposed to structurally modify the real line (e. g. , by adding a new interval) or provide shuttle services between two points when structural modifications are not possible. In this paper, we focus on the latter approach and propose to construct an accessibility range to extend the accessibility of the facility. In the range, agents can receive accommodations (e. g. , school buses, campus shuttles, or pickup services) to help reach the facility. Therefore, the cost of each agent is the distance from their ideal location to the facility (possibility) through the range. We focus on designing strategyproof mechanisms that elicit true ideal locations from the agents and construct accessibility ranges (intervals) to approximately minimize the social cost or the maximum cost of agents. For both social and maximum costs, we design group strategyproof mechanisms and strong group strategyproof mechanisms with (asymptotically) tight bounds on the approximation ratios.

AAMAS Conference 2024 Conference Paper

Mechanism Design for Reducing Agent Distances to Prelocated Facilities

• Hau Chan
• Xinliang Fu
• Minming Li
• Chenhao Wang

We consider a variant of facility location problems where the facility is prelocated at a specific position to serve the agents who are located on a real line. Because the facility cannot be relocated due to various constraints (e. g. , construction costs and requirements), the social planner considers the structural modification problem of adding short-cut edges to the real line (e. g. , shuttles between pairs of locations) for improving the accessibility or reducing costs of the agents to the facility, where the cost of an agent is measured by their shortest distance to the facility possibly using the short-cut edges. We focus on the mechanism design aspects of the problems where the agents’ locations are private. We propose several strategy-proof mechanisms that elicit true agent locations and minimize the total or maximum cost of agents. We provide approximation ratios for these mechanisms and lower bounds on the approximation ratios for total or maximum cost.

AAMAS Conference 2024 Conference Paper

Reinforcement Nash Equilibrium Solver

• Xinrun Wang
• Chang Yang
• Shuxin Li
• Pengdeng Li
• Xiao Huang
• Hau Chan
• Bo An

Nash Equilibrium (NE) is the canonical solution concept of game theory, which provides an elegant tool to understand the rationalities. Computing NE in two- or multi-player general-sum games is PPAD-Complete. Therefore, in this work, we propose REinforcement Nash Equilibrium Solver (RENES), which trains a single policy to modify the games with different sizes and applies the solvers on the modified games where the obtained solution is evaluated on the original games. Specifically, our contributions are threefold. i) We represent the games as 𝛼-rank response graphs and leverage graph neural network (GNN) to handle the games with different sizes as inputs; ii) We use tensor decomposition, e. g. , canonical polyadic (CP), to make the dimension of modifying actions fixed for games with different sizes; iii) We train the modifying strategy for games with the widely-used proximal policy optimization (PPO) and apply the solvers to solve the modified games, where the obtained solution is evaluated on original games. Extensive experiments on large-scale normal-form games show that our method can further improve the approximation of NE of different solvers, i. e. , 𝛼-rank, CE, FP and PRD, and can be generalized to unseen games.

IJCAI Conference 2024 Conference Paper

Reinforcement Nash Equilibrium Solver

• Xinrun Wang
• Chang Yang
• Shuxin Li
• Pengdeng Li
• Xiao Huang
• Hau Chan
• Bo An

Nash Equilibrium (NE) is the canonical solution concept of game theory, which provides an elegant tool to understand the rationalities. Though mixed strategy NE exists in any game with finite players and actions, computing NE in two- or multi-player general-sum games is PPAD-Complete. Various alternative solutions, e. g. , Correlated Equilibrium (CE), and learning methods, e. g. , fictitious play (FP), are proposed to approximate NE. For convenience, we call these methods as ``inexact solvers'', or ``solvers'' for short. However, the alternative solutions differ from NE and the learning methods generally fail to converge to NE. Therefore, in this work, we propose REinforcement Nash Equilibrium Solver (RENES), which trains a single policy to modify the games with different sizes and applies the solvers on the modified games where the obtained solution is evaluated on the original games. Specifically, our contributions are threefold. i) We represent the games as alpha-rank response graphs and leverage graph neural network (GNN) to handle the games with different sizes as inputs; ii) We use tensor decomposition, e. g. , canonical polyadic (CP), to make the dimension of modifying actions fixed for games with different sizes; iii) We train the modifying strategy for games with the widely-used proximal policy optimization (PPO) and apply the solvers to solve the modified games, where the obtained solution is evaluated on original games. Extensive experiments on large-scale normal-form games show that our method can further improve the approximation of NE of different solvers, i. e. , alpha-rank, CE, FP and PRD, and can be generalized to unseen games.

IJCAI Conference 2024 Conference Paper

Self-adaptive PSRO: Towards an Automatic Population-based Game Solver

• Pengdeng Li
• Shuxin Li
• Chang Yang
• Xinrun Wang
• Xiao Huang
• Hau Chan
• Bo An

Policy-Space Response Oracles (PSRO) as a general algorithmic framework has achieved state-of-the-art performance in learning equilibrium policies of two-player zero-sum games. However, the hand-crafted hyperparameter value selection in most of the existing works requires extensive domain knowledge, forming the main barrier to applying PSRO to different games. In this work, we make the first attempt to investigate the possibility of self-adaptively determining the optimal hyperparameter values in the PSRO framework. Our contributions are three-fold: (1) Using several hyperparameters, we propose a parametric PSRO that unifies the gradient descent ascent (GDA) and different PSRO variants. (2) We propose the self-adaptive PSRO (SPSRO) by casting the hyperparameter value selection of the parametric PSRO as a hyperparameter optimization (HPO) problem where our objective is to learn an HPO policy that can self-adaptively determine the optimal hyperparameter values during the running of the parametric PSRO. (3) To overcome the poor performance of online HPO methods, we propose a novel offline HPO approach to optimize the HPO policy based on the Transformer architecture. Experiments on various two-player zero-sum games demonstrate the superiority of SPSRO over different baselines.

AAAI Conference 2024 Conference Paper

Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems

• Jiaqian Li
• Minming Li
• Hau Chan

We study the group-fair obnoxious facility location problems from the mechanism design perspective where agents belong to different groups and have private location preferences on the undesirable locations of the facility. Our main goal is to design strategyproof mechanisms that elicit the true location preferences from the agents and determine a facility location that approximately optimizes several group-fair objectives. We first consider the maximum total and average group cost (group-fair) objectives. For these objectives, we propose deterministic mechanisms that achieve 3-approximation ratios and provide matching lower bounds. We then provide the characterization of 2-candidate strategyproof randomized mechanisms. Leveraging the characterization, we design randomized mechanisms with improved approximation ratios of 2 for both objectives. We also provide randomized lower bounds of 5/4 for both objectives. Moreover, we investigate intergroup and intragroup fairness (IIF) objectives, addressing fairness between groups and within each group. We present a mechanism that achieves a 4-approximation for the IIF objectives and provide tight lower bounds.

AAMAS Conference 2023 Conference Paper

Altruism in Facility Location Problems

• Houyu Zhou
• Hau Chan
• Minming Li

We study the facility location problems (FLPs) with altruistic agents who act to benefit others in their affiliated groups. Our aim is to design mechanisms that elicit true locations from the agents in different overlapping groups and locate a facility to serve agents to approximately optimize a given objective based on agents’ costs to the facility. Existing studies of FLPs consider myopic agents who aim to minimize their own costs to the facility, while we mainly consider altruistic agents who consider the group costs incurred by all agents in their groups. Accordingly, we define Pareto strategyproofness to account for this new type of agents and their multiple group memberships with incomparable group costs. We consider mechanisms satisfying this strategyproofness under various combinations of the planner’s objectives and agents’ group costs. For each of these settings, we provide upper and lower bounds of approximation ratios of the mechanisms satisfying the Pareto strategyproofness.

AIJ Journal 2023 Journal Article

Budget-feasible mechanisms for proportionally selecting agents from groups

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu
• Yingchao Zhao

In many social domains involving collective decision-making (e. g. , committee selection and survey sampling), it is often desirable to select individuals from different population groups to achieve proportional representation (e. g. , to represent the opinions of each group). For instance, in the selection of a committee (e. g. , to form a working group within a company), the planner would like to select agents from different groups to represent their respective groups proportionally. Typically, there are intrinsic private costs for agents to represent their groups, and the planner would like to compensate the selected agents via some form of payments, which is constrained by the planner's available budget. As the costs are unknown to the planner, the planner is required to design incentive mechanisms to elicit agents' real costs and provide payments (or monetary incentives) to the selected agents to ensure proportional representation and the total payments do not exceed the budget. Such a mechanism design setting falls into the budget-feasible mechanism design paradigm. However, existing budget-feasible mechanisms only consider all agents to be in the same group with non-proportional objectives. To study the above-mentioned setting, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the overall value of the selected agents from each group is maximized. We study this problem by first considering the setting with homogeneous agents who have identical values to the planner. Depending on agents' membership in the groups, we consider two models: a single group model where each agent belongs to only one group, and a multiple group model where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models that require different selection methods, i. e. , a novel greedy mechanism that considers all possible proportion ratios for the single group model and a novel mechanism that leverages the Max-Flow algorithm to evaluate the proportional representation for the multiple group model, to choose representative agents from each group. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on maximizing the minimum proportional representation of each group. We also provide a matching lower bound for budget-feasible proportion-representative mechanisms. Finally, we non-trivially extend these mechanisms to the settings of heterogeneous agents who can have different values to the planner under the two models.

TCS Journal 2023 Journal Article

Facility location games with ordinal preferences

• Hau Chan
• Zifan Gong
• Minming Li
• Chenhao Wang
• Yingchao Zhao

In this paper we study a novel model of facility location games with ordinal preferences. There is a set of self-interested agents and a set of heterogeneous facilities. Each agent is located on a line and has an ordinal preference over the facilities. Our goal is to design strategyproof mechanisms that elicit true information (preferences and/or locations) from the agents and locate the facilities to minimize both maximum and total cost objectives as well as to maximize both minimum and total utility objectives. For the four possible objectives, we consider the 2-facility settings in which only preferences are private, or locations are private. For each possible combination of the objectives and settings, we provide lower and upper bounds on the approximation ratios of strategyproof mechanisms, which are asymptotically tight up to a constant. Furthermore, we extend some of the results to the multiple-facility setting. Finally, we discuss the generalization of our results when the agents can misreport both locations and preferences, and the case when the approximations are defined additively.

AAMAS Conference 2023 Conference Paper

Mechanism Design for Improving Accessibility to Public Facilities

• Hau Chan
• Chenhao Wang

We consider a variant of the facility location problems where agents are located on a real line and the facility is fixed at a designated location to serve the agents. As the facility cannot be relocated due to various constraints (e. g. , construction costs and regulatory requirements), the social planner considers the structural modification problem of adding a short-cut edge to the real line for improving the accessibility or costs of the agents to the facility, where the cost of an agent is measured by their shortest distance to the facility. For a mechanism design version of the structural modification problem where the agents are assumed to have private locations, we propose several strategy-proof mechanisms to elicit truthful locations from the agents and add a short-cut edge to (approximately) minimize the total cost or maximum cost of agents. We derive the upper bounds of these mechanisms and provide lower bounds on the approximation ratios for both objectives.

AAAI Conference 2023 Conference Paper

Multi-Stage Facility Location Problems with Transient Agents

• Xuezhen Wang
• Vincent Chau
• Hau Chan
• Ken C.K. Fong
• Minming Li

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 m^f(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, where 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.

ICLR Conference 2023 Conference Paper

Population-size-Aware Policy Optimization for Mean-Field Games

• Pengdeng Li
• Xinrun Wang
• Shuxin Li 0001
• Hau Chan
• Bo An 0001

In this work, we attempt to bridge the two fields of finite-agent and infinite-agent games, by studying how the optimal policies of agents evolve with the number of agents (population size) in mean-field games, an agent-centric perspective in contrast to the existing works focusing typically on the convergence of the empirical distribution of the population. To this end, the premise is to obtain the optimal policies of a set of finite-agent games with different population sizes. However, either deriving the closed-form solution for each game is theoretically intractable, training a distinct policy for each game is computationally intensive, or directly applying the policy trained in a game to other games is sub-optimal. We address these challenges through the \textbf{P}opulation-size-\textbf{A}ware \textbf{P}olicy \textbf{O}ptimization (PAPO). Our contributions are three-fold. First, to efficiently generate efficient policies for games with different population sizes, we propose PAPO, which unifies two natural options (augmentation and hypernetwork) and achieves significantly better performance. PAPO consists of three components: i) the population-size encoding which transforms the original value of population size to an equivalent encoding to avoid training collapse, ii) a hypernetwork to generate a distinct policy for each game conditioned on the population size, and iii) the population size as an additional input to the generated policy. Next, we construct a multi-task-based training procedure to efficiently train the neural networks of PAPO by sampling data from multiple games with different population sizes. Finally, extensive experiments on multiple environments show the significant superiority of PAPO over baselines, and the analysis of the evolution of the generated policies further deepens our understanding of the two fields of finite-agent and infinite-agent games.

IJCAI Conference 2022 Conference Paper

Analyzing and Designing Strategic Environments in Social Domains

• Hau Chan

The cross-fertilization of AI and economic concepts has led to the advanced development of novel computational ideas. These ideas include models and approaches for analyzing multi-agent interaction (via game-theoretic models and solution concepts) in strategic environments and designing strategic environments (via mechanism design) to address principal decision-making problems involving multi-agent within various social contexts. In what follows, we will discuss our works on these two main topics. For analyzing multi-agent interaction, we will discuss several computational game-theoretic models to capture various agent characteristics and social (e. g. , self-organization) domains. For designing strategic environments, we will discuss principal decision-making mechanism design settings in various social (e. g. , facility location) contexts where the principal has to design mechanisms that elicit agent preferences over social outcomes and implement the principal's desirable social outcomes.

TCS Journal 2022 Journal Article

Monotone k-submodular secretary problems: Cardinality and knapsack constraints

• Zhongzheng Tang
• Chenhao Wang
• Hau Chan

In this paper, we consider the k-submodular secretary problem, in which the items or secretaries arrive one by one in a uniformly random order, and the goal is to select k disjoint sets of items, so as to maximize the expectation of a monotone non-negative k-submodular function. A decision for each item must be made immediately and irrevocably after its arrival: accept and assign it to one of the k dimensions, or reject it. We first show that, in the unconstrained setting, there is an offline algorithm that can be transformed to a k 2 k − 1 -competitive online algorithm, which is asymptotically the best possible. For the problem with cardinality constraints, we present online algorithms with provable performance guarantees for the total size constraint and individual size constraint settings that depend on the corresponding budget parameters. For the problem under a knapsack constraint, we provide a constant-competitive online algorithm.

JAIR Journal 2022 Journal Article

Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results

• Dominik Peters
• Lan Yu
• Hau Chan
• Edith Elkind

A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989b) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin–Courant rule for preferences single-peaked on trees. We show that in this setting the egalitarian version of this rule admits a polynomial-time winner determination algorithm. For the utilitarian version, we prove that winner determination remains NP-hard for the Borda scoring function; indeed, this hardness results extends to a large family of scoring functions. However, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We then explore the power and limitations of this framework: we develop polynomial-time algorithms to find trees with the smallest maximum degree, diameter, or pathwidth, but show that it is NP-hard to check whether a given profile is single-peaked on a tree that is isomorphic to a given tree, or on a regular tree.

AAAI Conference 2022 Conference Paper

Sequential Blocked Matching

• Nicholas Bishop
• Hau Chan
• Debmalya Mandal
• Long Tran-Thanh

We consider a sequential blocked matching (SBM) model where strategic agents repeatedly report ordinal preferences over a set of services to a central planner. The planner’s goal is to elicit agents’ true preferences and design a policy that matches services to agents in order to maximize the expected social welfare with the added constraint that each matched service can be blocked or unavailable for a number of time periods. Naturally, SBM models the repeated allocation of reusable services to a set of agents where each allocated service becomes unavailable for a fixed duration. We first consider the offline SBM setting, where the strategic agents are aware of their true preferences. We measure the performance of any policy by distortion, the worst-case multiplicative approximation guaranteed by any policy. For the setting with s services, we establish lower bounds of Ω(s) and Ω( √ s) on the distortions of any deterministic and randomised mechanisms, respectively. We complement these results by providing approximately truthful, measured by incentive ratio, deterministic and randomised policies based on random serial dictatorship which match our lower bounds. Our results show that there is a significant improvement if one considers the class of randomised policies. Finally, we consider the online SBM setting with bandit feedback where each agent is initially unaware of her true preferences, and the planner must facilitate each agent in the learning of their preferences through the matching of services over time. We design an approximately truthful mechanism based on the explore-then-commit paradigm, which achieves logarithmic dynamic approximate regret.

IJCAI Conference 2022 Conference Paper

Strategyproof Mechanisms for Group-Fair Facility Location Problems

• Houyu Zhou
• Minming Li
• Hau Chan

We study the facility location problems where agents are located on a real line and divided into groups based on criteria such as ethnicity or age. Our aim is to design mechanisms to locate a facility to approximately minimize the costs of groups of agents to the facility fairly while eliciting the agents' locations truthfully. We first explore various well-motivated group fairness cost objectives for the problems and show that many natural objectives have an unbounded approximation ratio. We then consider minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, we show that existing classical mechanisms (e. g. , median) and new group-based mechanisms provide bounded approximation ratios, where the group-based mechanisms can achieve better ratios. We also provide lower bounds for both objectives. To measure fairness between groups and within each group, we study a new notion of intergroup and intragroup fairness (IIF). We consider two IIF objectives and provide mechanisms with tight approximation ratios.

IJCAI Conference 2021 Conference Paper

Budget-feasible Mechanisms for Representing Groups of Agents Proportionally

• Xiang Liu
• Hau Chan
• Minming Li
• Weiwei Wu

In this paper, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the selected agents from each group is maximized. Depending on agents' membership in the groups, we consider two main models: single group setting where each agent belongs to only one group, and multiple group setting where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models, which can select representative agents from different groups. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on proportional representation.

AAAI Conference 2021 Conference Paper

Facility’s Perspective to Fair Facility Location Problems

• Chenhao Wang
• Xiaoying Wu
• Minming Li
• Hau Chan

We study the problem faced by a decision maker who wants to locate a set of facilities on a real line and allocate agents/items to the facilities. The items have given locations on the line, and can only be assigned to one of their closest facilities. The facilities are controlled by managers, who have additive utility over the items. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair. In this paper, we are interested in fair allocation among facility managers and consider the well-studied proportionality and envy-freeness fairness notions and their relaxations. We assess the availability, existence, approximability, and the quality (price of fairness) of fair solutions, where the quality measures the system efficiency loss under a fair allocation compared to the one that maximizes the social welfare. further, we show that one can find a Pareto-optimal solution in polynomial time.

IJCAI Conference 2021 Conference Paper

Game-theoretic Analysis of Effort Allocation of Contributors to Public Projects

• Jared Soundy
• Chenhao Wang
• Clay Stevens
• Hau Chan

Public projects can succeed or fail for many reasons such as the feasibility of the original goal and coordination among contributors. One major reason for failure is that insufficient work leaves the project partially completed. For certain types of projects anything short of full completion is a failure (e. g. , feature request on software projects in GitHub). Therefore, project success relies heavily on individuals allocating sufficient effort. When there are multiple public projects, each contributor needs to make decisions to best allocate his/her limited effort (e. g. , time) to projects while considering the effort allocation decisions of other strategic contributors and his/her parameterized utilities based on values and costs for the projects. In this paper, we introduce a game-theoretic effort allocation model of contributors to public projects for modeling effort allocation of strategic contributors. We study the related Nash equilibrium (NE) computational problems and provide NP-hardness results for the existence of NE and polynomial-time algorithms for finding NE in restricted settings. Finally, we investigate the inefficiency of NE measured by the price of anarchy and price of stability.

TCS Journal 2021 Journal Article

Influence maximization in the presence of vulnerable nodes: A ratio perspective

• Huiping Chen
• Grigorios Loukides
• Solon P. Pissis
• Hau Chan

Influence maximization is a key problem seeking to identify users who will diffuse information to influence the largest number of other users in a social network. A drawback of the influence maximization problem is that it could be socially irresponsible to influence users many of whom would be harmed, due to their demographics, health conditions, or socioeconomic characteristics (e. g. , predominantly overweight people influenced to buy junk food). Motivated by this drawback and by the fact that some of these vulnerable users will be influenced inadvertently, we introduce the problem of finding a set of users (seeds) that limits the influence to vulnerable users while maximizing the influence to the non-vulnerable users. We define a measure that captures the quality of a set of seeds as an additively smoothed ratio (ASR) between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop methods which aim to find a set of seeds that maximizes the measure: greedy heuristics, an approximation algorithm, as well as several variations of the approximation algorithm. We evaluate our methods on synthetic and real-world datasets and demonstrate they substantially outperform a state-of-the-art competitor in terms of both effectiveness and efficiency. We also demonstrate that the variations of our approximation algorithm offer different trade-offs between effectiveness and efficiency.

IJCAI Conference 2021 Conference Paper

Mechanism Design for Facility Location Problems: A Survey

• Hau Chan
• Aris Filos-Ratsikas
• Bo Li
• Minming Li
• Chenhao Wang

The study of approximate mechanism design for facility location has been in the center of research at the intersection of artificial intelligence and economics for the last decade, largely due to its practical importance in various domains, such as social planning and clustering. At a high level, the goal is to select a number of locations on which to build a set of facilities, aiming to optimize some social objective based on the preferences of strategic agents, who might have incentives to misreport their private information. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting all the different variants and methodologies, as well as the most interesting directions for future research.

AAMAS Conference 2021 Conference Paper

Multi-Robot Task Allocation-Complexity and Approximation

• Haris Aziz
• Hau Chan
• Ágnes Cseh
• Bo Li
• Fahimeh Ramezani
• Chenhao Wang

Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.

NeurIPS Conference 2020 Conference Paper

Adversarial Blocking Bandits

• Nicholas Bishop
• Hau Chan
• Debmalya Mandal
• Long Tran-Thanh

We consider a general adversarial multi-armed blocking bandit setting where each played arm can be blocked (unavailable) for some time periods and the reward per arm is given at each time period adversarially without obeying any distribution. The setting models scenarios of allocating scarce limited supplies (e. g. , arms) where the supplies replenish and can be reused only after certain time periods. We first show that, in the optimization setting, when the blocking durations and rewards are known in advance, finding an optimal policy (e. g. , determining which arm per round) that maximises the cumulative reward is strongly NP-hard, eliminating the possibility of a fully polynomial-time approximation scheme (FPTAS) for the problem unless P = NP. To complement our result, we show that a greedy algorithm that plays the best available arm at each round provides an approximation guarantee that depends on the blocking durations and the path variance of the rewards. In the bandit setting, when the blocking durations and rewards are not known, we design two algorithms, RGA and RGA-META, for the case of bounded duration an path variation. In particular, when the variation budget B T is known in advance, RGA can achieve O(\sqrt{T(2\tilde{D}+K)B {T}}) dynamic approximate regret. On the other hand, when B_T is not known, we show that the dynamic approximate regret of RGA-META is at most O((K+\tilde{D})^{1/4}\tilde{B}^{1/2}T^{3/4}) where \tilde{B} is the maximal path variation budget within each batch of RGA-META (which is provably in order of o(\sqrt{T}). We also prove that if either the variation budget or the maximal blocking duration is unbounded, the approximate regret will be at least Theta(T). We also show that the regret upper bound of RGA is tight if the blocking durations are bounded above by an order of O(1).

AAAI Conference 2020 Conference Paper

Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives

• Haris Aziz
• Hau Chan
• Barton Lee
• Bo Li
• Toby Walsh

We consider the facility location problem in the onedimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, we prove that the corresponding optimization problem, where the goal is to locate facilities to minimize either the total cost to all agents or the maximum cost of any agent is NP-hard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilities have identical capacities. We then consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that several natural mechanisms studied in the uncapacitated setting either lose strategyproofness or a bound on the solution quality for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.

IJCAI Conference 2020 Conference Paper

Fighting Wildfires under Uncertainty - A Sequential Resource Allocation Approach

• Hau Chan
• Long Tran-Thanh
• Vignesh Viswanathan

Standard disaster response involves using drones (or helicopters) for reconnaissance and using people on the ground to mitigate the damage. In this paper, we look at the problem of wildfires and propose an efficient resource allocation strategy to cope with both dynamically changing environment and uncertainty. In particular, we propose Firefly, a new resource allocation algorithm, that can provably achieve optimal or near optimal solutions with high probability by first efficiently allocating observation drones to collect information to reduce uncertainty, and then allocate the firefighting units to extinguish fire. For the former, Firefly uses a combination of maximum set coverage formulation and a novel utility estimation technique, and it uses a knapsack formulation to calculate the allocation for the latter. We also demonstrate empirically by using a real-world dataset that Firefly achieves up to 80-90% performance of the offline optimal solution, even with a small amount of drones, in most of the cases.

AAMAS Conference 2019 Conference Paper

Maximin-Aware Allocations of Indivisible Goods

• Hau Chan
• Jing Chen
• Bo Li
• Xiaowei Wu

We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the bundles (or allocated goods) of other agents. In particular, we propose maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not get the worst bundle, even if she does not know how the other goods are distributed. We also introduce two of its relaxations, MMA1 and MMAX. We show that MMA1 and MMAX potentially have stronger egalitarian guarantees than EF1 and are easier to achieve than MMS and EFX. Finally, we present a polynomial-time algorithm, which computes an allocation such that every agent is either 1 2 -approximate MMA or exactly MMAX. Interestingly, the returned allocation is also 1 2 -approximate EFX when all agents have subadditive valuations, which answers an open question left in [Plaut and Roughgarden, SODA 2018].

IJCAI Conference 2019 Conference Paper

Maximin-Aware Allocations of Indivisible Goods

• Hau Chan
• Jing Chen
• Bo Li
• Xiaowei Wu

We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not envy at least one other agent, even if she does not know how the other goods are distributed among other agents. We also introduce two of its relaxations, and discuss their egalitarian guarantee and existence. Finally, we present a polynomial-time algorithm, which computes an allocation that approximately satisfies MMA or its relaxations. Interestingly, the returned allocation is also 1/2-approximate EFX when all agents have sub- additive valuations, which improves the algorithm in [Plaut and Roughgarden, 2018].

AAMAS Conference 2019 Conference Paper

Maxmin Share Fair Allocation of Indivisible Chores to Asymmetric Agents

• Haris Aziz
• Hau Chan
• Bo Li

We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concepts we focus on are natural generalizations of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for allocation of goods to asymmetric agents, and even for chores to symmetric agents do not provide good approximations for allocation of chores to asymmetric agents under WMMS. As a consequence, we present a novel polynomial-time constantapproximation algorithm, via linear program, for OWMMS. For two special cases: binary valuation case and 2-agent case, we provide exact or better constant-approximation algorithms.

IJCAI Conference 2019 Conference Paper

Weighted Maxmin Fair Share Allocation of Indivisible Chores

• Haris Aziz
• Hau Chan
• Bo Li

We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for allocation of goods to asymmetric agents, and even for chores to symmetric agents do not provide good approximations for allocation of chores to asymmetric agents under WMMS. As a consequence, we present a novel polynomial-time constant-approximation algorithm, via linear program, for OWMMS. For two special cases: the binary valuation case and the 2-agent case, we provide exact or better constant-approximation algorithms.

IJCAI Conference 2019 Conference Paper

Who Should Pay the Cost: A Game-theoretic Model for Government Subsidized Investments to Improve National Cybersecurity

• Xinrun Wang
• Bo An
• Hau Chan

Due to the recent cyber attacks, cybersecurity is becoming more critical in modern society. A single attack (e. g. , WannaCry ransomware attack) can cause as much as $4 billion in damage. However, the cybersecurity investment by companies is far from satisfactory. Therefore, governments (e. g. , in the UK) launch grants and subsidies to help companies to boost their cybersecurity to create a safer national cyber environment. The allocation problem is hard due to limited subsidies and the interdependence between self-interested companies and the presence of a strategic cyber attacker. To tackle the government's allocation problem, we introduce a Stackelberg game-theoretic model where the government first commits to an allocation and the companies/users and attacker simultaneously determine their protection and attack (pure or mixed) strategies, respectively. For the pure-strategy case, while there may not be a feasible allocation in general, we prove that computing an optimal allocation is NP-hard and propose a linear reverse convex program when the attacker can attack all users. For the mixed-strategy case, we show that there is a polynomial time algorithm to find an optimal allocation when the attacker has a single-attack capability. We then provide a heuristic algorithm, based on best-response-gradient dynamics, to find an effective allocation in the general setting. Experimentally, we show that our heuristic is effective and outperforms other baselines on synthetic and real data.

IJCAI Conference 2018 Conference Paper

An FPTAS for Computing Nash Equilibrium in Resource Graph Games

• Hau Chan
• Albert Xin Jiang

We consider the problem of computing a mixed-strategy Nash equilibrium (MSNE) in resource graph games (RGGs), a compact representation for games with an exponential number of strategies. In an RGG, each player's pure strategy is a subset of resources, represented by a binary vector, and her pure strategy set is represented compactly using a set of linear inequality constraints. Given the pure strategies of the players, each player's utility depends on the resource graph and the numbers of times the neighboring resources are used. RGGs are general enough to capture a wide variety of games studied in literature, including congestion games and security games. In this paper, we provide the first Fully Polytnomial Time Approximation Scheme (FPTAS) for computing an MSNE in any symmetric multilinear RGG where its constraint moralized resource graph (a graph formed between the moralized resource graph and the constraints defining the strategy polytope) has bounded treewidth. Our FPTAS can be generalized to compute optimal MSNE, and to games with a constant number of player types. As a consequence, our FPTAS provides new approximation results for security games, network congestion games, and bilinear games.

AAMAS Conference 2018 Conference Paper

Learning Game-theoretic Models from Aggregate Behavioral Data with Applications to Vaccination Rates in Public Health

• Hau Chan
• Luis E. Ortiz

In this paper, we undertake the challenging task of uncovering independencies of public-health behavioral data on populations’ vaccination rates collected by government officials in the United States. We use computational game theory to model such data as the result of distributed decision-making at the reported granularity level (e. g. , nations and states). To achieve our task, we posit the view of aggregated behavioral data as jointly randomized, or mixed, strategies of multiple agents. We propose a novel general machine-learning approach to learn game-theoretic models within a given hypothesis class of games from any potentially noisy dataset of mixed strategies. We illustrate our framework using publicly available data on vaccination rates in the continental USA.

IJCAI Conference 2017 Conference Paper

Maximizing Awareness about HIV in Social Networks of Homeless Youth with Limited Information

• Amulya Yadav
• Hau Chan
• Albert Xin Jiang
• Haifeng Xu
• Eric Rice
• Milind Tambe

This paper presents HEALER, a software agent that recommends sequential intervention plans for use by homeless shelters, who organize these interventions to raise awareness about HIV among homeless youth. HEALER's sequential plans (built using knowledge of social networks of homeless youth) choose intervention participants strategically to maximize influence spread, while reasoning about uncertainties in the network. While previous work presents influence maximizing techniques to choose intervention participants, they do not address two real-world issues: (i) they completely fail to scale up to real-world sizes; and (ii) they do not handle deviations in execution of intervention plans. HEALER handles these issues via two major contributions: (i) HEALER casts this influence maximization problem as a POMDP and solves it using a novel planner which scales up to previously unsolvable real-world sizes; and (ii) HEALER allows shelter officials to modify its recommendations, and updates its future plans in a deviation-tolerant manner. HEALER was deployed in the real world in Spring 2016 with considerable success.

AAAI Conference 2017 Conference Paper

Resource Graph Games: A Compact Representation for Games with Structured Strategy Spaces

• Albert Jiang
• Hau Chan
• Kevin Leyton-Brown

In many real-world systems, strategic agents’ decisions can be understood as complex—i. e. , consisting of multiple subdecisions—and hence can give rise to an exponential number of pure strategies. Examples include network congestion games, simultaneous auctions, and security games. However, agents’ sets of strategies are often structured, allowing them to be represented compactly. There currently exists no general modeling language that captures a wide range of commonly seen strategy structure and utility structure. We propose Resource Graph Games (RGGs), the first general compact representation for games with structured strategy spaces, which is able to represent a wide range of games studied in literature. We leverage recent results about multilinearity, a key property of games that allows us to represent the mixed strategies compactly, and, as a result, to compute various equilibrium concepts efficiently. While not all RGGs are multilinear, we provide a general method of converting RGGs to those that are multilinear, and identify subclasses of RGGs whose converted version allow efficient computation.

AAMAS Conference 2016 Conference Paper

Budget Feasible Mechanisms for Dealers

• Hau Chan
• Jing Chen

We consider the problem of designing budget feasible mechanisms for a dealer, who aims to maximize revenue by buying items from a seller market and selling them to a buyer market that consists of unit-demand buyers. Different from the related literature, the dealer’s “value” for a set of items that he purchased from the seller market is not directly given as a number but it is defined to be the maximum revenue the dealer can obtain from selling the items to the buyers. We aim to design mechanisms that are dominant-strategy truthful for the sellers to report their costs and envy-free for the buyers to purchase their most preferred items (given their prices) in the final outcome, such that the total payment to the sellers does not exceed the dealer’s budget and the dealer’s revenue is (approximately) maximized. First, to understand the structure of the optimal mechanisms, we show that the maximum (envy-free) revenue obtainable by the dealer as a function of the set of purchased items is monotone and subadditive. Thus, existing results on subadditive optimization problems are potentially applicable in solving the mechanism design problem for the dealer. However, a crucial assumption adopted by all previous studies on subadditive functions is that the mechanism or algorithm has access to the value oracle and/or the demand oracle. In the dealer’s problem, instead, we show that (1) the demand oracle can be efficiently simulated by the value oracle and (2) both have efficient O(log n)-approximation algorithms, where n is the number of buyers. This is particularly interesting given the literature, since, in general, the demand oracle can always efficiently simulate the value oracle, and there are cases where the demand oracle is strictly more powerful. Our results show that, for the dealer’s problem, the two oracles are as powerful as each other. Finally, we construct a polynomial-time budget feasible mechanism for the dealer that doesn’t use any oracle and provides an O((log2 n)(log2 m))-approximation of the optimal revenue, where m is the number of sellers.

IJCAI Conference 2016 Conference Paper

Congestion Games with Polytopal Strategy Spaces

• Hau Chan
• Albert Xin Jiang

Congestion games are a well-studied class of games that has been used to model real-world systems such as Internet routing. In many congestion games, each player's number of strategies can be exponential in the natural description of the game. Most existing algorithms for game theoretic computation, from computing expected utilities and best responses to finding Nash equilibrium and other solution concepts, all involve enumeration of pure strategies. As a result, such algorithms would take exponential time on these congestion games. In this work, we study congestion games in which each player's strategy space can be described compactly using a set of linear constraints. For instance, network congestion games naturally fall into this subclass as each player's strategy can be described by a set of flow constraints. We show that we can represent any mixed strategy compactly using marginals which specify the probability of using each resource. As a consequence, the expected utilities and the best responses can be computed in polynomial time. We reduce the problem of computing a best/worst symmetric approximate mixed-strategy Nash equilibrium in symmetric congestion games to a constraint optimization problem on a graph formed by the resources and the strategy constraints. As a result, we present a fully polynomial time approximation scheme (FPTAS) for this problem when the graph has bounded tree width.

AAMAS Conference 2016 Conference Paper

Provision-After-Wait with Common Preferences

• Hau Chan
• Jing Chen

We study the Provision-after-Wait problem in healthcare introduced by Braverman, Chen, and Kannan (2016). In this setting, patients seek a medical procedure, and the procedure can be performed by different hospitals of different costs. Each patient has a value for each hospital, and a budget-constrained government/planner pays for the medical expenses of the patients. The planner’s goal is to find an optimal stable assignment that is envy-free and maximizes the social welfare while keeping the expenses within the budget. In this work, we focus on the settings where the patients have a common preference of the hospitals. We show that computing the optimal stable assignment for maximizing social welfare is NP-hard. Furthermore, we construct a fully polynomial-time approximation scheme (FPTAS) that runs in time O((n + m)n3 m/ ), where m and n are the number of hospitals and patients, respectively. In order to develop the FPTAS, we have defined and studied a new problem, ordered Knapsack. We also consider the setting where the planner uses lottery as a rationing tool. For a large sub-class of our settings, we show the conditions under which the optimal lottery scheme has a simple structure and generates more social welfare than the optimal stable assignment. Moreover, such optimal lottery scheme can be computed by a linear program.

AAMAS Conference 2016 Conference Paper

Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty

• Amulya Yadav
• Hau Chan
• Albert Xin Jiang
• Haifeng Xu
• Eric Rice
• Milind Tambe

AAAI Conference 2015 Conference Paper

Computing Nash Equilibrium in Interdependent Defense Games

• Hau Chan
• Luis Ortiz

Roughly speaking, Interdependent Defense (IDD) games, previously proposed, model the situation where an attacker wants to cause as much damage as possible to a network by attacking one of the sites in the network. Each site must make an investment decision regarding security to protect itself against a direct or indirect attack, the latter due to potential transfer-risk from an unprotected neighboring site. The work introducing IDD games discusses potential applications to model the essence of real-world scenarios such as the 2006 transatlantic aircraft plot. In this paper, our focus is the study of the problem of computing a Nash Equilibrium (NE) in IDD games. We show that an efficient algorithm to determine whether some attacker’s strategy can be a part of a NE in an instance of IDD games is unlikely to exist. Yet, we provide a dynamic programming algorithm to compute an approximate NE when the graph/network structure of the game is a directed tree with a single source, and show that it is an FPTAS. We also introduce an improved heuristic to compute an approximate NE on arbitrary graph structures. Our experiments show that our heuristic is more efficient, and provides better approximations, than best-response-gradient dynamics for the case of Internet games, a class of games introduced and studied in the original work on IDD games.

NeurIPS Conference 2014 Conference Paper

Computing Nash Equilibria in Generalized Interdependent Security Games

• Hau Chan
• Luis Ortiz

We study the computational complexity of computing Nash equilibria in generalized interdependent-security (IDS) games. Like traditional IDS games, originally introduced by economists and risk-assessment experts Heal and Kunreuther about a decade ago, generalized IDS games model agents’ voluntary investment decisions when facing potential direct risk and transfer risk exposure from other agents. A distinct feature of generalized IDS games, however, is that full investment can reduce transfer risk. As a result, depending on the transfer-risk reduction level, generalized IDS games may exhibit strategic complementarity (SC) or strategic substitutability (SS). We consider three variants of generalized IDS games in which players exhibit only SC, only SS, and both SC+SS. We show that determining whether there is a pure-strategy Nash equilibrium (PSNE) in SC+SS-type games is NP-complete, while computing a single PSNE in SC-type games takes worst-case polynomial time. As for the problem of computing all mixed-strategy Nash equilibria (MSNE) efficiently, we produce a partial characterization. Whenever each agent in the game is indiscriminate in terms of the transfer-risk exposure to the other agents, a case that Kearns and Ortiz originally studied in the context of traditional IDS games in their NIPS 2003 paper, we can compute all MSNE that satisfy some ordering constraints in polynomial time in all three game variants. Yet, there is a computational barrier in the general (transfer) case: we show that the computational problem is as hard as the Pure-Nash-Extension problem, also originally introduced by Kearns and Ortiz, and that it is NP complete for all three variants. Finally, we experimentally examine and discuss the practical impact that the additional protection from transfer risk allowed in generalized IDS games has on MSNE by solving several randomly-generated instances of SC+SS-type games with graph structures taken from several real-world datasets.

IJCAI Conference 2013 Conference Paper

Multiwinner Elections under Preferences that Are Single-Peaked on a Tree

• Lan Yu
• Hau Chan
• Edith Elkind

We study the complexity of electing a committee under several variants of the Chamberlin–Courant rule when the voters’ preferences are single-peaked on a tree. We first show that this problem is easy for the egalitarian, or “minimax” version of this problem, for arbitrary trees and misrepresentation functions. For the standard (utilitarian) version of this problem we provide an algorithm for an arbitrary misrepresentation function whose running time is polynomial in the input size as long as the number of leaves of the underlying tree is bounded by a constant. On the other hand, we prove that our problem remains computationally hard on trees that have bounded degree, diameter, or pathwidth. Finally, we show how to modify Trick’s [1989] algorithm to check whether an election is single-peaked on a tree whose number of leaves does not exceed a given parameter λ.

UAI Conference 2012 Conference Paper

Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks

• Hau Chan
• Michael Ceyko
• Luis E. Ortiz

We propose interdependent defense (IDD) games, a computational game-theoretic framework to study aspects of the interdependence of risk and security in multi-agent systems under deliberate external attacks. Our model builds upon interdependent security (IDS) games, a model due to Heal and Kunreuther that considers the source of the risk to be the result of a fixed randomizedstrategy. We adapt IDS games to model the attacker’s deliberate behavior. We define the attacker’s pure-strategy space and utility function and derive appropriate cost functions for the defenders. We provide a complete characterization of mixed-strategy Nash equilibria (MSNE), and design a simple polynomial-time algorithm for computing all of them, for an important subclass of IDD games. In addition, we propose a randominstance generator of (general) IDD games based on a version of the real-world Internetderived Autonomous Systems (AS) graph (with around 27K nodes and 100K edges), and present promising empirical results using a simple learning heuristics to compute (approximate) MSNE in such games.