We consider the problem of fairly dividing a set items. Much fair division literature assumes that items are ``goods'' i.e., they yield positive utility for agents. There is also some work where ``chores'' negative In this paper, we more general scenario an agent may have or each item. This framework captures, e.g., task assignment, agents can both and utilities task. show whereas axiomatic computational results extend to setting, others do not. present several new efficient algorithms...

We develop a model of multiwinner elections that combines performance-based measures the quality committee (such as, e.g., Borda scores members) with diversity constraints. Specifically, we assume candidates have certain attributes as being male or female, junior senior, etc.) and goal is to elect that, on one hand, has high score regarding given performance measure, but other meets requirements (e.g., form "at least 30% members are at 40% females"). analyze computational complexity...

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. propose two variants weighted envy-freeness up to one item (WEF1): strong , where envy can be eliminated by removing an from envied agent’s bundle, weak either (as version) or replicating bundle envying bundle. show additive valuations, is both Pareto optimal strongly WEF1 always exists computed pseudo-polynomial time; moreover, maximizes...

We consider fair allocation of indivisible items under an additional constraint: there is undirected graph describing the relationship between items, and each agent's share must form a connected subgraph this graph. This framework captures, e.g., land plots, where describes accessibility relation among plots. focus on agents that have additive utilities for several common division solution concepts, such as proportionality, envy-freeness maximin guarantee. While finding good allocations...

We study the existence of allocations indivisible goods that are envy-free up to one good (EF1), under additional constraint each bundle needs be connected in an underlying item graph G. When items arranged a path, we show EF1 guaranteed exist for arbitrary monotonic utility functions over bundles, provided either there at most four agents, or any number agents but they all have identical functions. Our proofs based on classical arguments from divisible cake-cutting setting, and involve...

We study the problem of allocating indivisible items to agents with additive valuations, under additional constraint that bundles must be connected in an underlying item graph. Previous work has considered existence and complexity fair allocations. finding allocation is Pareto-optimal. While it easy find efficient when graph a path or star, NP-hard for many other topologies, even trees bounded pathwidth maximum degree 3. show on path, there are instances where no Pareto-optimal satisfies...

We study the allocation of indivisible goods that form an undirected graph and quantify loss fairness when we impose a constraint each agent must receive connected subgraph. Our focus is on well-studied notion maximin share fairness. introduce price connectivity to capture largest gap between graph-specific unconstrained share, derive bounds this quantity which are tight for large classes graphs in case two agents paths stars general case. For instance, with show biconnected it possible...

Abstract Fair division has been studied in both continuous and discrete contexts. One strand of the literature seeks to award each agent with a single connected piece—a subinterval. The analogue for case corresponds fair graph , where allocations must be contiguous so that bundle vertices is required induce subgraph. With envy-freeness up one item ( EF1 ) as fairness criterion, however, positive results three or more agents have mostly limited traceable graphs. We introduce tangles new...

The airport problem is a classical and well-known model of fair cost-sharing for single facility among multiple agents. This article extends it to more general setting involving facilities. Specifically, in our model, each agent selects shares the cost with other agents using same facility. scenario frequently occurs sharing economies, such as subscription costs multi-user license or taxi fares customers traveling potentially different destinations along route. Our can be viewed coalition...

We propose a new variant of the group activity selection problem (GASP), where agents are placed on social network and activities can only be assigned to connected subgroups. show that if multiple groupscan simultaneously engage in same activity, finding stable outcome is easy as long networkis acyclic. In contrast, each single only, outcomes becomes computationally intractable, even underlying very simple: determining whether given instance GASP admits Nash turns out NP-hard when path,...

We consider the problem of fairly dividing a set items. Much fair division literature assumes that items are `goods' i.e., they yield positive utility for agents. There is also some work where `chores' negative In this paper, we more general scenario an agent may have or each item. This framework captures, e.g., task assignment, agents can both and utilities task. show whereas axiomatic computational results extend to setting, others do not. present several new efficient algorithms finding...

We study hedonic coalition formation games in which cooperation among the players is restricted by a graph structure: subset of can form if and only they are connected given graph. investigate complexity finding stable outcomes such games, for several notions stability. In particular, we provide an efficient algorithm that finds individually partition arbitrary game on acyclic also introduce new stability concept -in-neighbor stability- tailored our setting. show problem in-neighbor outcome...

We study the allocation of indivisible goods that form an undirected graph and quantify loss fairness when we impose a constraint each agent must receive connected subgraph. Our focus is on well-studied notions including envy-freeness maximin share fairness. introduce price connectivity to capture largest multiplicative gap between graph-specific unconstrained derive bounds this quantity which are tight for large classes graphs in case two agents paths stars general case. For instance, with...

In this article, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond matroid rank functions . This is a versatile valuation class with several desirable properties (such as monotonicity submodularity), which naturally lends itself number real-world domains. We use these our advantage; first, show that when agent valuations are functions, socially optimal (i.e., utilitarian social welfare-maximizing) achieves envy-freeness up...

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money, subsidize envious agents. In paper, we aim design truthful allocation mechanism goods achieve both efficiency criteria with limited amount subsidy. Following the work Halpern Shah, our central question as...

We initiate the study of fairness among classes agents in online bipartite matching where there is a given set offline vertices (aka agents) and another items) that arrive must be matched irrevocably upon arrival. In this setting, are partitioned into required to fair with respect classes. adopt popular notions (e.g. envy-freeness, proportionality, maximin share) their relaxations setting deterministic randomized algorithms for indivisible items (leading integral matchings) divisible...

We study a fair division setting in which number of players are to be fairly distributed among set teams. In our model, not only do the teams have preferences over as canonical setting, but also focus on guaranteeing envy-freeness up one player (EF1) for together with stability condition both sides. show that an allocation satisfying EF1, swap stability, and individual always exists can computed polynomial time, even when may positive or negative values players. Similarly, balanced stable...

In Group Activity Selection Problem with graph structure (gGASP), players form coalitions to participate in activities and have preferences over pairs of the (activity, group size); moreover, a can only engage same activity if members connected subset underlying communication structure. We study parameterized complexity finding outcomes gGASP that are Nash stable, individually stable or core stable. For parameter `number activities', we propose an FPT algorithm for stability case where...

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both equally. Prior work shows that, when is represented by an interval, consensus with at most n cuts always exists but hard compute even for agents simple valuation functions. In this paper, we study in natural setting which consists set items without linear ordering. For and additively separable utilities, present polynomial-time algorithm computes show are almost surely necessary...

Cake-cutting is a fundamental model of dividing heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem indivisible goods fairly under connectivity constraints path. We prove that connected division items satisfying discrete counterpart envy-freeness, called envy-freeness up to one good (EF1), always exists for any number agents n with monotone valuations. Our result settles an open question raised by Bilò et al. (2019), who...