We study the fair allocation of indivisible goods across groups of agents, where each agent fully enjoys all goods allocated to their group. We focus on groups of two (couples) and other groups of small size. For two couples, an EF1 allocation — one in which all agents find their group's bundle no worse than the other group's, up to one good — always exists and can be found efficiently. For three or more couples, EF1 allocations need not exist. Turning to proportionality, we show that, whenever groups have size at most k, a PROPk allocation exists and can be found efficiently. In fact, our algorithm additionally guarantees (fractional) Pareto optimality and PROP1 to the first agent in each group, PROP2 to the second, and so on, for an arbitrary agent ordering. In special cases, we show that there are PROP1 allocations for any number of couples.
论文检索
输入标题、作者或关键词，从 2,854 篇学术成果中精准定位
We study the fair allocation of indivisible goods with variable groups. In this model, the goal is to partition the agents into groups of given sizes and allocate the goods to the groups in a fair manner. We show that for any number of groups and corresponding sizes, there always exists an envy-free up to one good (EF1) outcome, thereby generalizing an important result from the individual setting. Our result holds for arbitrary monotonic utilities and comes with an efficient algorithm. We also prove that an EF1 outcome is guaranteed to exist even when the goods lie on a path and each group must receive a connected bundle. In addition, we consider a probabilistic model where the utilities are additive and drawn randomly from a distribution. We show that if there are n agents and the number of goods m is divisible by the number of groups k, then an envy-free outcome exists with high probability if m = ω(log n), and this bound is tight. On the other hand, if m is not divisible by k, then an envy-free outcome is unlikely to exist as long as m = o(√n).
Incentives for early arrival (I4EA) was recently proposed for studying online cooperative games. In an online cooperative game, players arrive in an unknown order, and the value increase after each player arrived should be distributed immediately among all the arrived players. Although there is only one arriving order in the game, we also hope that the value distribution is equal to their Shapley value in expectation. To achieve these goals, the early solutions ignored the fairness in each single arriving order. More specifically, an important player may receive nothing in a game, which seems unfair in reality. To combat this, we propose refined fairness in this paper and design new solutions in 0-1 value games. Specifically, we compute the distance of the distribution in each order to the Shapley value and aim to minimize it. We propose a new mechanism called Egalitarian Value-Sharing (EVS) to do so. We also show that the mechanism can maximize the egalitarian welfare among all the players who made contributions.
We study the fair division of indivisible chores among agents with additive disutility functions. We investigate the existence of allocations satisfying the popular fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. The existence of 4-EFX allocations was recently established by Garg, Murhekar, and Qin (2025). We improve this guarantee by proving the existence of 2-EFX allocations for all instances with additive disutilities. This approximation was previously known only for restricted instances such as bivalued disutilities (Lin, Wu, and Zhou (2025)) or three agents (Afshinmehr, Ansaripour, Danaei, and Mehlhorn (2024)). We obtain our result by providing a general framework for achieving approximate-EFX allocations. The approach begins with a suitable initial allocation and performs a sequence of local swaps between the bundles of envious and envied agents. For our main result, we begin with an initial allocation that satisfies envy-freeness up to one chore (EF1) and Pareto-optimality (PO); the existence of such an allocation was recently established in a major breakthrough by Mahara (2025). We further demonstrate the strength and generality of our framework by giving simple and unified proofs of existing results, namely (i) 2-EFX for bivalued instances, (ii) 2-EFX for three agents, (iii) EFX when the number of chores is at most twice the number of agents, and (iv) 4-EFX for all instances. We expect this framework to have broader applications in approximate-EFX due to its simplicity and generality.
We study the problem of fairly allocating a set of m goods among n agents in the asymptotic setting, where each item's value for each agent is drawn from an underlying joint distribution. Prior works have shown that if this distribution is well-behaved, then an envy-free allocation exists with high probability when m=Ω(n log n). Under the stronger assumption that item values are independently and identically distributed (i.i.d.) across agents, it is known that this requirement improves to m=Ω(n log n / log log n), which is tight. However, these results rely on non-strategyproof mechanisms, such as maximum-welfare allocation or the round-robin algorithm, limiting their applicability in settings with strategic agents. In this work, we extend the theory to a broader, more realistic class of joint value distributions, allowing for correlations among agents, atomicity, and unequal probabilities of having the highest value for an item. We show that envy-free allocations continue to exist with a high probability when m=Ω(n log n). More importantly, we give a new randomized mechanism that is truthful in expectation, efficiently implementable in polynomial time, and outputs envy-free allocations with high probability, answering an open question from the literature. We further extend our mechanism to settings with asymptotic weighted fair division and multiple agent types and good types, proving new results in each case.
This paper investigates the problem of shared resource allocation, where a set of agents must be assigned to heterogeneous resources, with each agent allocated exactly one resource and each resource potentially shared by multiple agents. An agent’s utility for a given resource is jointly determined by the resource's type and the number of agents sharing it. We focus on two fundamental classes of monotone valuations: monotone nondecreasing and monotone nonincreasing, where an agent’s utility respectively increases or decreases with the number of agents sharing the resource. Within this shared resource framework, we examine classical notions of fairness and stability, including maximin-share fairness, envy-freeness, Nash stability, and two epistemic relaxations—epistemic envy-freeness and epistemic Nash stability—as well as swap stability. We propose formal definitions adapted to this setting and systematically analyze the relationships among these concepts. The primary contributions of this work consist of establishing existence and computational complexity results for each notion under both monotonicity assumptions and developing polynomial-time algorithms in cases where fair or stable allocations are guaranteed to exist.
Dividing Indivisible Items for the Benefit of All: It Is Hard to Be Fair Without Social Awareness
PDF ↗In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining some fairness criterion. We reveal that the complexity of the problem heavily depends on whether the agents are socially aware, i.e., they take into consideration the social impact functions. For socially unaware agents, we prove that the problem is NP-hard for a variety of fairness notions, and that it is tractable only for very restricted cases, e.g., if for every agent valuation equals social impact and it is binary. On the other hand, social awareness allows for fair allocations that maximize social impact, and such allocations can be computed in polynomial time. Interestingly, the problem becomes again intractable as soon as the definition of social awareness is relaxed.
We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX) — an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While recent results have established EFX existence for settings with at most three distinct valuations and for two types of goods, the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasiliniear time when there are two types of goods, given that the valuations are positive. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation.
We study the problem of (approximate) maximin share (MMS) allocation of indivisible items among a set of agents. We focus on the graphical valuation model, in which the input is given by a graph where edges correspond to items, and vertices correspond to agents. An edge may have non-zero marginal value only for its incident vertices. We study additive, XOS and subadditive valuations and we present positive and negative results for (approximate) MMS fairness, and also for (approximate) pair-wise maximin share (PMMS) fairness.
We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. We prove existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent i there exist values aᵢ > bᵢ such that agent i assigns value vᵢ({g}) ∈ {aᵢ, bᵢ} to each good g. We establish an analogous existence result for PMMS allocations when aᵢ is divisible by bᵢ. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle S has value vᵢ(S) ∈ {0, 1}. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.
The fair division of indivisible goods is not only a subject of theoretical research, but also an important problem in practice, with solutions being offered on several online platforms. Little is known, however, about the characteristics of real-world allocation instances and how they compare to synthetic instances. Using dimensionality reduction, we compute a map of allocation instances: a 2-dimensional embedding such that an instance's location on the map is predictive of the instance's origin and other key instance features. Because the axes of this map closely align with the utility matrix's two largest singular values, we define a second, explicit map, which we theoretically characterize.
Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations
PDF ↗We revisit the setting of fair allocation of indivisible items among agents with heterogeneous, non-monotone valuations. We explore the existence and efficient computation of allocations that approximately satisfy either envy-freeness or equity constraints. Approximate envy-freeness ensures that each agent values her bundle at least as much as those given to the others, after some (or any) item removal, while approximate equity guarantees roughly equal valuations among agents, under similar adjustments. As a key technical contribution of this work, by leveraging fixed-point theorems (such as Sperner's Lemma and its variants), we establish the existence of envy-free-up-to-one-good-and-one-chore (EF1_g^c) and equitable-up-to-one-good-and-one-chore (EQ1_g^c) allocations, for non-monotone valuations that are always either non-negative or non-positive. These notions represent slight relaxations of the well-studied envy-free-up-to-one-item (EF1) and equitable-up-to-one-item (EQ1) guarantees, respectively. Our existential results hold even when items are arranged in a path and bundles must form connected sub-paths. The case of non-positive valuations, in particular, has been solved by proving a novel multi-coloring variant of Sperner's Lemma that constitutes a combinatorial result of independent interest. In addition, we also design a polynomial-time dynamic programming algorithm that computes an EQ1_g^c allocation. For monotone non-increasing valuations and path-connected bundles, all the above results can be extended to EF1 and EQ1 guarantees as well. Finally, we provide existential and computational results for certain stronger up-to-any-item equity notions under objective valuations, where items are partitioned into goods and chores.
Equitability is a well-studied fairness notion in fair division, where an allocation is equitable if all agents receive equal utility from their allocation. For indivisible items, an exactly equitable allocation may not exist, hence, a natural relaxation is EQ1, which stipulates that any inequitability should be resolved by the removal of a single item. In this paper, we study equitability in the context of randomized allocations. Specifically, we aim to achieve equitability in expectation (ex ante EQ) and require that each deterministic outcome in the support satisfies ex post EQ1. Such an allocation is commonly known as a `Best of Both Worlds' allocation, and has been studied, e.g., for envy-freeness and MMS. We characterize the existence of such allocations using a geometric condition on convex combinations of allocations, and use this to give comprehensive results on both existence and computation. For two agents, we show that ex ante EQ and ex post EQ1 allocations always exist and can be computed in polynomial time. For three or more agents, however, such allocations may not exist. We prove that deciding existence of such allocations is strongly NP-complete in general, and weakly NP-complete even for three agents. We also present a pseudo-polynomial time algorithm for a constant number of agents. Additionally, we show that when agents have binary valuations, best of both worlds allocations that additionally satisfy welfare guarantees exist and are efficiently computable.
On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting
PDF ↗Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear programming for deciding whether and when core-stable committees are guaranteed to exist. In contrast to SAT-based approaches popular in computational social choice, our method can produce proofs for a specific number of candidates independent of the number of voters. In addition to these computational gains, our program lends itself to a novel duality-based reformulation of the core stability problem, from which we obtain new existence results in special cases. Further, we use our framework to reveal previously unknown relationships between core stability and other desirable properties, such as notions of priceability.
In recent years, research in Participatory Budgeting (PB) has put a greater emphasis on rules satisfying notions of fairness and proportionality, with the Method of Equal Shares (MES) being a prominent example. However, proportionality can come at a cost to the total utilitarian welfare. Our work formalizes this relationship, by deriving minimum utilitarian welfare guarantees for MES for a subclass of satisfaction functions called DNS functions, which includes two of the most popular ways of measuring a voter’s utility in the PB setting: considering (1) the total cost of approved projects or (2) the total number of those projects. Our results are parameterized in terms of minimum and maximum project costs, which allows us to improve on the mostly negative results found in prior studies, and reduce to the existing multiwinner guarantee when project costs are equal. We show that our guarantees are asymptotically tight for rules satisfying Extended Justified Representation up to one project, showing that no proportional rule can achieve a better utilitarian guarantee than MES.
Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
PDF ↗Although approximate notions of envy-freeness—such as envy-freeness up to one good (EF1)—have been extensively studied for indivisible goods, the seemingly simpler fairness concept of proportionality up to one good (PROP1) has received far less attention. For additive valuations, every EF1 allocation is PROP1, and well-known algorithms such as round-robin and envy-cycle elimination compute such allocations in polynomial time. PROP1 is also compatible with Pareto efficiency, as maximum Nash welfare allocations are EF1 and hence PROP1. We ask whether these favorable properties extend to non-additive valuations. We study a broad class of allocation instances with satiating goods, where agents have non-negative valuation functions that need not be monotone, allowing for negative marginal values. We present the following results: --EF1 implies PROP1 for submodular valuations over satiating goods, ensuring existence and efficient computation via envy-cycle elimination for monotone submodular valuations; --Round-robin computes a partial PROP1 allocation after the second-to-last round for satiating submodular goods and a complete PROP1 for submodular monotone valuations; --PROP1 allocations for satiating subadditive goods can be computed in polynomial-time; --Maximum Nash welfare allocations are PROP1 for monotone submodular goods, revealing yet another facet of their ``unreasonable fairness.''
Graph neural networks (GNNs) have emerged as the mainstream paradigm for graph representation learning due to their effective message aggregation. However, this advantage also amplifies biases inherent in graph topology, raising fairness concerns. Existing fairness-aware GNNs provide satisfactory performance on fairness metrics such as Statistical Parity and Equal Opportunity while maintaining acceptable accuracy trade-offs. Unfortunately, we observe that this pursuit of fairness metrics neglects the GNN's ability to predict negative labels, which renders their predications with extremely high False Positive Rates (FPRs), resulting in negative effects in high-risk scenarios. To this end, we advocate that classification performance should be carefully calibrated while improving fairness, rather than simply constraining accuracy loss. Furthermore, we propose Fair GNN via Structural Entropy (FairGSE), a novel framework that maximizes two-dimensional structural entropy (2D-SE) to improve fairness without neglecting false positives. Experiments on several real-world datasets show FairGSE reduces FPR by 39% vs. state-of-the-art fairness-aware GNNs, with comparable fairness improvement.
From Points to Coalitions: Hierarchical Contrastive Shapley Values for Prioritizing Data Samples
PDF ↗How should we quantify the value of each training example when datasets are large, heterogeneous, and geometrically structured? Classical Data-Shapley answers in principle, but its O(n!) complexity and point-wise perspective are ill-suited to modern scales. We propose Hierarchical Contrastive Data Valuation (HCDV), a three-stage framework that (i) learns a contrastive, geometry-preserving representation, (ii) organizes the data into a balanced coarse-to-fine hierarchy of clusters, and (iii) assigns Shapley-style pay-offs to coalitions via local Monte-Carlo games whose budgets are propagated downward. HCDV collapses the factorial burden to O(T∑ℓKℓ) = O(TKmax log n), rewards examples that sharpen decision boundaries, and regularizes outliers through curvature-based smoothness. We prove that HCDV approximately satisfies the four Shapley axioms with surplus loss O(η log n), enjoys sub-Gaussian coalition deviation Õ(1/√T), and incurs at most kε∞ regret for top-k selection. Experiments on four benchmarks — tabular, vision, streaming, and a 45 M-sample CTR task — plus the OpenDataVal suite show that HCDV lifts accuracy by up to +5 pp, slashes valuation time by up to 100×, and directly supports tasks such as augmentation filtering, low-latency streaming updates, and fair marketplace payouts.
This paper revisits fairness-aware interactive recommendation (e.g., TikTok, KuaiShou) by introducing a novel control knob, i.e., the lifecycle of items. We make threefold contributions. First, we conduct a comprehensive empirical analysis and uncover that item lifecycles in short-video platforms follow a compressed three-phase pattern, i.e., rapid growth, transient stability, and sharp decay, which significantly deviates from the classical four-stage model (introduction, growth, maturity, decline). Second, we introduce LHRL, a lifecycle-aware hierarchical reinforcement learning framework that dynamically harmonizes fairness and accuracy by leveraging phase-specific exposure dynamics. LHRL consists of two key components: (1) PhaseFormer, a lightweight encoder combining STL decomposition and attention mechanisms for robust phase detection; (2) a two-level HRL agent, where the high-level policy imposes phase-aware fairness constraints, and the low-level policy optimizes immediate user engagement. This decoupled optimization allows for effective reconciliation between long-term equity and short-term utility. Third, experiments on multiple real-world interactive recommendation datasets demonstrate that LHRL significantly improves both fairness and user engagement. Furthermore, the integration of lifecycle-aware rewards into existing RL-based models consistently yields performance gains, highlighting the generalizability and practical value of our approach.
We study a general framework of optimization with the aim to compute fair solutions in settings with a set of agents whose valuations are combined using an aggregation function. The strength of our framework lies (1) in its generality and (2) in the fact that we leverage the power of ex-ante fairness, a concept that has recently gained much attention in the scope of fair allocation and fairness in AI in general. More precisely, in our setting there are n set functions f₁, …, fₙ (e.g., the valuation functions of n agents) that are combined using an aggregation function g (e.g., the minimum, Nash social welfare, p-norm). The power of ex-ante fairness is obtained by allowing as a feasible solution not simply a finite set S, but instead a distribution Π over feasible sets. The goal in our setting is then to find a probability distribution p in Π that maximizes the value resulting from aggregating (using g) the n expected values of the functions f₁, …, fₙ obtained when sampling a set S according to the distribution p. We stress that this is different from maximizing the expected value of g (ex-post fairness) and typically allows for much fairer solutions. We give three different greedy algorithms for three different settings of this framework and prove that they achieve constant approximation guarantees under certain realistic assumptions. For some of the settings, we show that these approximation guarantees are tight. Specific scenarios that can be modelled using our framework include fair information diffusion in social networks, fair submodular matching problems, and ex-ante versions of item assignment problems.