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.

27 papers

1 author row

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

AAMAS Conference 2026 Conference Paper

Proportional and Pareto-Optimal Allocation of Chores with Subsidy

Jugal Garg
Eklavya Sharma
Xiaowei Wu

We consider the problem of allocating𝑚 indivisible chores among𝑛 agents with possibly different weights, aiming for a solution that is both fair and efficient. Specifically, we focus on the classic fairness notion of proportionality and efficiency notion of Pareto-optimality. Since proportional allocations may not always exist in this setting, we allow the use of subsidies (monetary compensation to agents) to ensure agents are proportionally-satisfied, and aim to minimize the total subsidy required. Wu and Zhou [49] showed that when each chore has disutility at most 1, a total subsidy of at most𝑛/3−1/6 is sufficient to guarantee proportionality. However, their approach is based on a complex technique, which does not guarantee economic efficiency—a key desideratum in fair division. In this work, we give a polynomial-time algorithm that achieves the same subsidy bound while also ensuring Pareto-optimality. Moreover, both our algorithm and its analysis are significantly simpler than those of Wu and Zhou [49]. Our approach first computes a proportionally-fair competitive equilibrium, and then applies a rounding procedure guided by minimum-pain-per-buck edges.

PDF

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

I&C Journal 2025 Journal Article

Approximate envy-freeness in indivisible resource allocation with budget constraints

Xiaowei Wu
Bo Li
Jiarui Gan

We study the fair allocation of indivisible resources under knapsack constraints, where a set of items with varied costs and values are to be allocated among a group of agents. Each agent has a budget constraint on the total cost of items she can receive. The goal is to compute a budget-feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, which is endowed with all the unallocated items. Since EF allocations barely exist (even without the budget constraints), we are interested in the relaxed notion of envy-freeness up to one item (EF1). Our results are twofold. Firstly, for the general setting where agents have heterogeneous valuations and budgets, we show that a budget-feasible allocation that maximizes the Nash social welfare (NSW) achieves a 1/4-approximation of EF1. This approximation ratio carries to the general case of arbitrary monotone subadditive valuations. The approximation ratio improves gracefully when the items have small cost compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity, and to 1 if the agents further have identical valuations. Secondly, when agents have identical valuations, we design a polynomial-time algorithm that computes a 1/2-approximate EF1 allocation for an arbitrary number of agents. For the case of identical agents and the case of two agents, we propose polynomial-time algorithms for computing EF1 allocations.

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

AIJ Journal 2025 Journal Article

IID prophet inequality with a single data point

Yilong Feng
Bo Li
Haolong Li
Xiaowei Wu
Yutong Wu

In this work, we study the single-choice prophet inequality problem, where a seller encounters a sequence of n online bids. These bids are modeled as independent and identically distributed (i. i. d.) random variables drawn from an unknown distribution. Upon the revelation of each bid's value, the seller must make an immediate and irrevocable decision on whether to accept the bid and sell the item to the bidder. The objective is to maximize the competitive ratio between the expected gain of the seller and that of the maximum bid. It is shown by Correa et al. [1] that when the distribution is unknown or only o ( n ) uniform samples from the distribution are given, the best an algorithm can do is 1 / e -competitive. In contrast, when the distribution is known [2], or when Ω ( n ) uniform samples are given [3], the optimal competitive ratio of 0. 7451 can be achieved. In this paper, we study the setting when the seller has access to a single point in the cumulative density function of the distribution, which can be learned from historical sales data. We investigate how effectively this data point can be used to design competitive algorithms. Motivated by the algorithm for the secretary problem, we propose the observe-and-accept algorithm that sets a threshold in the first phase using the data point and adopts the highest bid from the first phase as the threshold for the second phase. It can be viewed as a natural combination of the single-threshold algorithm for prophet inequality and the secretary problem algorithm. We show that our algorithm achieves a good competitive ratio for a wide range of data points, reaching up to 0. 6785-competitive as n → ∞ for certain data points. Additionally, we study an extension of the algorithm that utilizes more than two phases and show that the competitive ratio can be further improved to at least 0. 6862.

Details DOI

AIJ Journal 2025 Journal Article

On the computation of mixed strategies for security games with general defending requirements

Rufan Bai
Haoxing Lin
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 attacks by the attacker. While allowing targets to have different values, classic settings often assume uniform requirements for defending 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 security games in which the targets can have different defending requirements. In contrast to the case of uniform defending requirements, 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 strong upper and lower bounds for the optimal mixed strategy defending result. Additionally, we extend our analysis to study uniform attack settings on these security games. We propose an efficient close-to-optimal Patching algorithm that computes mixed strategies using only a few pure strategies. Furthermore, we study the setting when the game is played on a network and resource sharing is enabled between neighboring targets. We show the effectiveness of our algorithm in various large real-world datasets, addressing both uniform and general defending requirements.

Details DOI

TCS Journal 2025 Journal Article

On the existence of EFX (and Pareto-optimal) allocations for binary chores

Biaoshuai Tao
Xiaowei Wu
Ziqi Yu
Shengwei Zhou

We study the problem of allocating a set of indivisible chores among agents while each chore has a binary marginal. We focus on the fairness criteria of envy-freeness up to any item (EFX) and investigate the existence of EFX allocations. We show that when agents have additive binary cost functions, EFX and Pareto-optimal (PO) allocations can be computed in polynomial time. We further consider more general cost functions: cancelable, submodular, and general (with binary marginal). For binary cancelable chores, we show that EFX allocations can be computed in polynomial time, but EFX is incompatible with PO. For submodular and general functions (with binary marginals), we propose algorithms for the computation of approximate EFX and envy-free (EF) (partial) allocations with at most n − 1 unallocated items respectively.

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

AIJ Journal 2025 Journal Article

Weighted EF1 allocations for indivisible chores

Xiaowei Wu
Cong Zhang
Shengwei Zhou

We study how to fairly allocate a set of indivisible chores to a group of agents, where each agent i has a non-negative weight w i that represents her obligation for undertaking the chores. We consider the fairness notion of weighted envy-freeness up to one item (WEF1) and propose an efficient picking sequence algorithm for computing WEF1 allocations. Our analysis is based on a natural and powerful continuous interpretation for the picking sequence algorithms in the weighted setting, which might be of independent interest. Using this interpretation, we establish the necessary and sufficient conditions under which picking sequence algorithms can guarantee other fairness notions in the weighted setting. We also study the best-of-both-worlds setting and propose a lottery that guarantees ex-ante WEF and ex-post WEF( 1, 1 ). Then we study the existence of fair and efficient allocations and propose efficient algorithms for computing WEF1 and PO allocations for bi-valued instances. Our result generalizes that of Garg et al. (AAAI 2022) and Ebadian et al. (AAMAS 2022) to the weighted setting. Our work also studies the price of fairness for WEF1, and the implications of WEF1 to other fairness notions.

Details DOI

AIJ Journal 2024 Journal Article

Almost proportional allocations of indivisible chores: Computation, approximation and efficiency

Haris Aziz
Bo Li
Hervé Moulin
Xiaowei Wu
Xinran Zhu

Proportionality (PROP) is one of the simplest and most intuitive fairness criteria used for allocating items among agents with additive utilities. However, when the items are indivisible, ensuring PROP becomes unattainable, leading to increased focus on its relaxations. In this paper, we focus on the relaxation of proportionality up to any item (PROPX), where proportionality is satisfied if an arbitrary item is removed from every agent's allocation. We show that PROPX is an appealing fairness notion for the allocation of indivisible chores, which approximately implies some share-based notions, such as maximin share (MMS) and AnyPrice share (APS). We further provide a comprehensive understanding of PROPX allocations, regarding the computation, approximation, and compatibility with efficiency. On top of these, we extend the study to scenarios where agents do not share equal liability towards the chores, and approximate PROPX allocations using partial information about agents' utilities.

Details DOI

AIJ Journal 2024 Journal Article

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) allocations are 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 progress in this direction by providing several polynomial time algorithms for the computation of EFX and approximately EFX allocations. We show that for three agents we can always compute a ( 2 + 6 ) -approximation of EFX allocation. For n ≥ 4 agents, our algorithm always computes a ( 3 n 2 − n ) -approximation. We also study the bi-valued instances, in which agents have at most two cost values on the chores. For three agents, we provide an algorithm for the computation of EFX allocations. For n ≥ 4 agents, we present algorithms for the computation of partial EFX allocations with at most ( n − 1 ) unallocated items; and ( n − 1 ) -approximation of EFX allocations.

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

AIJ Journal 2023 Journal Article

Fair division of indivisible goods: Recent progress and open questions

Georgios Amanatidis
Haris Aziz
Georgios Birmpas
Aris Filos-Ratsikas
Bo Li
Hervé Moulin
Alexandros A. Voudouris
Xiaowei Wu

Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.

Details DOI

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 efﬁciency 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-ﬂow-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

TCS Journal 2019 Journal Article

Diffusion operator and spectral analysis for directed hypergraph Laplacian

T.-H. Hubert Chan
Zhihao Gavin Tang
Xiaowei Wu
Chenzi Zhang

In spectral graph theory, the Cheeger inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operator. Recently this inequality has been extended to undirected hypergraphs and directed normal graphs via a non-linear operator associated with a diffusion process in the underlying graph. In this work, we develop a unifying framework for defining a diffusion operator on a directed hypergraph with stationary vertices, which is general enough for the following two applications. 1. Cheeger's inequality for directed hyperedge expansion. 2. Quadratic optimization with stationary vertices in the context of semi-supervised learning. Despite the crucial role of the diffusion process in spectral analysis, previous works have not formally established the existence of the corresponding diffusion processes. In this work, we give a proof framework that can indeed show that such diffusion processes are well-defined. In the first application, we use the spectral properties of the diffusion operator to achieve the Cheeger's inequality for directed hyperedge expansion. In the second application, the diffusion operator can be interpreted as giving a continuous analog to the subgradient method, which moves the feasible solution in discrete steps towards an optimal solution.

Details DOI

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