Search

We consider the problem of allocating $m$ indivisible items to a set of $n$ heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that when agents are unweighted a total subsidy of $n/4$ suffices (assuming that each item has value/cost at most $1$ to every agent) to ensure proportionality. When agents have general weights, they proposed an algorithm that guarantees a weighted proportional allocation requiring a total subsidy of $(n-1)/2$, by rounding the fractional bid-and-take algorithm. In this work, we revisit the problem and the fractional bid-and-take algorithm. We show that by formulating the fractional allocation returned by the algorithm as a directed tree connecting the agents and splitting the tree into canonical components, there is a rounding scheme that requires a total subsidy of at most $n/3 - 1/6$., Comment: 30 pages, 11 figures

We study the problem of allocating a group 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, there exist EFX and Pareto-optimal (PO) allocations that can be computed in polynomial time. To the best of our knowledge, this is the first setting of a general number of agents that admits EFX and PO allocations, before which EFX and PO allocations have only been shown to exist for three bivalued agents. We further consider more general cost functions: cancelable and general monotone (both with binary marginal). We show that EFX allocations exist and can be computed for binary cancelable chores, but EFX is incompatible with PO. For general binary marginal functions, we propose an algorithm that computes (partial) envy-free (EF) allocations with at most $n-1$ unallocated items., Comment: 11 pages, 1 figure

We consider the problem of fair allocation of $m$ indivisible items to a group of $n$ agents with subsidy (money). Our work mainly focuses on the allocation of chores but most of our results extend to the allocation of goods as well. We consider the case when agents have (general) additive cost functions. Assuming that the maximum cost of an item to an agent can be compensated by one dollar, we show that a total of $n/4$ dollars of subsidy suffices to ensure a proportional allocation. Moreover, we show that $n/4$ is tight in the sense that there exists an instance with $n$ agents for which every proportional allocation requires a total subsidy of at least $n/4$. We also consider the weighted case and show that a total subsidy of $(n-1)/2$ suffices to ensure a weighted proportional allocation., Comment: 24 pages, 4 figures

We consider the online bipartite matching problem on $(k,d)$-bounded graphs, where each online vertex has at most $d$ neighbors, each offline vertex has at least $k$ neighbors, and $k\geq d\geq 2$. The model of $(k,d)$-bounded graphs is proposed by Naor and Wajc (EC 2015 and TEAC 2018) to model the online advertising applications in which offline advertisers are interested in a large number of ad slots, while each online ad slot is interesting to a small number of advertisers. They proposed deterministic and randomized algorithms with a competitive ratio of $1 - (1-1/d)^k$ for the problem, and show that the competitive ratio is optimal for deterministic algorithms. They also raised the open questions of whether strictly better competitive ratios can be achieved using randomized algorithms, for both the adversarial and stochastic arrival models. In this paper we answer both of their open problems affirmatively. For the adversarial arrival model, we propose a randomized algorithm with competitive ratio $1 - (1-1/d)^k + \Omega(d^{-4}\cdot e^{-\frac{k}{d}})$ for all $k\geq d\geq 2$. We also consider the stochastic model and show that even better competitive ratios can be achieved. We show that for all $k\geq d\geq 2$, the competitive ratio is always at least $0.8237$. We further consider the $b$-matching problem when each offline vertex can be matched at most $b$ times, and provide several competitive ratio lower bounds for the adversarial and stochastic model., Comment: Some error was discovered in the analysis for the stochastic setting

We consider the problem of fairly allocating a sequence of indivisible items that arrive online in an arbitrary order to a group of n agents with additive normalized valuation functions. We consider both the allocation of goods and chores and propose algorithms for approximating maximin share (MMS) allocations. When agents have identical valuation functions the problem coincides with the semi-online machine covering problem (when items are goods) and load balancing problem (when items are chores), for both of which optimal competitive ratios have been achieved. In this paper, we consider the case when agents have general additive valuation functions. For the allocation of goods, we show that no competitive algorithm exists even when there are only three agents and propose an optimal 0.5-competitive algorithm for the case of two agents. For the allocation of chores, we propose a (2-1/n)-competitive algorithm for n>=3 agents and a square root of 2 (approximately 1.414)-competitive algorithm for two agents. Additionally, we show that no algorithm can do better than 15/11 (approximately 1.364)-competitive for two agents., Comment: 29 pages, 1 figure (to appear in ICML 2023)

We consider the edge-weighted online stochastic matching problem, in which an edge-weighted bipartite graph G=(I\cup J, E) with offline vertices J and online vertex types I is given. The online vertices have types sampled from I with probability proportional to the arrival rates of online vertex types. The online algorithm must make immediate and irrevocable matching decisions with the objective of maximizing the total weight of the matching. For the problem with general arrival rates, Feldman et al. (FOCS 2009) proposed the Suggested Matching algorithm and showed that it achieves a competitive ratio of 1-1/e \approx 0.632. The ratio has recently been improved to 0.645 by Yan (2022), who proposed the Multistage Suggested Matching (MSM) algorithm. In this paper, we propose the Evolving Suggested Matching (ESM) algorithm, and show that it achieves a competitive ratio of 0.650.

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 its 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 existence of fair and efficient allocations and propose efficient algorithms for the computation of WEF1 and PO allocations for the 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., Comment: 26 pages, 2 figures

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 results to submodular objective functions and Matroid rank constraints., Comment: To appear in AAAI 2023

Currently, deep learning methods with stacking small size convolutional filters are widely used for automatic modulation classification (AMC). In this report, we find some experienced improvements by using large kernel size for convolutional deep convolution neural network based AMC, which is more efficient in extracting multi-scale features of the raw signal I/Q sequence data. Also, Squeeze-and-Excitation (SE) mechanisms can significantly help AMC networks to focus on the more important features of the signal. As a result, we propose a multi-scale feature network with large kernel size and SE mechanism (SE-MSFN) in this paper. SE-MSFN achieves state-of-the-art classification performance on the public well-known RADIOML 2018.01A dataset, with average classification accuracy of 64.50%, surpassing CLDNN by 1.42%, maximum classification accuracy of 98.5%, and an average classification accuracy of 85.53% in the lower SNR range 0dB to 10dB, surpassing CLDNN by 2.85%. In addition, we also verified that ensemble learning can help further improve classification performance. We hope this report can provide some references for developers and researchers in practical scenes., Comment: Accepted by IJCNN2022

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., Comment: This survey unifies and extends preliminary versions that appeared in IJCAI 2022 (arXiv:2202.07551) and SIGecom Exchanges (arXiv:2202.08713). It has been accepted for publication to the journal of Artificial Intelligence (AIJ)

In this work, we study the single-choice prophet inequality problem, where a gambler faces a sequence of~$n$ online i.i.d. random variables drawn from an unknown distribution. When a variable reveals its value, the gambler needs to decide irrevocably whether or not to accept the value. The goal is to maximize the competitive ratio between the expected gain of the gambler and that of the maximum variable. It is shown by Correa et al. 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 or $\Omega(n)$ uniform samples are given, the optimal competitive ratio of 0.7451 can be achieved. In this paper, we study a new model in which the algorithm has access to an oracle that answers quantile queries about the distribution and investigate to what extent we can use a small number of queries to achieve good competitive ratios. We first use the answers from the queries to implement the threshold-based algorithms and show that with two thresholds our algorithm achieves a competitive ratio of $0.6786$. Motivated by the two-threshold algorithm, we design the observe-and-accept algorithm that requires only a single query. This algorithm sets a threshold in the first phase by making a query and uses the maximum realization from the first phase as the threshold for the second phase. It can be viewed as a natural combination of the single-threshold algorithm and the algorithm for the secretary problem. By properly choosing the quantile to query and the break-point between the two phases, we achieve a competitive ratio of $0.6718$, beating the benchmark of $1-1/e$., Comment: 32 pages, 2 figures

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., Comment: Accepted by IJCAI-2022

The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.

A new class of spatially-coupled turbo-like codes (SC-TCs), dubbed generalized spatially coupled parallel concatenated codes (GSC-PCCs), is introduced. These codes are constructed by applying spatial coupling on parallel concatenated codes (PCCs) with a fraction of information bits repeated $q$ times. GSC-PCCs can be seen as a generalization of the original spatially-coupled parallel concatenated codes proposed by Moloudi et al. [2]. To characterize the asymptotic performance of GSC-PCCs, we derive the corresponding density evolution equations and compute their decoding thresholds. The threshold saturation effect is observed and proven. Most importantly, we rigorously prove that any rate-$R$ GSC-PCC ensemble with 2-state convolutional component codes achieves at least a fraction $1-\frac{R}{R+q}$ of the capacity of the binary erasure channel (BEC) for repetition factor $q\geq2$ and this multiplicative gap vanishes as $q$ tends to infinity. To the best of our knowledge, this is the first class of SC-TCs that are proven to be capacity-achieving. Further, the connection between the strength of the component codes, the decoding thresholds of GSC-PCCs, and the repetition factor are established. The superiority of the proposed codes with finite blocklength is exemplified by comparing their error performance with that of existing SC-TCs via computer simulations., Comment: Revised version, 36 pages, 10 figures, 4 tables. arXiv admin note: text overlap with arXiv:2105.00698

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 4.45-approximation of EFX allocation. For n>=4 agents, our algorithm always computes a (3n^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., Comment: Include new results about partial EFX allocations and improved results regarding approximate EFX allocations

In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a 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, who is 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). The computation of both exact and approximate EF1 allocations remains largely open, despite a recent effort by Wu et al. (IJCAI 2021) in showing that any budget-feasible allocation that maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper, we move one step forward by showing that for agents with identical additive valuations, a 1/2-approximate EF1 allocation can be computed in polynomial time. For the uniform-budget and two-agent cases, we propose efficient algorithms for computing an exact EF1 allocation. We also consider the large budget setting, i.e., when the item sizes are infinitesimal compared with the agents' budgets, and show that both the NSW maximizing allocation and the allocation our polynomial-time algorithm computes have an approximation close to 1 regarding EF1.

We introduce generalized spatially coupled parallel concatenated codes (GSC-PCCs), a class of spatially coupled turbo-like codes obtained by coupling parallel concatenated codes (PCCs) with a fraction of information bits repeated before the PCC encoding. GSC-PCCs can be seen as a generalization of the original spatially coupled parallel concatenated convolutional codes (SC-PCCs) proposed by Moloudi et al. [1]. To characterize the asymptotic performance of GSC-PCCs, we derive the corresponding density evolution equations and compute their decoding thresholds. We show that the proposed codes have some nice properties such as threshold saturation and that their decoding thresholds improve with the repetition factor $q$. Most notably, our analysis suggests that the proposed codes asymptotically approach the capacity as $q$ tends to infinity with any given constituent convolutional code., Comment: 6 pages, 3 figures, accepted by the 2021 IEEE International Symposium on Information Theory