We study the problem of fairly allocating m indivisible chores among n agents with additive cost functions. While the maximin share (MMS) is a prominent fairness criterion in theory, exact MMS allocations do not always exist. This has motivated relaxation that guarantees MMS fairness for only a subset of agents, aiming to maximize the number of satisfied agents. However, for chore allocation, guaranteeing most agents their full MMS is trivial but highly unsatisfactory, e.g., overburdening a single agent, which is undesirable in real-world platforms aiming for user retention and satisfaction. To address this, we propose a stronger and more practical notion called α-approximate all-but-one MMS (α-AMMS), which guarantees that n-1 agents receive their full MMS value, while the remaining agent receives an α-approximation. This model reflects common platform design goals, where satisfying the vast majority of users is critical, and near-fairness for the rest is acceptable. We show that there exist α-AMMS allocations, with α = 9/8 for three agents; α = 4/3 for four agents; and α = (n+1)2/4n for n ≥ 5 agents.

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.

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.

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.

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 the allocation of goods and chores separately and propose algorithms for approximating maximin share (MMS) allocations for both settings. 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\geq 3$ agents and a $\sqrt{2}\approx 1.414$-competitive algorithm for two agents. Additionally, we show that no algorithm can do better than $15/11\approx 1.364$-competitive for two agents.

We study how to fairly allocate a set of indivisible chores to a group of agents, where each agent i ∈ N has an additive cost function ci and a non-negative weight wi that represents its obligation for undertaking the chores. We consider the fairness notion of weighted envy-freeness up to one item (WEF1), which requires that the weighted cost ci(Xi \ {e})/wi of each agent i after removing the most costly item e is at most ci(Xj)/wj for any other agent j. While WEF1 allocations for goods can be computed in polynomial time (Chakraborty et al. TEAC 2021), its existence for chores is still an open problem. In this work, we answer this open problem affirmatively. We show that WEF1 allocations for chores always exist and can be computed in polynomial time.

The accurate trajectory prediction of surrounding vehicles is crucial for the sustainability and safety of connected and autonomous vehicles under mixed traffic streams in the real world. The task of trajectory prediction is challenging because there are all kinds of factors affecting the motions of vehicles, such as the individual movements, the ambient driving environment especially road conditions, and the interactions with neighboring vehicles. To resolve the above issues, this work proposes a novel Heterogeneous Context-Aware Graph Convolutional Networks following the Encoder-Decoder architecture, which simultaneously extracts the hidden contexts from individual historical trajectories, varying driving scene, and inter-vehicle interactional behaviors. Specifically, the historical vehicle trajectories are fed into Temporal Convolutional Network to capture the individual context. Besides, a 2-Dimensional Convolutional Network with temporal attention is designed for transforming the scene image stream into compressing scene context. Then a Spatio-Temporal Dynamic Graph Convolutional Networks is devised to model the evolving interactional patterns, which incorporates the acquired individual and scene contexts as the representation of the node. Finally, the aforementioned three contexts are combined and fed into the decoder to produce future trajectories. The proposed model is validated on two real-world datasets which contain various driving scenarios. Results demonstrated that the proposed model outperforms state-of-the-art methods in prediction accuracy and achieves immense stability towards different vehicle states.

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.