Arrow Research search

Author name cluster

Xiaowei Wu

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

25 papers
1 author row

Possible papers

25

AAAI Conference 2026 Conference Paper

MSCFL: Model Structure-Aware Clustered Federated Learning for System Heterogeneity and Data Drift

  • Yang Xu
  • Xiaowei Wu
  • Zifeng Xu
  • Cheng Zhang
  • Ju Ren
  • Yaoxue Zhang

Federated Learning (FL) faces significant challenges arising from both data and system heterogeneity. While Clustered Federated Learning (CFL) mitigates data heterogeneity by grouping clients with similar data distributions, it remains vulnerable to system heterogeneity, which can slow convergence due to performance disparities among clients. Moreover, data drift may degrade clustering accuracy and training efficiency over time. In this work, we propose a Model Structure-aware Clustered Federated Learning (MSCFL) framework that simultaneously addresses the issues of data heterogeneity, system heterogeneity, and data drift. MSCFL incorporates model pruning (MP) into the CFL framework to enhance training efficiency under system heterogeneity. To enable this integration, we address the key challenge of performing effective clustering based on heterogeneous, pruned local models with varying structures. To this end, we design a model structure-based similarity computation algorithm to integrate CFL with MP. To effectively address data drift, we propose a dynamic cluster migration strategy that efficiently monitors model structures via Hamming Distance and triggers re-clustering only when necessary. Extensive experimental results show that MSCFL improves the accuracy and convergence speed of cluster models, outperforming traditional CFL in various settings.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

A Little Subsidy Ensures MMS Allocation for Three Agents

  • Xiaowei Wu
  • Quan Xue
  • Shengwei Zhou

We consider the problem of fair allocation of m indivisible items to a group of n agents with subsidies (money). We address scenarios where agents have general additive cost/utility functions. Our work primarily focuses on the special case of three agents. Assuming that the maximum cost/utility of an item to an agent can be compensated by one dollar, we demonstrate that a total subsidy of 1/6 dollars is sufficient to ensure the existence of Maximin Share (MMS) allocations for both goods and chores. Additionally, we provide examples to establish the lower bounds of the required subsidies.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Approximately EFX and fPO Allocations for Bivalued Chores

  • Zehan Lin
  • Xiaowei Wu
  • Shengwei Zhou

We consider the computation for allocations of indivisible chores that are approximately EFX and fractional Pareto optimal (fPO). It has been shown that 3-EFX and fPO allocations for bi-valued instances always exist, where the cost of an item to an agent is either 1 or k (where k > 1), by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to (2-1/k), while preserving the fractional Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores and reallocates items until approximate EFX is achieved. We further improve our result for the case when k=2 and devise an algorithm that computes EFX and fPO allocations.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

  • Xiaowei Wu
  • Quan Xue
  • Shengwei Zhou

In this paper, we revisit the problem of fair allocation with subsidy. We first consider the allocation of m indivisible chores to n agents with additive (dis)utility functions. Under the assumption that the maximum (dis)utility of an item can be compensated by one dollar, Wu et al. (WINE 2023) showed that a total of n/4 dollars suffices to guarantee a proportional allocation by rounding fractional allocations. Their subsidy guarantee is optimal when n is even. For odd n, there is still a small gap between the upper and lower bounds for the total subsidy. In this paper, we propose a much simpler algorithm for the problem, which does not require rounding fractional allocations, and achieves an optimal subsidy guarantee for all values of n. Different from existing works, our algorithm does not require the computation and rounding of fractional allocations and admits a much simpler analysis. We further show that our algorithm and analysis framework can be extended to the mixture of (subjective) goods and chores, achieving the optimal subsidy guarantee.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Approximation Algorithm for Computing Budget-Feasible EF1 Allocations

  • Jiarui Gan
  • Bo Li
  • Xiaowei Wu

We study algorithmic fairness in a budget-feasible resource allocation problem. In this problem, a set of items with varied sizes and values are to be allocated to a group of agents, while each agent has a budget constraint on the total size of items she can receive. An envy-free (EF) allocation is defined in this context as one in which no agent envies another for the items they get and, in addition, no agent envies the charity, who is automatically endowed with all the unallocated items. Since EF allocations barely exist even without budget constraints, we are interested in the relaxed notion of envy-freeness up to one item (EF1). In this paper, we further the recent progress towards understanding the existence and approximations of EF1 (or EF2) allocations. We propose a polynomial-time algorithm that computes a 1/2-approximate EF1 allocation for an arbitrary number of agents with heterogeneous budgets. For the uniform-budget and two-agent cases, we present a polynomial-time algorithm that computes an exact EF1 allocation. We also consider the large budget setting, where the item sizes are infinitesimal relative to the agents’ budgets. We show that both the allocations that maximize the Nash social welfare and the allocations that our main algorithm computes are EF1 in the limit.

PDF

AAAI Conference 2023 Conference Paper

Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule

  • Bo Li
  • Xiaowei Wu
  • Chenyang Xu
  • Ruilong Zhang

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our problem to submodular objective functions and Matroid rank constraints.

PDF Details DOI

JAIR Journal 2023 Journal Article

Stackelberg Security Games with Contagious Attacks on a Network: Reallocation to the Rescue

  • Rufan Bai
  • Haoxing Lin
  • Xinyu Yang
  • Xiaowei Wu
  • Minming Li
  • Weijia Jia

In the classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective of maximizing the damage caused. In this paper, we consider the network defending problem against contagious attacks, e.g., the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in the real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. Therefore, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that the problem of computing optimal defending strategy is NP-hard even for some very special cases. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Approximately EFX Allocations for Indivisible Chores

  • Shengwei Zhou
  • Xiaowei Wu

In this paper we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocation is not guaranteed to exist, we consider the notion of envy-freeness up to any item (EFX). In contrast to the fruitful results regarding the (approximation of) EFX allocations for goods, very little is known for the allocation of chores. Prior to our work, for the allocation of chores, it is known that EFX allocations always exist for two agents, or general number of agents with identical ordering cost functions. For general instances, no non-trivial approximation result regarding EFX allocation is known. In this paper we make some progress in this direction by showing that for three agents we can always compute a 5-approximation of EFX allocation in polynomial time. For n>=4 agents, our algorithm always computes an allocation that achieves an approximation ratio of 3n^2 regarding EFX. We also study the bi-valued instances, in which agents have at most two cost values on the chores, and provide polynomial time algorithms for the computation of EFX allocation when n=3, and (n-1)-approximation of EFX allocation when n>=4.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Mixed Strategies for Security Games with General Defending Requirements

  • Rufan Bai
  • Haoxing Lin
  • Xinyu Yang
  • Xiaowei Wu
  • Minming Li
  • Weijia Jia

The Stackelberg security game is played between a defender and an attacker, where the defender needs to allocate a limited amount of resources to multiple targets in order to minimize the loss due to adversarial attack by the attacker. While allowing targets to have different values, classic settings often assume uniform requirements to defend the targets. This enables existing results that study mixed strategies (randomized allocation algorithms) to adopt a compact representation of the mixed strategies. In this work, we initiate the study of mixed strategies for the security games in which the targets can have different defending requirements. In contrast to the case of uniform defending requirement, for which an optimal mixed strategy can be computed efficiently, we show that computing the optimal mixed strategy is NP-hard for the general defending requirements setting. However, we show that strong upper and lower bounds for the optimal mixed strategy defending result can be derived. We propose an efficient close-to-optimal Patching algorithm that computes mixed strategies that use only few pure strategies. We also study the setting when the game is played on a network and resource sharing is enabled between neighboring targets. Our experimental results demonstrate the effectiveness of our algorithm in several large real-world datasets.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Budget-feasible Maximum Nash Social Welfare is Almost Envy-free

  • Xiaowei Wu
  • Bo Li
  • Jiarui Gan

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Defending against Contagious Attacks on a Network with Resource Reallocation

  • Rufan Bai
  • Haoxing Lin
  • Xinyu Yang
  • Xiaowei Wu
  • Minming Li
  • Weijia Jia

In classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective to maximize the damage caused. Existing models assume that the attack at node u causes damage only at u. However, in many real-world security scenarios, the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes, e. g. , for the outbreak of a virus. In this paper, we consider the network defending problem against contagious attacks. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. To this end, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that this more general model is difficult in two aspects: (1) even for a fixed allocation of resources, we show that computing the optimal reallocation is NP-hard; (2) for the case when reallocation is not allowed, we show that computing the optimal allocation (against contagious attack) is also NP-hard. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks. *Funded by the Science and Technology Development Fund, Macau SAR (File no. SKLIOTSC-2018-2020), the Start-up Research Grant of University of Macau (File no. SRG2020-00020- IOTSC). This work was supported in part by the Science and Technology Development Fund, Macau SAR under File no. 0060/2019/A1, and in part by Research Grant of University of Macau under Grant MYRG2018-00237-FST. † City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. The work described in this paper was partially sponsored by Project 11771365 supported by NSFC. ‡ BNU-UIC Institute of Artificial Intelligence and Future Networks, Beijing Normal University (Zhuhai), Guangdong, China. The work was partially supported by Chinese National Research Fund (NSFC) Key Project No. 61532013; NSFC grant No. 61872239; and Guangdong Provincial Key Lab of AI and Multimodal Data Processing at BNU-HKBU UIC. Copyright © 2021, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved.

PDF Details

AAAI Conference 2020 Conference Paper

Defending with Shared Resources on a Network

  • Minming Li
  • Long Tran-Thanh
  • Xiaowei Wu

In this paper we consider a defending problem on a network. In the model, the defender holds a total defending resource of R, which can be distributed to the nodes of the network. The defending resource allocated to a node can be shared by its neighbors. There is a weight associated with every edge that represents the efficiency defending resources are shared between neighboring nodes. We consider the setting when each attack can affect not only the target node, but its neighbors as well. Assuming that nodes in the network have different treasures to defend and different defending requirements, the defender aims at allocating the defending resource to the nodes to minimize the loss due to attack. We give polynomial time exact algorithms for two important special cases of the network defending problem. For the case when an attack can only affect the target node, we present an LP-based exact algorithm. For the case when defending resources cannot be shared, we present a max-flow-based exact algorithm. We show that the general problem is NP-hard, and we give a 2approximation algorithm based on LP-rounding. Moreover, by giving a matching lower bound of 2 on the integrality gap on the LP relaxation, we show that our rounding is tight.

PDF Details

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

PDF

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

PDF Details

IJCAI Conference 2019 Conference Paper

Strategyproof and Approximately Maxmin Fair Share Allocation of Chores

  • Haris Aziz
  • Bo Li
  • Xiaowei Wu

We initiate the work on fair and strategyproof allocation of indivisible chores. The fairness concept we consider in this paper is maxmin share (MMS) fairness. We consider three previously studied models of information elicited from the agents: the ordinal model, the cardinal model, and the public ranking model in which the ordinal preferences are publicly known. We present both positive and negative results on the level of MMS approximation that can be guaranteed if we require the algorithm to be strategyproof. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.

PDF Details

AAMAS Conference 2019 Conference Paper

Well-behaved Online Load Balancing Against Strategic Jobs

  • Bo Li
  • Minming Li
  • Xiaowei Wu

In the online load balancing problem on related machines, we have a set of jobs (with different sizes) arriving online, and we need to assign each job to a machine immediately upon its arrival, so as to minimize the makespan, i. e. , the maximum completion time. In classic mechanism design problems, we assume that the jobs are controlled by selfish agents, with the sizes being their private information. Each job (agent) aims at minimizing its own cost, which is its completion time plus the payment charged by the mechanism. Truthful mechanisms guaranteeing that every job minimizes its cost by reporting its true size have been well-studied [Aspnes et al. JACM 1997, Feldman et al. EC 2017]. In this paper, we study truthful online load balancing mechanisms that are well-behaved [Epstein et al. , MOR 2016]. Wellbehavior is important as it guarantees fairness between machines, and implies truthfulness in some cases when machines are controlled by selfish agents. Unfortunately, existing truthful online load balancing mechanisms are not well-behaved. We first show that to guarantee producing a well-behaved schedule, any online algorithm (even non-truthful) has a competitive ratio at least Ω( √ m), wherem is the number of machines. Then we propose a mechanism that guarantees truthfulness of the online jobs, and produces a schedule that is almost well-behaved. We show that our algorithm has a competitive ratio of O(logm). Moreover, for the case when the sizes of online jobs are bounded, the competitive ratio of our algorithm improves to O(1). Interestingly, we show several cases for which our mechanism is actually truthful against selfish machines.

PDF

IJCAI Conference 2016 Conference Paper

A Framework for Recommending Relevant and Diverse Items

  • Chaofeng Sha
  • Xiaowei Wu
  • Junyu Niu

The traditional recommendation systems usually aim to improve the recommendation accuracy while overlooking the diversity within the recommended lists. Although some diversification techniques have been designed to recommend top-k items in terms of both relevance and diversity, the coverage of the user's interest is overlooked. In this paper, we propose a general framework to recommend relevant and diverse items which explicitly takes the coverage of user interest into account. Based on the theoretical analysis, we design efficient greedy algorithms to get the near optimal solutions for those NP-hard problems. Experimental results on MovieLens dataset demonstrate that our approach outperforms state-of-the-art techniques in terms of both precision and diversity.

PDF Details