Fair Public Decision Making

Authors

Vincent Conitzer, Rupert Freeman, Nisarg Shah

Type: Article

Publication Date: 2017-06-20

Citations: 125

DOI: https://doi.org/10.1145/3033274.3085125

Ask PDF

Abstract

We generalize the classic problem of fairly allocating indivisible goods to the problem of fair public decision making, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide positive utility to multiple players. We extend the popular fairness notion of proportionality (which is not guaranteeable) to our more general setting, and introduce three novel relaxations --- proportionality up to one issue, round robin share, and pessimistic proportional share --- that are also interesting in the classic goods allocation setting. We show that the Maximum Nash Welfare solution, which is known to satisfy appealing fairness properties in the classic setting, satisfies or approximates all three relaxations in our framework. We also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without insisting on Pareto optimality.

Locations

arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

None

2025-04-30

Alfin Luluk Kamalia , Nina Queena Hadi Putri

None

2025-05-13

None

2022-06-15

None

2025-05-13

None

2025-04-30

None

2025-05-20

None

2025-04-30

None

2024-06-01

None

2025-05-21

None

2025-02-28

None

2022-12-03

None

2025-05-20

None

2025-05-01

None

2025-05-13

None

2014-07-02

None

2025-05-16

None

2025-05-15

None

2024-08-12

None

2023-06-27

None

2011-08-01

Multi-Winner Voting with Approval Preferences

2022-11-17

Martin Lackner , Piotr Skowron

Multi-winner voting is the process of selecting a fixed-size set of representative candidates based on voters' preferences. It occurs in applications ranging from politics (parliamentary elections) to the design of … Multi-winner voting is the process of selecting a fixed-size set of representative candidates based on voters' preferences. It occurs in applications ranging from politics (parliamentary elections) to the design of modern computer applications (collaborative filtering, dynamic Q&A platforms, diversifying search results). All these applications share the problem of identifying a representative subset of alternatives -- and the study of multi-winner voting is the principled analysis of this task. This book provides a thorough and in-depth look at multi-winner voting based on approval preferences. One speaks of approval preferences if voters express their preferences by providing a set of candidates they approve. Approval preferences thus separate candidates in approved and disapproved ones, a simple, binary classification. The corresponding multi-winner voting rules are called approval-based committee (ABC) rules. Due to the simplicity of approval preferences, ABC rules are widely suitable for practical use. Recent years have seen a rising interest in ABC voting. While multi-winner voting has been originally a topic studied by economists and political scientists, a significant share of recent progress has occurred in the field of computational social choice. This discipline is situated in the intersection of artificial intelligence, computer science, economics, and (to a lesser degree) political science, combining insights and methods from these distinct fields. The goal of this book is to present fundamental concepts and results for ABC voting and to discuss the recent advances in computational social choice. The main focus is on axiomatic analysis, algorithmic results, and relevant applications.

View PDF Chat

On Best-of-Both-Worlds Fair-Share Allocations

2022-01-01

Moshe Babaioff , Tomer Ezra , Uriel Feige

View PDF Chat

Picking Sequences and Monotonicity in Weighted Fair Division

2021-08-01

Mithun Chakraborty , Ulrike Schmidt-Kraepelin , Warut Suksompong

We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our … We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems.

View PDF Chat

Markets for public decision-making

2020-11-18

Nikhil Garg , Ashish Goel , Benjamin Plaut

View PDF Chat

Computing Welfare-Maximizing Fair Allocations of Indivisible Goods

2020-01-01

Haris Aziz , Xin Huang , Nicholas Mattei +1 more

We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable … We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx).

View PDF Chat

On the Proximity of Markets with Integral Equilibria

2019-07-17

Siddharth Barman , Sanath Kumar Krishnamurthy

We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with … We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with additive valuations (Eisenberg and Gale 1959; Orlin 2010), such equilibria, in general, assign goods fractionally to agents. Hence, Fisher markets are not directly applicable in the context of indivisible goods. In this work we show that one can always bypass this hurdle and, up to a bounded change in agents’ budgets, obtain markets that admit an integral equilibrium. We refer to such markets as pure markets and show that, for any given Fisher market (with additive valuations), one can efficiently compute a “near-by,” pure market with an accompanying integral equilibrium.Our work on pure markets leads to novel algorithmic results for fair division of indivisible goods. Prior work in discrete fair division has shown that, under additive valuations, there always exist allocations that simultaneously achieve the seemingly incompatible properties of fairness and efficiency (Caragiannis et al. 2016); here fairness refers to envyfreeness up to one good (EF1) and efficiency corresponds to Pareto efficiency. However, polynomial-time algorithms are not known for finding such allocations. Considering relaxations of proportionality and EF1, respectively, as our notions of fairness, we show that fair and Pareto efficient allocations can be computed in strongly polynomial time.

View PDF Chat

Funding Public Projects: A Case for the Nash Product Rule

2020-05-16

Florian Brandl , Felix Brandt , Dominik Peters +2 more

We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for … We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for participatory budgeting without an exogenously available budget, as well as donor coordination when interpreting charities as public projects and donations as contributions. Our aim is to identify a mutually beneficial distribution of the individual contributions. In the preference aggregation problem that we study, agents report linear utility functions over projects together with the amount of their contributions, and the mechanism determines a socially optimal distribution of the money. We identify a specific mechanism---the Nash product rule---which picks the distribution that maximizes the product of the agents' utilities. This rule is Pareto efficient, and we prove that it satisfies attractive incentive properties: the Nash rule spends an agent's contribution only on projects the agent finds acceptable, and it provides strong participation incentives. We also discuss issues of strategyproofness and monotonicity.

Algorithms for Competitive Division of Chores

2019-07-03

Simina Brânzei , Fedor Sandomirskiy

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best … We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash Social Welfare on the Pareto frontier of the set of feasible utilities. The rule becomes multivalued and none of the standard methods can be applied to compute its outcome. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in Devanur et al (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).

Sub-committee Approval Voting and Generalised Justified Representation Axioms

2017-01-01

Haris Aziz , Barton E. Lee

Social choice is replete with various settings including single-winner voting, multi-winner voting, probabilistic voting, multiple referenda, and public decision making. We study a general model of social choice called Sub-Committee … Social choice is replete with various settings including single-winner voting, multi-winner voting, probabilistic voting, multiple referenda, and public decision making. We study a general model of social choice called Sub-Committee Voting (SCV) that simultaneously generalizes these settings. We then focus on sub-committee voting with approvals and propose extensions of the justified representation axioms that have been considered for proportional representation in approval-based committee voting. We study the properties and relations of these axioms. For each of the axioms, we analyse whether a representative committee exists and also examine the complexity of computing and verifying such a committee.

Cluster Attack: Query-based Adversarial Attacks on Graph with Graph-Dependent Priors

2022-07-01

Zhengyi Wang , Zhongkai Hao , Ziqiao Wang +2 more

While deep neural networks have achieved great success in graph analysis, recent work has shown that they are vulnerable to adversarial attacks. Compared with adversarial attacks on image classification, performing … While deep neural networks have achieved great success in graph analysis, recent work has shown that they are vulnerable to adversarial attacks. Compared with adversarial attacks on image classification, performing adversarial attacks on graphs is more challenging because of the discrete and non-differential nature of the adjacent matrix for a graph. In this work, we propose Cluster Attack --- a Graph Injection Attack (GIA) on node classification, which injects fake nodes into the original graph to degenerate the performance of graph neural networks (GNNs) on certain victim nodes while affecting the other nodes as little as possible. We demonstrate that a GIA problem can be equivalently formulated as a graph clustering problem; thus, the discrete optimization problem of the adjacency matrix can be solved in the context of graph clustering. In particular, we propose to measure the similarity between victim nodes by a metric of Adversarial Vulnerability, which is related to how the victim nodes will be affected by the injected fake node, and to cluster the victim nodes accordingly. Our attack is performed in a practical and unnoticeable query-based black-box manner with only a few nodes on the graphs that can be accessed. Theoretical analysis and extensive experiments demonstrate the effectiveness of our method by fooling the node classifiers with only a small number of queries.

View PDF Chat

Approval-Based Committee Voting: Axioms, Algorithms, and Applications.

2020-07-03

Martin Lackner , Piotr Skowron

Approval-based committee (ABC) rules are voting rules that output a fixed-size subset of candidates, a so-called committee. ABC rules select committees based on dichotomous preferences, i.e., a voter either approves … Approval-based committee (ABC) rules are voting rules that output a fixed-size subset of candidates, a so-called committee. ABC rules select committees based on dichotomous preferences, i.e., a voter either approves or disapproves a candidate. This simple type of preferences makes ABC rules widely suitable for practical use. In this survey, we summarize the current understanding of ABC rules from the viewpoint of computational social choice. The main focus is on axiomatic analysis, algorithmic results, and relevant applications.

Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule

2023-06-26

Bo Li , Xiaowei Wu , Chenyang Xu +1 more

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 … 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 problem to submodular objective functions and Matroid rank constraints.

View PDF Chat

Electing the Executive Branch

2020-01-01

Ehud Shapiro , Nimrod Talmon

The executive branch, or government, is typically not elected directly by the people, but rather formed by another elected body or person such as the parliament or the president. As … The executive branch, or government, is typically not elected directly by the people, but rather formed by another elected body or person such as the parliament or the president. As a result, its members are not directly accountable to the people, individually or as a group. We consider a scenario in which the members of the government are elected directly by the people, and wish to achieve proportionality while doing so. We propose a formal model consisting of $k$ offices, each with its own disjoint set of candidates, and a set of voters who provide approval ballots for all offices. We wish to identify good aggregation rules that assign one candidate to each office. As using a simple majority vote for each office independently might result in disregarding minority preferences altogether, here we consider an adaptation of the greedy variant of Proportional Approval Voting (GreedyPAV) to our setting, and demonstrate -- through computer-based simulations -- how voting for all offices together using this rule overcomes this weakness. We note that the approach is applicable also to a party that employs direct democracy, where party members elect the party's representatives in a coalition government.

View PDF Chat

Approximate Group Fairness for Clustering

2022-01-01

Bo Li , Lijun Li , Ankang Sun +2 more

We incorporate group fairness into the algorithmic centroid clustering problem, where $k$ centers are to be located to serve $n$ agents distributed in a metric space. We refine the notion … We incorporate group fairness into the algorithmic centroid clustering problem, where $k$ centers are to be located to serve $n$ agents distributed in a metric space. We refine the notion of proportional fairness proposed in [Chen et al., ICML 2019] as {\em core fairness}, and $k$-clustering is in the core if no coalition containing at least $n/k$ agents can strictly decrease their total distance by deviating to a new center together. Our solution concept is motivated by the situation where agents are able to coordinate and utilities are transferable. A string of existence, hardness and approximability results is provided. Particularly, we propose two dimensions to relax core requirements: one is on the degree of distance improvement, and the other is on the size of deviating coalition. For both relaxations and their combination, we study the extent to which relaxed core fairness can be satisfied in metric spaces including line, tree and general metric space, and design approximation algorithms accordingly.

View PDF Chat

Monotonicity and competitive equilibrium in cake-cutting

2018-05-26

Erel Segal-Halevi , Balázs R. Sziklai

View PDF Chat

The maximin support method: an extension of the D’Hondt method to approval-based multiwinner elections

2022-04-29

Luis Sánchez Fernández , Norberto Fernández , Jesús Arias Fisteus +1 more

Abstract We propose the maximin support method, a novel extension of the D’Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to … Abstract We propose the maximin support method, a novel extension of the D’Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the voter support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D’Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relationship between the maximin support method and alternative D’Hondt extensions due to Phragmén.

View PDF Chat

A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

2020-07-09

Haris Aziz , Hervé Moulin , Fedor Sandomirskiy

View PDF Chat

Democratic fair allocation of indivisible goods

2019-09-03

Erel Segal-Halevi , Warut Suksompong

View PDF Chat

Nash Welfare Guarantees for Fair and Efficient Coverage

2022-01-01

Siddharth Barman , Anand Krishna , Y. Narahari +1 more

View PDF Chat

Picking sequences and monotonicity in weighted fair division

2021-08-13

Mithun Chakraborty , Ulrike Schmidt-Kraepelin , Warut Suksompong

View PDF Chat

The Power of Signaling and Its Intrinsic Connection to the Price of Anarchy

2022-01-01

Jamie Nachbar , Haifeng Xu

View PDF Chat

Unified Fair Allocation of Goods and Chores via Copies

2023-09-22

Yotam Gafni , Xin Huang , Ron Lavi +1 more

We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts … We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts for goods with copies; (2) the existence of EFX and other solution concepts for chores. We establish a tight relation between these issues via two conceptual contributions: First, a refinement of envy-based fairness notions that we term envy without commons (denoted EFX WC when applied to EFX). Second, a formal duality theorem relating the existence of a host of (refined) fair allocation concepts for copies to their existence for chores. We demonstrate the usefulness of our duality result by using it to characterize the existence of EFX for chores through the dual environment, as well as to prove EFX existence in the special case of leveled preferences over the chores. We further study the hierarchy among envy-freeness notions without commons and their α-MMS guarantees, showing, for example, that any EFX WC allocation guarantees at least $\frac{4}{11}$ -MMS for goods with copies.

View PDF Chat

Playing Divide-and-Choose Given Uncertain Preferences

2022-01-01

Jamie Tucker-Foltz , Richard Zeckhauser

We study the classic divide-and-choose method for equitably allocating divisible goods between two players who are rational, self-interested Bayesian agents. The players have additive private values drawn from common priors. … We study the classic divide-and-choose method for equitably allocating divisible goods between two players who are rational, self-interested Bayesian agents. The players have additive private values drawn from common priors. We characterize the structure of optimal divisions in the divide-and-choose game and show how to efficiently compute equilibria. We identify several striking differences between optimal strategies in the cases of known versus unknown preferences. Most notably, the divider has a compelling "diversification" incentive which leads to multiple goods being divided at equilibrium. We show that the relative utilities of the two players depend on their uncertainties about each other's values and the number of goods. We prove that, when values are independently and identically distributed across players and goods, the chooser is strictly better off for a small number of goods, while the divider is strictly better off for a large number of goods.

View PDF Chat

Fair and Efficient Allocations under Subadditive Valuations

2021-05-18

Bhaskar Ray Chaudhury , Jugal Garg , Ruta Mehta

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the … We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely 1/2-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p in (-\infty, 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = -\infty while also retaining the remarkable fairness properties.

View PDF Chat

Approximately Envy-Free Budget-Feasible Allocation

2021-01-01

Jiarui Gan , Bo Li , Xiaowei Wu

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 … 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.

Fair allocation of combinations of indivisible goods and chores

2018-01-01

Haris Aziz , Ioannis Caragiannis , Ayumi Igarashi

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

The Price of Connectivity in Fair Division

2021-05-18

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu +1 more

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected … We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

View PDF Chat

Beyond identical utilities: buyer utility functions and fair allocations.

2021-09-17

Franklin Camacho , Rigoberto Fonseca-Delgado , Ramón Pino Pérez +1 more

The problem of finding envy-free allocations of indivisible goods can not always be solved; therefore, it is common to study some relaxations such as envy-free up to one good (EF1). … The problem of finding envy-free allocations of indivisible goods can not always be solved; therefore, it is common to study some relaxations such as envy-free up to one good (EF1). Another property of interest for efficiency of an allocation is the Pareto Optimality (PO). Under additive utility functions, it is possible to find allocations EF1 and PO using Nash social welfare. However, to find an allocation that maximizes the Nash social welfare is a computationally hard problem. In this work we propose a polynomial time algorithm which maximizes the utilitarian social welfare and at the same time produces an allocation which is EF1 and PO in a special case of additive utility functions called buyer utility functions. Moreover, a slight modification of our algorithm produces an allocation which is envy-free up to any positively valued good (EFX).

Fair and Efficient Allocations with Limited Demands

2021-05-18

Sushirdeep Narayana , Ian A. Kash

We study the fair division problem of allocating multiple resources among a set of agents with Leontief preferences that are each required to complete a finite amount of work, which … We study the fair division problem of allocating multiple resources among a set of agents with Leontief preferences that are each required to complete a finite amount of work, which we term "limited demands". We examine the behavior of the classic Dominant Resource Fairness (DRF) mechanism in this setting and show it is fair but only weakly Pareto optimal and inefficient in many natural examples. We propose as an alternative the Least Cost Product (LCP) mechanism, a natural adaptation of Maximum Nash Welfare to this setting. We characterize the structure of allocation of the LCP mechanism in this setting, show that it is Pareto efficient, and that it satisfies the relatively weak fairness property of sharing incentives. While we prove that it satisfies the stronger fairness property of (expected) envy freeness in some special cases, we provide a counterexample showing it does not do so in general, a striking contrast to the "unreasonable fairness" of Maximum Nash Welfare in other settings. Simulations suggest, however, that these violations of envy freeness are rare in randomly generated examples.

View PDF Chat

Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free

2020-01-01

Xiaowei Wu , Bo Li , Jiarui Gan

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has … The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.

Computing welfare-Maximizing fair allocations of indivisible goods

2022-10-13

Haris Aziz , Xin Huang , Nicholas Mattei +1 more

View PDF Chat

Achieving Proportionality up to the Maximin Item with Indivisible Goods

2021-05-18

Artem Baklanov , Pranav Garimidi , Vasilis Gkatzelis +1 more

We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial … We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.

View PDF Chat

Markets for Public Decision-making

2018-07-27

Nikhil Garg , Ashish Goel , Benjamin Plaut

A public decision-making problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each issue. We … A public decision-making problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each issue. We study adaptations of market economies to this setting, focusing on binary issues. Issues have prices, and each agent is endowed with artificial currency that she can use to purchase probability for her preferred alternatives (we allow randomized outcomes). We first show that when each issue has a single price that is common to all agents, market equilibria can be arbitrarily bad. This negative result motivates a different approach. We present a novel technique called issue expansion, which transforms any public decision-making instance into an equivalent Fisher market, the simplest type of private goods market. This is done by expanding each issue into many goods: one for each pair of agents who disagree on that issue. We show that the prices in the constructed Fisher market yield a pricing equilibrium in the original public decision-making problem which maximizes Nash welfare. More broadly, pairwise issue expansion uncovers a powerful connection between the public decision-making and private goods settings; this immediately yields several interesting results about public decisions markets, and furthers the hope that we will be able to find a simple iterative voting protocol that leads to near-optimum decisions.

Developments in Multi-Agent Fair Allocation

2020-04-03

Haris Aziz

Fairness is becoming an increasingly important concern when designing markets, allocation procedures, and computer systems. I survey some recent developments in the field of multi-agent fair allocation. Fairness is becoming an increasingly important concern when designing markets, allocation procedures, and computer systems. I survey some recent developments in the field of multi-agent fair allocation.

View PDF Chat

Fair Division: The Computer Scientist's Perspective

2020-05-11

Toby Walsh

I survey recent progress on a classic and challenging problem in social choice: the fair division of indivisible items. I discuss how a computational perspective has provided interesting insights into … I survey recent progress on a classic and challenging problem in social choice: the fair division of indivisible items. I discuss how a computational perspective has provided interesting insights into and understanding of how to divide items fairly and efficiently. This has involved bringing to bear tools such as those used in knowledge representation, computational complexity, approximation methods, game theory, online analysis and communication complexity

Participatory Budgeting: Models and Approaches

2020-08-10

Haris Aziz , Nisarg Shah

View PDF Chat

Mixed Fair Division: A Survey

2023-01-01

Shengxin Liu , Xinhang Lu , Mashbat Suzuki +1 more

Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has … Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions and future directions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (mixed goods), and (iii) indivisible goods with subsidy which can be viewed like a divisible good.

View PDF Chat

Almost (Weighted) Proportional Allocations for Indivisible Chores✱✱

2022-04-25

Bo Li , Yingkai Li , Xiaowei Wu

In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of … In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents' ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.

View PDF Chat

Greedy Algorithms for Fair Division of Mixed Manna.

2019-11-25

Martin Aleksandrov , Toby Walsh

We consider a multi-agent model for fair division of mixed manna (i.e. items for which agents can have positive, zero or negative utilities), in which agents have additive utilities for … We consider a multi-agent model for fair division of mixed manna (i.e. items for which agents can have positive, zero or negative utilities), in which agents have additive utilities for bundles of items. For this model, we give several general impossibility results and special possibility results for three common fairness concepts (i.e. EF1, EFX, EFX3) and one popular efficiency concept (i.e. PO). We also study how these interact with common welfare objectives such as the Nash, disutility Nash and egalitarian welfares. For example, we show that maximizing the Nash welfare with mixed manna (or minimizing the disutility Nash welfare) does not ensure an EF1 allocation whereas with goods and the Nash welfare it does. We also prove that an EFX3 allocation may not exist even with identical utilities. By comparison, with tertiary utilities, EFX and PO allocations, or EFX3 and PO allocations always exist. Also, with identical utilities, EFX and PO allocations always exist. For these cases, we give polynomial-time algorithms, returning such allocations and approximating further the Nash, disutility Nash and egalitarian welfares in special cases.

Price of Fairness in Budget Division for Egalitarian Social Welfare

2020-01-01

Zhongzheng Tang , Chenhao Wang , Mengqi Zhang

View PDF Chat

Justified representation in approval-based committee voting

2017-01-09

Haris Aziz , Markus Brill , Vincent Conitzer +3 more

View PDF Chat

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

2015-07-05

Euiwoong Lee

We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem … We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.

The Core of the Participatory Budgeting Problem

2016-01-01

Brandon Fain , Ashish Goel , Kamesh Munagala

View PDF Chat