Search

We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least $1/2$ of the agents in each group, and prove that the $1/2$ fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting., Comment: Appears in the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI), 2018

Ranking alternatives is a natural way for humans to explain their preferences. It is being used in many settings, such as school choice, course allocations and residency matches. In some cases, several `items' are given to each participant. Without having any information on the underlying cardinal utilities, arguing about fairness of allocation requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the difference between two items at the top is larger than the difference between two items at the bottom. This assumption implies a preference extension which we call diminishing differences (DD), where X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for finding a necessarily-DD-proportional allocation if it exists. Using simulations, we show that with high probability, a necessarily-proportional allocation does not exist but a necessarily-DD-proportional allocation exists, and moreover, that allocation is proportional according to the underlying cardinal utilities. We also consider chore allocation under the analogous condition --- increasing-differences., Comment: Revised version, based on very helpful suggestions of JAIR referees. Gaps in some proofs were filled, more experiments were done, and more

Competitive equilibrium (CE) is a fundamental concept in market economics. Its efficiency and fairness properties make it particularly appealing as a rule for fair allocation of resources among agents with possibly different entitlements. However, when the resources are indivisible, a CE might not exist even when there is one resource and two agents with equal incomes. Recently, Babaioff and Nisan and Talgam-Cohen (2017) have suggested to consider the entire space of possible incomes, and check whether there exists a competitive equilibrium for almost all income-vectors --- all income-space except a subset of measure zero. They proved various existence and non-existence results, but left open the cases of four goods and three or four agents with monotonically-increasing preferences. This paper proves non-existence in both these cases, thus completing the characterization of CE existence for almost all incomes in the domain of monotonically increasing preferences. Additionally, the paper provides a complete characterization of CE existence in the domain of monotonically decreasing preferences, corresponding to allocation of chores. On the positive side, the paper proves that CE exists for almost all incomes when there are four goods and three agents with additive preferences. The proof uses a new tool for describing a CE, as a subgame-perfect equilibrium of a specific sequential game. The same tool also enables substantially simpler proofs to the cases already proved by Babaioff et al. Additionally, this paper proves several strong fairness properties that are satisfied by any CE allocation, illustrating its usefulness for fair allocation among agents with different entitlements., Comment: All the inexistence results are now stronger - they show that even CE-fairness alone (without efficiency) cannot be attained

Level-1 Consensus is a property of a preference-profile. Intuitively, it means that there exists a preference relation which induces an ordering of all other preferences such that frequent preferences are those that are more similar to it. This is a desirable property, since it enhances the stability of social choice by guaranteeing that there exists a Condorcet winner and it is elected by all scoring rules. In this paper, we present an algorithm for checking whether a given preference profile exhibits level-1 consensus. We apply this algorithm to a large number of preference profiles, both real and randomly-generated, and find that level-1 consensus is very improbable. We support these empirical findings theoretically, by showing that, under the impartial culture assumption, the probability of level-1 consensus approaches zero when the number of individuals approaches infinity. Motivated by these observations, we show that the level-1 consensus property can be weakened while retaining its stability implications. We call this weaker property Flexible Consensus. We show, both empirically and theoretically, that it is considerably more probable than the original level-1 consensus. In particular, under the impartial culture assumption, the probability for Flexible Consensus converges to a positive number when the number of individuals approaches infinity.

There is a heterogeneous resource that contains both good parts and bad parts, for example, a cake with some parts burnt, a land-estate with some parts heavily taxed, or a chore with some parts fun to do. The resource has to be divided fairly among $n$ agents with different preferences, each of whom has a personal value-density function on the resource. The value-density functions can accept any real value --- positive, negative or zero. Each agent should receive a connected piece and no agent should envy another agent. We prove that such a division exists for 3 agents and present preliminary positive results for larger numbers of agents., Comment: Extended version of AAMAS-18 paper. Contains preliminary results indicating that the conjecture is true in two special cases (Section 6)

In the classic cake-cutting problem (Steinhaus, 1948), a heterogeneous resource has to be divided among n agents with different valuations in a proportional way --- giving each agent a piece with a value of at least 1/n of the total. In many applications, such as dividing a land-estate or a time-interval, it is also important that the pieces are connected. We propose two additional requirements: resource-monotonicity (RM) and population-monotonicity (PM). When either the cake or the set of agents changes and the cake is re-divided using the same rule, the utility of all remaining agents must change in the same direction. Classic cake-cutting protocols are neither RM nor PM. Moreover, we prove that no Pareto-optimal proportional division rule can be either RM or PM. Motivated by this negative result, we search for division rules that are weakly-Pareto-optimal --- no other division is strictly better for all agents. We present two such rules. The relative-equitable rule, which assigns the maximum possible relative value equal for all agents, is proportional and PM. The so-called rightmost-mark rule, which is an improved version of the Cut and Choose protocol, is proportional and RM for two agents., Comment: Submitted version. arXiv admin note: substantial text overlap with arXiv:1510.05229

In a large, possibly infinite population, each subject is colored red with probability $p$, independently of the others. Then, a finite sub-population is selected, possibly as a function of the coloring. The imbalance in the sub-population is defined as the difference between the number of reds in it and p times its size. This paper presents high-probability upper bounds (tail-bounds) on this imbalance. To present the upper bounds we define the *UI dimension* --- a new measure for the richness of a set-family. We present three simple rules for upper-bounding the UI dimension of a set-family. Our upper bounds on the imbalance in a sub-population depend only on the size of the sub-population and on the UI dimension of its support. We relate our results to known concepts from machine learning, particularly the VC dimension and Rademacher complexity.

Classic cake-cutting algorithms enable people with different preferences to divide among them a heterogeneous resource (``cake''), such that the resulting division is fair according to each agent's individual preferences. However, these algorithms either ignore the geometry of the resource altogether, or assume it is one-dimensional. In practice, it is often required to divide multi-dimensional resources, such as land-estates or advertisement spaces in print or electronic media. In such cases, the geometric shape of the allotted piece is of crucial importance. For example, when building houses or designing advertisements, in order to be useful, the allotments should be squares or rectangles with bounded aspect-ratio. We thus introduce the problem of fair land division --- fair division of a multi-dimensional resource wherein the allocated piece must have a pre-specified geometric shape. We present constructive division algorithms that satisfy the two most prominent fairness criteria, namely envy-freeness and proportionality. In settings where proportionality cannot be achieved due to the geometric constraints, our algorithms provide a partially-proportional division, guaranteeing that the fraction allocated to each agent be at least a certain positive constant. We prove that in many natural settings the envy-freeness requirement is compatible with the best attainable partial-proportionality., Comment: A preliminary version named 'Envy-free cake-cutting in two dimensions' appeared in the proceedings of AAAI 2015 (https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/viewPaper/9656). The main additions here are: (a) handling multi-dimensional resources of arbitrary shape rather than just rectangles, (b) handling an arbitrary number n of agents rather than just 2 or 3, (c) rewriting most proofs

In a seminal paper, McAfee (1992) presented the first dominant strategy truthful mechanism for double auction. His mechanism attains nearly optimal gain-from-trade when the market is sufficiently large. However, his mechanism may leave money on the table, since the price paid by the buyers may be higher than the price paid to the sellers. This money is included in the gain-from-trade and in some cases it accounts for almost all the gain-from-trade, leaving almost no gain-from-trade to the traders. We present SBBA: a variant of McAfee's mechanism which is strongly budget-balanced. There is a single price, all money is exchanged between buyers and sellers and no money is left on the table. This means that all gain-from-trade is enjoyed by the traders. We generalize this variant to spatially-distributed markets with transit costs., Comment: Accepted to SAGT 2016. This full version (14 pages) includes an additional example

We consider the class of valuations on indivisible items called gross-substitute (GS). This class was introduced by Kelso and Crawford (1982) and is widely used in studies of markets with indivisibilities. GS is a condition on the demand-flow in a specific scenario: some items become more expensive while other items retain their price. We prove that GS implies a much stronger condition, describing the demand-flow in the general scenario in which all prices may change. We prove that the demand of GS agents always flows (weakly) downwards, i.e, from items with higher price-increase to items with lower price-increase. We show that this property is equivalent to GS and is not true when there are complementarities., Comment: 7 pages. Improved examples and added missing proofs

This paper extends the classic cake-cutting problem to a situation in which the "cake" is divided among families. Each piece of cake is owned and used simultaneously by all members of the family. A typical example of such a cake is land. We examine three ways to assess the fairness of such a division, based on the classic no-envy criterion: (a) Average envy-freeness means that for each family, the average value of its share (averaged over all family members) is weakly larger than the average value of any other share; (b) Unanimous envy-freeness means that in each family, each member values the family's share weakly more than any other share; (c) Democratic envy-freeness means that in each family, at least half the members value the family's share weakly more than any other share. We study each of these definitions from both an existential and a computational perspective., Comment: The paper is obsolete - it is subsumed by the paper "Fair Cake-Cutting among Families", arXiv:1510.03903

Motivated by applications such as stock exchanges and spectrum auctions, there is a growing interest in mechanisms for arranging trade in two-sided markets. Existing mechanisms are either not truthful, or do not guarantee an asymptotically-optimal gain-from-trade, or rely on a prior on the traders' valuations, or operate in limited settings such as a single kind of good. We extend the random market-halving technique used in earlier works to markets with multiple kinds of goods, where traders have gross-substitute valuations. We present MIDA: a Multi Item-kind Double-Auction mechanism. It is prior-free, truthful, strongly-budget-balanced, and guarantees near-optimal gain from trade when market sizes of all goods grow to $\infty$ at a similar rate., Comment: Full version of IJCAI-18 paper, with 2 figures. Previous names: "MIDA: A Multi Item-type Double-Auction Mechanism", "A Random-Sampling Double-Auction Mechanism". 10 pages

Inside a two dimensional region ("cake"), there are $m$ non-overlapping tiles of a certain kind ("toppings"). We want to expand the toppings while keeping them non-overlapping, and possibly add some blank pieces of the same "certain kind", such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axes-parallel rectangles. (4) The cake is an axes-parallel rectilinear polygon and the toppings are axes-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks., Comment: A revised version of "Cutting a Cake without Harming the Toppings"

The paper considers fair allocation of resources that are already allocated in an unfair way. This setting requires a careful balance between the fairness considerations and the rights of the present owners. The paper presents re-division algorithms that attain various trade-off points between fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity -- the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity -- the cake is a two-dimensional rectangle or rectilinear polygon and the pieces should be rectangles; (d) convexity -- the cake is a two-dimensional convex polygon and the pieces should be convex. These re-division algorithms have implications on another problem: the price-of-fairness -- the loss of social welfare caused by fairness requirements. Each algorithm implies an upper bound on the price-of-fairness with the respective geometric constraints., Comment: Improved algorithms attaining better constants in redivision algorithms and better price-of-fairness bounds

We consider the classic problem of envy-free division of a heterogeneous good ("cake") among several agents. It is known that, when the allotted pieces must be connected, the problem cannot be solved by a finite algorithm for 3 or more agents. The impossibility result, however, assumes that the entire cake must be allocated. In this paper we replace the entire-allocation requirement with a weaker \emph{partial-proportionality} requirement: the piece given to each agent must be worth for it at least a certain positive fraction of the entire cake value. We prove that this version of the problem is solvable in bounded time even when the pieces must be connected. We present simple, bounded-time envy-free cake-cutting algorithms for: (1) giving each of $n$ agents a connected piece with a positive value; (2) giving each of 3 agents a connected piece worth at least 1/3; (3) giving each of 4 agents a connected piece worth at least 1/7; (4) giving each of 4 agents a disconnected piece worth at least 1/4; (5) giving each of $n$ agents a disconnected piece worth at least $(1-\epsilon)/n$ for any positive $\epsilon$., Comment: The first version was presented at AAMAS 2015: http://dl.acm.org/citation.cfm?id=2773268 . The current version is substantially revised and extended

We study the monotonicity properties of solutions in the classic problem of fair cake-cutting --- dividing a heterogeneous resource among agents with different preferences. Resource- and population-monotonicity relate to scenarios where the cake, or the number of participants who divide the cake, changes. It is required that the utility of all participants change in the same direction: either all of them are better-off (if there is more to share or fewer to share among) or all are worse-off (if there is less to share or more to share among). We formally introduce these concepts to the cake-cutting problem and examine whether they are satisfied by various common division rules. We prove that the Nash-optimal rule, which maximizes the product of utilities, is resource-monotonic and population-monotonic, in addition to being Pareto-optimal, envy-free and satisfying a strong competitive-equilibrium condition. Moreover, we prove that it is the only rule among a natural family of welfare-maximizing rules that is both proportional and resource-monotonic., Comment: Revised version

We study the fair division of a continuous resource, such as a land-estate or a time-interval, among pre-specified groups of agents, such as families. Each family is given a piece of the resource and this piece is used simultaneously by all family members, while different members may have different value functions. Three ways to assess the fairness of such a division are examined. (a) Average Fairness means that each family's share is fair according to the "family value function", defined as the arithmetic mean of the value functions of the family members. (b) Unanimous Fairness means that all members in all families feel that their family's share is fair according to their personal value function. (c) Democratic Fairness means that in each family, at least a fixed fraction (e.g. a half) of the members feel that their family's share is fair. We compare these criteria based on the number of connected components in the resulting division and on their compatibility with Pareto-efficiency., Comment: Add a cool reduction from equitable division among individuals to average-proportional division among families

We consider the classic problem of fairly dividing a heterogeneous good ("cake") among several agents with different valuations. Classic cake-cutting procedures either allocate each agent a collection of disconnected pieces, or assume that the cake is a one-dimensional interval. In practice, however, the two-dimensional shape of the allotted pieces is important. In particular, when building a house or designing an advertisement in printed or electronic media, squares are more usable than long and narrow rectangles. We thus introduce and study the problem of fair two-dimensional division wherein the allotted pieces must be of some restricted two-dimensional geometric shape(s), particularly squares and fat rectangles. Adding such geometric constraints re-opens most questions and challenges related to cake-cutting. Indeed, even the most elementary fairness criterion --- proportionality --- can no longer be guaranteed. In this paper we thus examine the level of proportionality that can be guaranteed, providing both impossibility results and constructive division procedures., Comment: Journal version

We consider the problem of fairly dividing a two dimensional heterogeneous good among multiple players. Applications include division of land as well as ad space in print and electronic media. Classical cake cutting protocols primarily consider a one-dimensional resource, or allocate each player multiple infinitesimally small "pieces". In practice, however, the two dimensional \emph{shape} of the allotted piece is of crucial importance in many applications (e.g. squares or bounded aspect-ratio rectangles are most useful for building houses, as well as advertisements). We thus introduce and study the problem of fair two-dimensional division wherein the allotted plots must be of some restricted two-dimensional geometric shape(s). Adding this geometric constraint re-opens most questions and challenges related to cake-cutting. Indeed, even the elementary \emph{proportionality} fairness criteria can no longer be guaranteed in all cases. In this paper we thus examine the \emph{level} of proportionality that \emph{can} be guaranteed, providing both impossibility results (for proportionality that cannot be guaranteed), and algorithmic constructions (for proportionality that can be guaranteed). We focus primarily on the case when the cake is a rectilinear polygon and the allotted plots must be squares or bounded aspect-ratio rectangles., Comment: Superseded by arXiv:1510.03170