SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Justified representation in approval-based committee voting

2017-01-09
Haris Aziz , Markus Brill , Vincent Conitzer +3 more
View PDF Chat

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

2016-10-01
Haris Aziz , Simon Mackenzie
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer … We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nnnnnn. Even if we do not run our protocol to completion, it can find in at most n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n+1</sup> queries an envy-free partial allocation of the cake in which each agent gets at least 1/n of the value of the whole cake.
View PDF Chat

Fair assignment of indivisible objects under ordinal preferences

2015-06-18
Haris Aziz , Serge Gaspers , Simon Mackenzie +1 more
View PDF Chat

Computing desirable partitions in additively separable hedonic games

2012-09-23
Haris Aziz , Felix Brandt , Hans Georg Seedig
View PDF Chat

Participatory Budgeting: Models and Approaches

2020-08-10
Haris Aziz , Nisarg Shah
View PDF Chat

The computational complexity of random serial dictatorship

2013-09-14
Haris Aziz , Felix Brandt , Markus Brill
View PDF Chat

A discrete and bounded envy-free cake cutting protocol for four agents

2016-06-10
Haris Aziz , Simon Mackenzie
We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has … We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem to obtain a bounded envy-free protocol for more than three agents. The problem has been termed the central open problem in cake cutting. We solve this problem by proposing a discrete and bounded envy-free protocol for four agents.
View PDF Chat

Online Fair Division: analysing a Food Bank problem

2015-02-26
Martin Aleksandrov , Haris Aziz , Serge Gaspers +1 more
We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply … We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply declare what items they like. We analyse several axiomatic properties of these mechanisms like strategy-proofness and envy-freeness. Finally, we perform a competitive analysis and compute the price of anarchy.

Fractional Hedonic Games

2019-05-31
Haris Aziz , Florian Brandl , Felix Brandt +3 more
The work we present in this article initiated the formal study of fractional hedonic games (FHGs), coalition formation games in which the utility of a player is the average value … The work we present in this article initiated the formal study of fractional hedonic games (FHGs), coalition formation games in which the utility of a player is the average value he ascribes to the members of his coalition. Among other settings, this covers situations in which players only distinguish between friends and non-friends and desire to be in a coalition in which the fraction of friends is maximal. FHGs thus not only constitute a natural class of succinctly representable coalition formation games but also provide an interesting framework for network clustering. We propose a number of conditions under which the core of FHGs is non-empty and provide algorithms for computing a core stable outcome. By contrast, we show that the core may be empty in other cases, and that it is computationally hard in general to decide non-emptiness of the core.
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

Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations

2014-01-01
Haris Aziz , Chun Ye
View PDF Chat

Proportionally Representative Participatory Budgeting: Axioms and Algorithms

2018-07-09
Haris Aziz , Barton E. Lee , Nimrod Talmon
Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axioms in participatory budgeting, by generalizing relevant axioms for … Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axioms in participatory budgeting, by generalizing relevant axioms for approval-based multi-winner elections. We observe a rich landscape with respect to the computational complexity of identifying proportional budgets and computing such, and present budgeting methods that satisfy these axioms by identifying budgets that are representative to the demands of vast segments of the voters.

False-Name Manipulations in Weighted Voting Games

2011-01-20
Haris Aziz , Yoram Bachrach , Edith Elkind +1 more
Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if … Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A players power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.
View PDF Chat

Fair division of indivisible goods: Recent progress and open questions

2023-06-16
Georgios Amanatidis , Haris Aziz , Georgios Birmpas +5 more
Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources … Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.
View PDF Chat

Complexity of coalition structure generation

2011-05-02
Haris Aziz , Bart de Keijzer
We revisit the coalition structure generation problem in which the goal is to partition the players into exhaustive and disjoint coalitions so as to maximize the social welfare. One of … We revisit the coalition structure generation problem in which the goal is to partition the players into exhaustive and disjoint coalitions so as to maximize the social welfare. One of our key results is a general polynomial-time algorithm to solve the problem for all coalitional games provided that player types are known and the number of player types is bounded by a constant. As a corollary, we obtain a polynomial-time algorithm to compute an optimal partition for weighted voting games with a constant number of weight values and for coalitional skill games with a constant number of skills. We also consider well-studied and well-motivated coalitional games defined compactly on combinatorial domains. For these games, we characterize the complexity of computing an optimal coalition structure by presenting polynomial-time algorithms, approximation algorithms, or NP-hardness and inapproximability lower bounds.

Strategyproof peer selection using randomization, partitioning, and apportionment

2019-06-18
Haris Aziz , Omer Lev , Nicholas Mattei +2 more
View PDF Chat

Stable Matching with Uncertain Linear Preferences

2019-11-14
Haris Aziz , Péter Bíró , Serge Gaspers +3 more
Abstract We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: … Abstract We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model—there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.
View PDF Chat

Possible and Necessary Allocations via Sequential Mechanisms

2014-01-01
Haris Aziz , Toby Walsh , Lirong Xia
A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of … A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for five natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternating, strictly alternating and all policies. We identify characterizations of allocations produced balanced, recursively balanced, balanced alternating policies and strictly alternating policies respectively, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.
View PDF Chat

Weighted Maxmin Fair Share Allocation of Indivisible Chores

2019-07-28
Haris Aziz , Hau Chan , Bo Li
We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and … We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for allocation of goods to asymmetric agents, and even for chores to symmetric agents do not provide good approximations for allocation of chores to asymmetric agents under WMMS. As a consequence, we present a novel polynomial-time constant-approximation algorithm, via linear program, for OWMMS. For two special cases: the binary valuation case and the 2-agent case, we provide exact or better constant-approximation algorithms.
View PDF Chat

The expanding approvals rule: improving proportional representation and monotonicity

2019-08-09
Haris Aziz , Barton E. Lee
View PDF Chat

The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality

2017-07-28
Haris Aziz , Edith Elkind , Piotr Faliszewski +2 more
We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second … We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.
View PDF Chat

Efficient reallocation under additive and responsive preferences

2019-05-30
Haris Aziz , Péter Bíró , Jérôme Lang +2 more
View PDF Chat

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.

Online fair division: analysing a food bank problem

2015-07-25
Martin Aleksandrov , Haris Aziz , Serge Gaspers +1 more
We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply … We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply declare what items they like. We analyse axiomatic properties of these mechanisms such as strategy-proofness and envy freeness. Finally, we perform a competitive analysis and compute the price of anarchy.

From Matching with Diversity Constraints to Matching with Regional Quotas

2020-01-01
Haris Aziz , Serge Gaspers , Zhaohong Sun +1 more
In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with … In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.

Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives

2020-04-03
Haris Aziz , Hau Chan , Barton E. Lee +2 more
We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic … We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, we prove that the corresponding optimization problem, where the goal is to locate facilities to minimize either the total cost to all agents or the maximum cost of any agent is NP-hard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilities have identical capacities. We then consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that several natural mechanisms studied in the uncapacitated setting either lose strategyproofness or a bound on the solution quality %on the returned solution for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.
View PDF Chat

Almost Group Envy-free Allocation of Indivisible Goods and Chores

2020-07-01
Haris Aziz , Simon Rey
We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established … We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of indivisible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We also prove that checking whether a given allocation satisfies GEF1 is coNP-complete when there are either only goods, only chores or both.
View PDF Chat

A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents

2016-04-13
Haris Aziz , Simon Mackenzie
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from $n$ agents. The problem has received attention in computer … We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from $n$ agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is $n^{n^{n^{n^{n^n}}}}$. We additionally show that even if we do not run our protocol to completion, it can find in at most $n^3{(n^2)}^n$ queries a partial allocation of the cake that achieves proportionality (each agent gets at least $1/n$ of the value of the whole cake) and envy-freeness. Finally we show that an envy-free partial allocation can be computed in at most $n^3{(n^2)}^n$ queries such that each agent gets a connected piece that gives the agent at least $1/(3n)$ of the value of the whole cake.

Manipulating the Probabilistic Serial Rule

2015-05-04
Haris Aziz , Serge Gaspers , Simon Mackenzie +3 more
The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its desirable fairness and welfare properties. However, PS is … The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its desirable fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We initiate the study of the computational complexity of an agent manipulating the PS rule. We show that computing an expected utility better response is NP-hard. On the other hand, we present a polynomial-time algorithm to compute a lexicographic best response. For the case of two agents, we show that even an expected utility best response can be computed in polynomial time. Our result for the case of two agents relies on an interesting connection with sequential allocation of discrete objects.

Stable Matching with Uncertain Linear Preferences

2016-01-01
Haris Aziz , Péter Bíró , Serge Gaspers +3 more
View PDF Chat

A Rule for Committee Selection with Soft Diversity Constraints

2019-09-05
Haris Aziz
View PDF Chat

The capacity constrained facility location problem

2020-10-02
Haris Aziz , Hau Chan , Barton E. Lee +1 more
View PDF Chat

Fair mixing: the case of dichotomous preferences

2017-01-01
Haris Aziz , Anna Bogomolnaia , Hervé Moulin
Agents vote to choose a fair mixture of public outcomes; each agent likes or dislikes each outcome. We discuss three outstanding voting rules. The Conditional Utilitarian rule, a variant of … Agents vote to choose a fair mixture of public outcomes; each agent likes or dislikes each outcome. We discuss three outstanding voting rules. The Conditional Utilitarian rule, a variant of the random dictator, is Strategyproof and guarantees to any group of like-minded agents an influence proportional to its size. It is easier to compute and more efficient than the familiar Random Priority rule. Its worst case (resp. average) inefficiency is provably (resp. in numerical experiments) low if the number of agents is low. The efficient Egalitarian rule protects similarly individual agents but not coalitions. It is Excludable Strategyproof: I do not want to lie if I cannot consume outcomes I claim to dislike. The efficient Nash Max Product rule offers the strongest welfare guarantees to coalitions, who can force any outcome with a probability proportional to their size. But it fails even the excludable form of Strategyproofness.

Random matching under priorities: stability and no envy concepts

2019-04-03
Haris Aziz , Bettina Klaus
View PDF Chat

Justified Representation in Approval-Based Committee Voting

2015-02-16
Haris Aziz , Markus Brill , Vincent Conitzer +3 more
We consider approval-based committee voting, i.e., the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). … We consider approval-based committee voting, i.e., the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agree- ment by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.
View PDF Chat

Justifications of welfare guarantees under normalized utilities

2020-01-28
Haris Aziz
It is standard in computational social choice to analyse welfare considerations under the assumptions of normalized utilities. In this note, we summarize some common reasons for this approach. We then … It is standard in computational social choice to analyse welfare considerations under the assumptions of normalized utilities. In this note, we summarize some common reasons for this approach. We then mention another justification which is ignored but has solid normative appeal. The central concept used in the `new' justification can also be used more widely as a social objective.
View PDF Chat

Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation

2023-01-30
Haris Aziz , Rupert Freeman , Nisarg Shah +1 more
Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of … Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of fairness such as EV, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as EV up to one good can be guaranteed. In “Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation,” H. Aziz, R. Freeman, N. Shah, and R. Vaish ask whether it is possible to achieve both types of guarantees simultaneously. More specifically, they ask whether there exists a probability distribution over deterministic allocations such that every deterministic allocation is envy-free up to one good and the distribution is exactly envy-free in expectation. The main result of the paper answers this question in the affirmative, showing that ex ante and ex post fairness need not be in conflict.
View PDF Chat

A Study of Proxies for Shapley Allocations of Transport Costs

2016-08-06
Haris Aziz , Casey Cahan , Charles Gretton +3 more
We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle … We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.
View PDF Chat

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

Complexity of comparison of influence of players in simple games

2008-01-01
Haris Aziz
Coalitional voting games appear in different forms in multi-agent systems, social choice and threshold logic. In this paper, the complexity of comparison of influence between players in coalitional voting games … Coalitional voting games appear in different forms in multi-agent systems, social choice and threshold logic. In this paper, the complexity of comparison of influence between players in coalitional voting games is characterized. The possible representations of simple games considered are simple games represented by winning coalitions, minimal winning coalitions, weighted voting game or a multiple weighted voting game. The influence of players is gauged from the viewpoint of basic player types, desirability relations and classical power indices such as Shapley-Shubik index, Banzhaf index, Holler index, Deegan-Packel index and Chow parameters. Among other results, it is shown that for a simple game represented by minimal winning coalitions, although it is easy to verify whether a player has zero or one voting power, computing the Banzhaf value of the player is #P-complete. Moreover, it is proved that multiple weighted voting games are the only representations for which it is NP-hard to verify whether the game is linear or not. For a simple game with a set W^m of minimal winning coalitions and n players, a O(n.|W^m|+(n^2)log(n)) algorithm is presented which returns `no' if the game is non-linear and returns the strict desirability ordering otherwise. The complexity of transforming simple games into compact representations is also examined.

The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality

2017-01-27
Haris Aziz , Edith Elkind , Piotr Faliszewski +2 more
We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein: A committee is stable if each committee … We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein: A committee is stable if each committee member is preferred to each non-member by a (possibly weak) majority of voters. The second notion is called local stability (introduced in this paper): A size-$k$ committee is locally stable in an election with $n$ voters if there is no candidate $c$ and no group of more than $\frac{n}{k+1}$ voters such that each voter in this group prefers $c$ to each committee member. We argue that Gehrlein-stable committees are appropriate for shortlisting tasks, and that locally stable committees are better suited for applications that require proportional representation. The goal of this paper is to analyze these notions in detail, explore their compatibility with notions of proportionality, and investigate the computational complexity of related algorithmic tasks.

Complexity of Manipulating Sequential Allocation

2017-02-10
Haris Aziz , Sylvain Bouveret , Jérôme Lang +1 more
Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been … Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.
View PDF Chat

Simultaneously Achieving Ex-ante and Ex-post Fairness

2020-01-01
Haris Aziz
View PDF Chat

Proportionally Representative Participatory Budgeting with Ordinal Preferences

2021-05-18
Haris Aziz , Barton E. Lee
Participatory budgeting (PB) is a democratic paradigm whereby voters decide on a set of projects to fund with a limited budget. We consider PB in a setting where voters report … Participatory budgeting (PB) is a democratic paradigm whereby voters decide on a set of projects to fund with a limited budget. We consider PB in a setting where voters report ordinal preferences over projects and have (possibly) asymmetric weights. We propose proportional representation axioms and clarify how they fit into other preference aggregation settings, such as multi-winner voting and approval-based multi-winner voting. As a result of our study, we also discover a new solution concept for approval-based multi-winner voting, which we call Inclusion PSC (IPSC). IPSC is stronger than proportional justified representation (PJR), incomparable to extended justified representation (EJR), and yet compatible with EJR. The well-studied Proportional Approval Voting (PAV) rule produces a committee that satisfies both EJR and IPSC; however, both these axioms can also be satisfied by an algorithm that runs in polynomial-time.
View PDF Chat

Wiretapping a Hidden Network

2009-01-01
Haris Aziz , Oded Lachish , Mike Paterson +1 more
View PDF Chat

Parametrized algorithms for random serial dictatorship

2014-08-12
Haris Aziz , Julián Mestre
View PDF Chat

Possible and Necessary Allocations via Sequential Mechanisms

2014-12-06
Haris Aziz , Toby Walsh , Lirong Xia
A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of … A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for five natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternating, strictly alternating and all policies. We identify characterizations of allocations produced balanced, recursively balanced, balanced alternating policies and strictly alternating policies respectively, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.

Complexity of coalition structure generation

2011-01-01
Haris Aziz , Bart de Keijzer
We revisit the coalition structure generation problem in which the goal is to partition the players into exhaustive and disjoint coalitions so as to maximize the social welfare. One of … We revisit the coalition structure generation problem in which the goal is to partition the players into exhaustive and disjoint coalitions so as to maximize the social welfare. One of our key results is a general polynomial-time algorithm to solve the problem for all coalitional games provided that player types are known and the number of player types is bounded by a constant. As a corollary, we obtain a polynomial-time algorithm to compute an optimal partition for weighted voting games with a constant number of weight values and for coalitional skill games with a constant number of skills. We also consider well-studied and well-motivated coalitional games defined compactly on combinatorial domains. For these games, we characterize the complexity of computing an optimal coalition structure by presenting polynomial-time algorithms, approximation algorithms, or NP-hardness and inapproximability lower bounds.
View PDF Chat

Strategyproof and Approximately Maxmin Fair Share Allocation of Chores

2019-07-28
Haris Aziz , Bo Li , Xiaowei Wu
We initiate the work on fair and strategyproof allocation of indivisible chores. The fairness concept we consider in this paper is maxmin share (MMS) fairness. We consider three previously studied … We initiate the work on fair and strategyproof allocation of indivisible chores. The fairness concept we consider in this paper is maxmin share (MMS) fairness. We consider three previously studied models of information elicited from the agents: the ordinal model, the cardinal model, and the public ranking model in which the ordinal preferences are publicly known. We present both positive and negative results on the level of MMS approximation that can be guaranteed if we require the algorithm to be strategyproof. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.
View PDF Chat

Efficient, Fair, and Incentive-Compatible Healthcare Rationing

2021-07-18
Haris Aziz , Florian Brandl
During the COVID-19 pandemic, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We … During the COVID-19 pandemic, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We consider a healthcare rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories and the patients have different priorities for the categories. We present an allocation rule that respects the priorities, complies with the eligibility requirements, allocates the largest feasible number of units, and does not incentivize agents to hide that they qualify through a category. Moreover, the rule is polynomial-time computable. To the best of our knowledge, it is the first known rule with the aforementioned properties.
View PDF Chat

Proportionality-based fairness and strategyproofness in the facility location problem

2025-05-01
Haris Aziz , Alexander Lam , Barton E. Lee +1 more

Strategyproof Maximum Matching under Dichotomous Agent Preferences

2025-02-14
Haris Aziz , Md. Shahidul Islam , Szilvia Pápai
We consider a two-sided matching problem in which the agents on one side have dichotomous preferences and the other side representing institutions has strict preferences (priorities). It captures several important … We consider a two-sided matching problem in which the agents on one side have dichotomous preferences and the other side representing institutions has strict preferences (priorities). It captures several important applications in matching market design in which the agents are only interested in getting matched to an acceptable institution. These include centralized daycare assignment and healthcare rationing. We present a compelling new mechanism that satisfies many prominent and desirable properties including individual rationality, maximum size, fairness, Pareto-efficiency on both sides, strategyproofness on both sides, non-bossiness and having polynomial time running time. As a result, we answer an open problem whether there exists a mechanism that is agent-strategyproof, maximum, fair and non-bossy.
View PDF Chat

Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy

2025-02-13
Noga Klein Elmalem , Haris Aziz , Rica Gonen +7 more
We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to … We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to their entitlement at least as favorable as any others relative to their own. Often, achieving WEF necessitates monetary transfers, which can be modeled as third-party subsidies. The goal is to attain WEF with bounded subsidies. Previous work relied on characterizations of unweighted envy-freeness (EF), that fail in the weighted setting. This makes our new setting challenging. We present polynomial-time algorithms that compute WEF allocations with a guaranteed upper bound on total subsidy for monotone valuations and various subclasses thereof. We also present an efficient algorithm to compute a fair allocation of items and money, when the budget is not enough to make the allocation WEF. This algorithm is new even for the unweighted setting.
View PDF Chat

Sequential Payment Rules: Approximately Fair Budget Divisions via Simple Spending Dynamics

2024-12-03
Haris Aziz , Patrick Lederer , Xinhang Lu +2 more
In approval-based budget division, a budget needs to be distributed to some candidates based on the voters' approval ballots over these candidates. In the pursuit of simple, well-behaved, and approximately … In approval-based budget division, a budget needs to be distributed to some candidates based on the voters' approval ballots over these candidates. In the pursuit of simple, well-behaved, and approximately fair rules for this setting, we introduce the class of sequential payment rules, where each voter controls a part of the budget and repeatedly spends his share on his approved candidates to determine the final distribution. We show that all sequential payment rules satisfy a demanding population consistency notion and we identify two particularly appealing rules within this class called the maximum payment rule (MP) and the $\frac{1}{3}$-multiplicative sequential payment rule ($\frac{1}{3}$-MP). More specifically, we prove that (i) MP is, apart from one other rule, the only monotonic sequential payment rule and gives a $2$-approximation to a fairness notion called average fair share, and (ii) $\frac{1}{3}$-MP gives a $\frac{3}{2}$-approximation to average fair share, which is optimal among sequential payment rules.
View PDF Chat

Group Fairness in Peer Review

2024-10-04
Haris Aziz , Evi Micha , Nisarg Shah
Large conferences such as NeurIPS and AAAI serve as crossroads of various AI fields, since they attract submissions from a vast number of communities. However, in some cases, this has … Large conferences such as NeurIPS and AAAI serve as crossroads of various AI fields, since they attract submissions from a vast number of communities. However, in some cases, this has resulted in a poor reviewing experience for some communities, whose submissions get assigned to less qualified reviewers outside of their communities. An often-advocated solution is to break up any such large conference into smaller conferences, but this can lead to isolation of communities and harm interdisciplinary research. We tackle this challenge by introducing a notion of group fairness, called the core, which requires that every possible community (subset of researchers) to be treated in a way that prevents them from unilaterally benefiting by withdrawing from a large conference. We study a simple peer review model, prove that it always admits a reviewing assignment in the core, and design an efficient algorithm to find one such assignment. We use real data from CVPR and ICLR conferences to compare our algorithm to existing reviewing assignment algorithms on a number of metrics.
View PDF Chat

Weighted Envy-free Allocation with Subsidy

2024-08-16
Haris Aziz , Xin Huang , Kei Kimura +3 more
We consider the problem of fair allocation with subsidy when agents have weighted entitlements. After highlighting several important differences from the unweighted cases, we present several results concerning weighted envy-freeability … We consider the problem of fair allocation with subsidy when agents have weighted entitlements. After highlighting several important differences from the unweighted cases, we present several results concerning weighted envy-freeability including general characterizations, algorithms for achieving and testing weighted envy-freeability, lower and upper bounds for worst case subsidy for non-wasteful and envy-freeable allocations, and algorithms for achieving weighted envy-freeability along with other properties.
View PDF Chat

Committee Monotonic Proportional Representation: A New Voting Rule and Impossibility Results

2024-06-28
Haris Aziz , Patrick Lederer , Angus Ritossa
We study committee voting rules under ranked preferences, which map the voters' preference relations to a subset of the alternatives of predefined size. In this setting, the compatibility between proportional … We study committee voting rules under ranked preferences, which map the voters' preference relations to a subset of the alternatives of predefined size. In this setting, the compatibility between proportional representation and committee monotonicity is a fundamental open problem that has been mentioned in several works. We design a new multi-winner voting rule called the Solid Coalition Refinement (SCR) Rule that simultaneously satisfies committee monotonicity and Dummett's PSC as well as one of its variants called inclusion PSC. This is the first rule known to satisfy both of these properties. Moreover, we show that this is effectively the best that we can hope for as other fairness notions adapted from approval voting such as Rank-JR and Rank-PJR+ are incompatible with committee monotonicity.
View PDF Chat

Fair Lotteries for Participatory Budgeting

2024-04-08
Haris Aziz , Xinhang Lu , Mashbat Suzuki +2 more
In pursuit of participatory budgeting (PB) outcomes with broader fairness guarantees, we initiate the study of lotteries over discrete PB outcomes. As the projects have heterogeneous costs, the amount spent … In pursuit of participatory budgeting (PB) outcomes with broader fairness guarantees, we initiate the study of lotteries over discrete PB outcomes. As the projects have heterogeneous costs, the amount spent may not be equal ex ante and ex post. To address this, we develop a technique to bound the amount by which the ex-post spend differs from the ex-ante spend -- the property is termed budget balanced up to one project (BB1). With respect to fairness, we take a best-of-both-worlds perspective, seeking outcomes that are both ex-ante and ex-post fair. Towards this goal, we initiate a study of ex-ante fairness properties in PB, including Individual Fair Share (IFS), Unanimous Fair Share (UFS) and their stronger variants, as well as Group Fair Share (GFS). We show several incompatibility results between these ex-ante fairness notions and existing ex-post concepts based on justified representation. One of our main contributions is a randomized algorithm which simultaneously satisfies ex-ante Strong UFS, ex-post full justified representation (FJR) and ex-post BB1 for PB with binary utilities.
View PDF Chat

Envy-Free House Allocation under Uncertain Preferences

2024-03-24
Haris Aziz , Isaiah Iliffe , Bo Li +3 more
Envy-freeness is one of the most important fairness concerns when allocating items. We study envy-free house allocation when agents have uncertain preferences over items and consider several well-studied preference uncertainty … Envy-freeness is one of the most important fairness concerns when allocating items. We study envy-free house allocation when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing an allocation that has the highest probability of being envy-free. We show that each model leads to a distinct set of algorithmic and complexity results, including detailed results on (in-)approximability. En route, we consider two related problems of checking whether there exists an allocation that is possibly or necessarily envy-free. We give a complete picture of the computational complexity of these two problems for all the uncertainty models we consider.
View PDF Chat

Fair Lotteries for Participatory Budgeting

2024-03-24
Haris Aziz , Xinhang Lu , Mashbat Suzuki +2 more
In pursuit of participatory budgeting (PB) outcomes with broader fairness guarantees, we initiate the study of lotteries over discrete PB outcomes. As the projects have heterogeneous costs, the amount spent … In pursuit of participatory budgeting (PB) outcomes with broader fairness guarantees, we initiate the study of lotteries over discrete PB outcomes. As the projects have heterogeneous costs, the amount spent may not be equal ex ante and ex post. To address this, we develop a technique to bound the amount by which the ex-post spend differs from the ex-ante spend---the property is termed budget balanced up to one project (BB1). With respect to fairness, we take a best-of-both-worlds perspective, seeking outcomes that are both ex-ante and ex-post fair. Towards this goal, we initiate a study of ex-ante fairness properties in PB, including Individual Fair Share (IFS), Unanimous Fair Share (UFS) and their stronger variants, as well as Group Fair Share (GFS). We show several incompatibility results between these ex-ante fairness notions and existing ex-post concepts based on justified representation. One of our main contributions is a randomized algorithm which simultaneously satisfies ex-ante Strong UFS, ex-post full justified representation (FJR) and ex-post BB1 for PB with binary utilities.
View PDF Chat

Strategyproof and Proportionally Fair Facility Location

2024-01-01
Haris Aziz , Alexander Lam , Barton E. Lee +1 more
Download This Paper Open PDF in Browser Add Paper to My Library Share: Permalink Using these links will ensure access to this page indefinitely Copy URL Copy DOI Download This Paper Open PDF in Browser Add Paper to My Library Share: Permalink Using these links will ensure access to this page indefinitely Copy URL Copy DOI
View PDF Chat

Fairness Concepts for Indivisible Items with Externalities

2023-06-26
Haris Aziz , Warut Suksompong , Zhaohong Sun +1 more
We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us … We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied properties of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS), which applies to a more general public decision making model. We undertake a detailed study and present algorithms for finding fair allocations.
View PDF Chat

Approval-Based Voting with Mixed Goods

2023-06-26
Xinhang Lu , Jannik Peters , Haris Aziz +2 more
We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting … We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting—GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV)—and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.
View PDF Chat

Fair division of indivisible goods: Recent progress and open questions

2023-06-16
Georgios Amanatidis , Haris Aziz , Georgios Birmpas +5 more
Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources … Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.
View PDF Chat

Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation

2023-01-30
Haris Aziz , Rupert Freeman , Nisarg Shah +1 more
Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of … Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of fairness such as EV, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as EV up to one good can be guaranteed. In “Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation,” H. Aziz, R. Freeman, N. Shah, and R. Vaish ask whether it is possible to achieve both types of guarantees simultaneously. More specifically, they ask whether there exists a probability distribution over deterministic allocations such that every deterministic allocation is envy-free up to one good and the distribution is exactly envy-free in expectation. The main result of the paper answers this question in the affirmative, showing that ex ante and ex post fairness need not be in conflict.
View PDF Chat

Proportional Fairness in Obnoxious Facility Location

2023-01-01
Haris Aziz , Alexander Lam , Bo Li +2 more
We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the … We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, not only are our proportional fairness axioms incompatible with strategyproofness, the Nash equilibria may not guarantee welfare within a constant factor of the optimal welfare. On the other hand, in the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare.
View PDF Chat

Matching Algorithms under Diversity-Based Reservations

2023-01-01
Haris Aziz , Sean Morota Chu , Zhaohong Sun
Selection under category or diversity constraints is a ubiquitous and widely-applicable problem that is encountered in immigration, school choice, hiring, and healthcare rationing. These diversity constraints are typically represented by … Selection under category or diversity constraints is a ubiquitous and widely-applicable problem that is encountered in immigration, school choice, hiring, and healthcare rationing. These diversity constraints are typically represented by minimum and maximum quotas on various categories or types. We undertake a detailed comparative study of applicant selection algorithms with respect to the diversity goals.
View PDF Chat

Best-of-Both-Worlds Fairness in Committee Voting

2023-01-01
Haris Aziz , Xinhang Lu , Mashbat Suzuki +2 more
The best-of-both-worlds paradigm advocates an approach that achieves desirable properties both ex-ante and ex-post. We launch a best-of-both-worlds fairness perspective for the important social choice setting of approval-based committee voting. … The best-of-both-worlds paradigm advocates an approach that achieves desirable properties both ex-ante and ex-post. We launch a best-of-both-worlds fairness perspective for the important social choice setting of approval-based committee voting. To this end, we initiate work on ex-ante proportional representation properties in this domain and formalize a hierarchy of notions including Individual Fair Share (IFS), Unanimous Fair Share (UFS), Group Fair Share (GFS), and their stronger variants. We establish their compatibility with well-studied ex-post concepts such as extended justified representation (EJR) and fully justified representation (FJR). Our first main result is a polynomial-time algorithm that simultaneously satisfies ex-post EJR, ex-ante GFS and ex-ante Strong UFS. Subsequently, we strengthen our ex-post guarantee to FJR and present an algorithm that outputs a lottery which is ex-post FJR and ex-ante Strong UFS, but does not run in polynomial time.

Proportionally Representative Clustering

2023-01-01
Haris Aziz , Barton E. Lee , Sean Morota Chu
In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on clustering -- one of the fundamental tasks in unsupervised … In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on clustering -- one of the fundamental tasks in unsupervised machine learning. We propose a new axiom ``proportional representation fairness'' (PRF) that is designed for clustering problems where the selection of centroids reflects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair clustering algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom (Chen, Fain, Lyu, and Munagala, ICML, 2019). Our algorithm for the discrete setting also matches the best known approximation factor for PF.
View PDF Chat

Computational complexity of $k$-stable matchings

2023-01-01
Haris Aziz , Gergely Csáji , Ágnes Cseh
We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we … We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching $k$-stable if no other matching exists that is more beneficial to at least $k$ out of the $n$ agents. The concept generalizes the recently studied majority stability. We prove that whereas the verification of $k$-stability for a given matching is polynomial-time solvable in all three models, the complexity of deciding whether a $k$-stable matching exists depends on $\frac{k}{n}$ and is characteristic to each model.
View PDF Chat

Envy-free House Allocation under Uncertain Preferences

2023-01-01
Haris Aziz , Isaiah Iliffe , Bo Li +3 more
We study the envy-free house allocation problem when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing … We study the envy-free house allocation problem when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing an allocation that has the highest probability of being envy-free. We show that each model leads to a distinct set of algorithmic and complexity results, including detailed results on (in-)approximability. En route, we consider two related problems of checking whether there exists an allocation that is possibly or necessarily envy-free. We give a complete picture of the computational complexity of these two problems for all the uncertainty models we consider.

Nash Welfare and Facility Location

2023-01-01
Alexander Lam , Haris Aziz , Toby Walsh
We consider the problem of locating a facility to serve a set of agents located along a line. The Nash welfare objective function, defined as the product of the agents' … We consider the problem of locating a facility to serve a set of agents located along a line. The Nash welfare objective function, defined as the product of the agents' utilities, is known to provide a compromise between fairness and efficiency in resource allocation problems. We apply this welfare notion to the facility location problem, converting individual costs to utilities and analyzing the facility placement that maximizes the Nash welfare. We give a polynomial-time approximation algorithm to compute this facility location, and prove results suggesting that it achieves a good balance of fairness and efficiency. Finally, we take a mechanism design perspective and propose a strategy-proof mechanism with a bounded approximation ratio for Nash welfare.

Computing welfare-Maximizing fair allocations of indivisible goods

2022-10-13
Haris Aziz , Xin Huang , Nicholas Mattei +1 more
View PDF Chat

Approximate and strategyproof maximin share allocation of chores with ordinal preferences

2022-07-05
Haris Aziz , Bo Li , Xiaowei Wu
View PDF Chat

The vigilant eating rule: A general approach for probabilistic economic design with constraints

2022-06-16
Haris Aziz , Florian Brandl
View PDF Chat

Obvious Manipulability of Voting Rules

2022-06-01
Haris Aziz , Alexander Lam
The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was … The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was proposed by Troyan and Morrill (2020). We identify several classes of voting rules that satisfy this notion. We also show that several voting rules including k-approval fail to satisfy this property. We characterize conditions under which voting rules are obviously manipulable. One of our insights is that certain rules are obviously manipulable when the number of alternatives is relatively large compared to the number of voters. In contrast to the Gibbard-Satterthwaite theorem, many of the rules we examined are not obviously manipulable. This reflects the relatively easier satisfiability of the notion and the zero information assumption of not obvious manipulability, as opposed to the perfect information assumption of strategyproofness. We also present algorithmic results for computing obvious manipulations and report on experiments.
View PDF Chat

Obvious Manipulability of Voting Rules

2022-06-01
Haris Aziz , Alexander Lam
The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was … The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was proposed by Troyan and Morrill (2020). We identify several classes of voting rules that satisfy this notion. We also show that several voting rules including k-approval fail to satisfy this property. We characterize conditions under which voting rules are obviously manipulable. One of our insights is that certain rules are obviously manipulable when the number of alternatives is relatively large compared to the number of voters. In contrast to the Gibbard-Satterthwaite theorem, many of the rules we examined are not obviously manipulable. This reflects the relatively easier satisfiability of the notion and the zero information assumption of not obvious manipulability, as opposed to the perfect information assumption of strategyproofness. We also present algorithmic results for computing obvious manipulations and report on experiments.
View PDF Chat

A characterization of proportionally representative committees

2022-03-25
Haris Aziz , Barton E. Lee
A well-known axiom for proportional representation is Proportionality for Solid Coalitions (PSC). We characterize committees satisfying PSC as the range of outcomes obtained by the class of Minimal Demand rules, … A well-known axiom for proportional representation is Proportionality for Solid Coalitions (PSC). We characterize committees satisfying PSC as the range of outcomes obtained by the class of Minimal Demand rules, which generalizes an approach pioneered by eminent philosopher Sir Michael Dummett.
View PDF Chat

Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions

2022-01-01
Haris Aziz , Bo Li , Hervé Moulin +1 more
The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, … The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.

How to make the toss fair in cricket?

2022-01-01
Haris Aziz
In the sport of cricket, the side that wins the toss and has the first choice to bat or bowl can have an unfair or a critical advantage. The issue … In the sport of cricket, the side that wins the toss and has the first choice to bat or bowl can have an unfair or a critical advantage. The issue has been discussed by International Cricket Council committees, as well as several cricket experts. In this article, I outline a method to make the toss fair in cricket. The method is based on ideas from the academic fields of game theory and fair division.

Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism

2022-01-01
Haris Aziz , Alexander Lam , Mashbat Suzuki +1 more
Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we … Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we propose a concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number $k$ between $1$ to $n$ and locates the facility at the $k$'th highest agent location) which satisfies Strong Proportionality in expectation. Our main theorem characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation among all randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism that even stronger ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation.
View PDF Chat

Fair Allocation of Two Types of Chores

2022-01-01
Haris Aziz , Jeremy Lindsay , Angus Ritossa +1 more
We consider the problem of fair allocation of indivisible chores under additive valuations. We assume that the chores are divided into two types and under this scenario, we present several … We consider the problem of fair allocation of indivisible chores under additive valuations. We assume that the chores are divided into two types and under this scenario, we present several results. Our first result is a new characterization of Pareto optimal allocations in our setting, and a polynomial-time algorithm to compute an envy-free up to one item (EF1) and Pareto optimal allocation. We then turn to the question of whether we can achieve a stronger fairness concept called envy-free up any item (EFX). We present a polynomial-time algorithm that returns an EFX allocation. Finally, we show that for our setting, it can be checked in polynomial time whether an envy-free allocation exists or not.
View PDF Chat

Approval-Based Voting with Mixed Goods

2022-01-01
Xinhang Lu , Jannik Peters , Haris Aziz +2 more
We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This setting generalizes both the well-studied model of multiwinner … We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This setting generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting -- GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV) -- and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.
View PDF Chat

Coordinating Monetary Contributions in Participatory Budgeting

2022-01-01
Haris Aziz , Sujit Gujar , Manisha Padala +2 more
We formalize a framework for coordinating funding and selecting projects, the costs of which are shared among agents with quasi-linear utility functions and individual budgets. Our model contains the classical … We formalize a framework for coordinating funding and selecting projects, the costs of which are shared among agents with quasi-linear utility functions and individual budgets. Our model contains the classical discrete participatory budgeting model as a special case, while capturing other useful scenarios. We propose several important axioms and objectives and study how well they can be simultaneously satisfied. We show that whereas welfare maximization admits an FPTAS, welfare maximization subject to a natural and very weak participation requirement leads to a strong inapproximability. This result is bypassed if we consider some natural restricted valuations, namely laminar single-minded valuations and symmetric valuations. Our analysis for the former restriction leads to the discovery of a new class of tractable instances for the Set Union Knapsack problem, a classical problem in combinatorial optimization.

Task Allocation using a Team of Robots

2022-01-01
Haris Aziz , Arindam Pal , Ali Pourmiri +2 more
Task allocation using a team or coalition of robots is one of the most important problems in robotics, computer science, operational research, and artificial intelligence. In recent work, research has … Task allocation using a team or coalition of robots is one of the most important problems in robotics, computer science, operational research, and artificial intelligence. In recent work, research has focused on handling complex objectives and feasibility constraints amongst other variations of the multi-robot task allocation problem. There are many examples of important research progress in these directions. We present a general formulation of the task allocation problem that generalizes several versions that are well-studied. Our formulation includes the states of robots, tasks, and the surrounding environment in which they operate. We describe how the problem can vary depending on the feasibility constraints, objective functions, and the level of dynamically changing information. In addition, we discuss existing solution approaches for the problem including optimization-based approaches, and market-based approaches.

Strategyproof and Proportionally Fair Facility Location

2021-11-02
Haris Aziz , Alexander Lam , Barton E. Lee +1 more
We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportional fairness. We present several characterization results … We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportional fairness. We present several characterization results for mechanisms that satisfy strategyproofness and varying levels of proportional fairness. We also characterize one of the mechanisms as the unique equilibrium outcome for any mechanism that satisfies natural fairness and monotonicity properties. Finally, we identify strategyproof and proportionally fair mechanisms that provide the best welfare-optimal approximation among all mechanisms that satisfy the corresponding fairness axiom.

Efficient, Fair, and Incentive-Compatible Healthcare Rationing

2021-07-18
Haris Aziz , Florian Brandl
During the COVID-19 pandemic, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We … During the COVID-19 pandemic, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We consider a healthcare rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories and the patients have different priorities for the categories. We present an allocation rule that respects the priorities, complies with the eligibility requirements, allocates the largest feasible number of units, and does not incentivize agents to hide that they qualify through a category. Moreover, the rule is polynomial-time computable. To the best of our knowledge, it is the first known rule with the aforementioned properties.
View PDF Chat

Achieving Envy-freeness and Equitability with Monetary Transfers

2021-05-18
Haris Aziz
When allocating indivisible resources or tasks, an envy-free allocation or equitable allocation may not exist. We present a sufficient condition and an algorithm to achieve envy-freeness and equitability when monetary … When allocating indivisible resources or tasks, an envy-free allocation or equitable allocation may not exist. We present a sufficient condition and an algorithm to achieve envy-freeness and equitability when monetary transfers are allowed. The approach works for any agent valuation functions (positive or negative) as long as they satisfy superadditivity. For the case of additive utilities, we present a characterization of allocations that can simultaneously be made equitable and envy-free via payments. Our study shows that superadditive valuations constitute the largest class of valuations for which an envy-free and equitable outcome exists for all instances. We then present a distributed algorithm to compute an approximately envy-free outcome for any class of valuations.
View PDF Chat

Optimal Kidney Exchange with Immunosuppressants

2021-05-18
Haris Aziz , Ágnes Cseh , John P. Dickerson +1 more
Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a … Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.
View PDF Chat

Proportionally Representative Participatory Budgeting with Ordinal Preferences

2021-05-18
Haris Aziz , Barton E. Lee
Participatory budgeting (PB) is a democratic paradigm whereby voters decide on a set of projects to fund with a limited budget. We consider PB in a setting where voters report … Participatory budgeting (PB) is a democratic paradigm whereby voters decide on a set of projects to fund with a limited budget. We consider PB in a setting where voters report ordinal preferences over projects and have (possibly) asymmetric weights. We propose proportional representation axioms and clarify how they fit into other preference aggregation settings, such as multi-winner voting and approval-based multi-winner voting. As a result of our study, we also discover a new solution concept for approval-based multi-winner voting, which we call Inclusion PSC (IPSC). IPSC is stronger than proportional justified representation (PJR), incomparable to extended justified representation (EJR), and yet compatible with EJR. The well-studied Proportional Approval Voting (PAV) rule produces a committee that satisfies both EJR and IPSC; however, both these axioms can also be satisfied by an algorithm that runs in polynomial-time.
View PDF Chat

Efficient, Fair, and Incentive-Compatible Healthcare Rationing.

2021-02-08
Haris Aziz , Florian Brandl
As the COVID-19 pandemic shows no clear signs of subsiding, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, … As the COVID-19 pandemic shows no clear signs of subsiding, fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We consider a healthcare rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories and the patients have different priorities for the categories. We present an allocation rule that respects the priorities, complies with the eligibility requirements, allocates the largest feasible number of units, and does not incentivize agents to hide that they qualify through a category. Moreover, the rule is polynomial-time computable. To the best of our knowledge, it is the first known rule with the aforementioned properties.

Participatory Funding Coordination: Model, Axioms and Rules

2021-01-27
Haris Aziz , Aditya Ganguly
We present a new model of collective decision making that captures important crowd-funding and donor coordination scenarios. In the setting, there is a set of projects (each with its own … We present a new model of collective decision making that captures important crowd-funding and donor coordination scenarios. In the setting, there is a set of projects (each with its own cost) and a set of agents (that have their budgets as well as preferences over the projects). An outcome is a set of projects that are funded along with the specific contributions made by the agents. For the model, we identify meaningful axioms that capture concerns including fairness, efficiency, and participation incentives. We then propose desirable rules for the model and study, which sets of axioms can be satisfied simultaneously. An experimental study indicates the relative performance of different rules as well as the price of enforcing fairness axioms.

Multi-Robot Task Allocation -- Complexity and Approximation

2021-01-01
Haris Aziz , Hau Chan , Ágnes Cseh +3 more
Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We … Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.

Individually Rational Land and Neighbor Allocation: Impossibility Results

2021-01-01
Haris Aziz
We consider a setting in which agents are allocated land plots and they have additive preferences over which plot they get and who their neighbor is. Strategyproofness, Pareto optimality, and … We consider a setting in which agents are allocated land plots and they have additive preferences over which plot they get and who their neighbor is. Strategyproofness, Pareto optimality, and individual rationality are three fundamental properties in economic design. We present two impossibility results showing that the three properties are incompatible in this context.

Multi-Robot Task Allocation -- Complexity and Approximation

2021-01-01
Haris Aziz , Hau Chan , Ágnes Cseh +3 more

Optimal Kidney Exchange with Immunosuppressants

2021-01-01
Haris Aziz , Ágnes Cseh , John P. Dickerson +1 more
Potent immunosuppressant drugs suppress the body’s ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the … Potent immunosuppressant drugs suppress the body’s ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, our setting also involves the decision about which patients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. We also show that these algorithms satisfy desirable axiomatic and strategic properties.

Obvious Manipulability of Voting Rules

2021-01-01
Haris Aziz , Alexander Lam
View PDF Chat

Participatory Funding Coordination: Model, Axioms and Rules

2021-01-01
Haris Aziz , Aditya Ganguly
View PDF Chat

Strategyproof and Proportionally Fair Facility Location

2021-01-01
Haris Aziz , Alexander Lam , Barton E. Lee +1 more
We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportionality-based fairness. We introduce and analyze a … We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportionality-based fairness. We introduce and analyze a hierarchy of proportionality-based fairness axioms of varying strength: Individual Fair Share (IFS), Unanimous Fair Share (UFS), Proportionality (as in Freeman et al, 2021), and Proportional Fairness (PF). For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness. We show that imposing strategyproofness renders many of the axioms to be equivalent: the family of mechanisms that satisfy proportionality, unanimity, and strategyproofness is equivalent to the family of mechanisms that satisfy UFS and strategyproofness, which, in turn, is equivalent to the family of mechanisms that satisfy PF and strategyproofness. Furthermore, there is a unique such mechanism: the Uniform Phantom mechanism, which is studied in Freeman et al. (2021). We also characterize the outcomes of the Uniform Phantom mechanism as the unique (pure) equilibrium outcome for any mechanism that satisfies continuity, strict monotonicity, and UFS. Finally, we analyze the approximation guarantees, in terms of optimal social welfare and minimum total cost, obtained by mechanisms that are strategyproof and satisfy each proportionality-based fairness axiom. We show that the Uniform Phantom mechanism provides the best approximation of the optimal social welfare (and also minimum total cost) among all mechanisms that satisfy UFS.

Participatory Funding Coordination: Model, Axioms and Rules

2021-01-01
Haris Aziz , Aditya Ganguly
We present a new model of collective decision making that captures important crowd-funding and donor coordination scenarios. In the setting, there is a set of projects (each with its own … We present a new model of collective decision making that captures important crowd-funding and donor coordination scenarios. In the setting, there is a set of projects (each with its own cost) and a set of agents (that have their budgets as well as preferences over the projects). An outcome is a set of projects that are funded along with the specific contributions made by the agents. For the model, we identify meaningful axioms that capture concerns including fairness, efficiency, and participation incentives. We then propose desirable rules for the model and study, which sets of axioms can be satisfied simultaneously. An experimental study indicates the relative performance of different rules as well as the price of enforcing fairness axioms.
View PDF Chat
Coauthor Papers Together
Toby Walsh 47
Nicholas Mattei 23
Barton E. Lee 23
Serge Gaspers 20
Simon Mackenzie 15
Bo Li 13
Paul Harrenstein 11
Hau Chan 10
Mashbat Suzuki 10
Florian Brandl 10
Jérôme Lang 8
Markus Brill 8
Erel Segal-Halevi 8
Edith Elkind 7
Hervé Moulin 7
Alexander Lam 7
Péter Bíró 7
Felix Brandt 6
Xinhang Lu 6
Jérôme Monnot 6
Zhaohong Sun 6
Ágnes Cseh 6
Baharak Rastegari 6
Xiaowei Wu 6
Ronald de Haan 6
Mike Paterson 6
Christine Rizkallah 5
Pang Luo 5
Jeremy Vollen 5
Nina Narodytska 5
Dominik Peters 5
Rupert Freeman 4
Warut Suksompong 4
Omer Lev 4
Xin Huang 4
Chun Ye 4
Nisarg Shah 4
Bart de Keijzer 4
Jeffrey S. Rosenschein 4
Aris Filos-Ratsikas 4
Angus Ritossa 4
Lirong Xia 4
Julien Lesca 3
Oded Lachish 3
Rahul Savani 3
Fedor Sandomirskiy 3
Piotr Skowron 3
Vincent Conitzer 3
Julián Mestre 3
John P. Dickerson 3

The computational complexity of random serial dictatorship

2013-09-14
Haris Aziz , Felix Brandt , Markus Brill
View PDF Chat

Justified representation in approval-based committee voting

2017-01-09
Haris Aziz , Markus Brill , Vincent Conitzer +3 more
View PDF Chat

Fair assignment of indivisible objects under ordinal preferences

2015-06-18
Haris Aziz , Serge Gaspers , Simon Mackenzie +1 more
View PDF Chat

Fair Public Decision Making

2017-06-20
Vincent Conitzer , Rupert Freeman , Nisarg Shah
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, … 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.
View PDF Chat

Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations

2014-01-01
Haris Aziz , Chun Ye
View PDF Chat

A social welfare optimal sequential allocation procedure

2013-08-03
Thomas Kalinowski , Nina Narodytska , Toby Walsh
We consider a simple sequential allocation procedure for sharing indivisible items between agents in which agents take turns to pick items. Supposing additive utilities and independence between the agents, we … We consider a simple sequential allocation procedure for sharing indivisible items between agents in which agents take turns to pick items. Supposing additive utilities and independence between the agents, we show that the expected utility of each agent is computable in polynomial time. Using this result, we prove that the expected utilitarian social welfare is maximized when agents take alternate turns. We also argue that this mechanism remains optimal when agents behave strategically.

The Core of the Participatory Budgeting Problem

2016-01-01
Brandon Fain , Ashish Goel , Kamesh Munagala
View PDF Chat

Proportionally Representative Participatory Budgeting: Axioms and Algorithms

2018-07-09
Haris Aziz , Barton E. Lee , Nimrod Talmon
Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axioms in participatory budgeting, by generalizing relevant axioms for … Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axioms in participatory budgeting, by generalizing relevant axioms for approval-based multi-winner elections. We observe a rich landscape with respect to the computational complexity of identifying proportional budgets and computing such, and present budgeting methods that satisfy these axioms by identifying budgets that are representative to the demands of vast segments of the voters.

The expanding approvals rule: improving proportional representation and monotonicity

2019-08-09
Haris Aziz , Barton E. Lee
View PDF Chat

Fair Allocation of Indivisible Goods to Asymmetric Agents

2019-01-07
Alireza Farhadi , Mohammad Ghodsi , Mohammad Taghi Hajiaghayi +5 more
We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is … We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee.&#x0D; Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.
View PDF Chat

Knapsack Voting for Participatory Budgeting

2019-05-31
Ashish Goel , A. Krishnaswamy , Sukolsak Sakshuwong +1 more
We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline its drawbacks, and introduce … We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline its drawbacks, and introduce a novel scheme tailored to this setting, which we call “Knapsack Voting.” We study its strategic properties—we show that it is strategy-proof under a natural model of utility (a dis-utility given by the ℓ 1 distance between the outcome and the true preference of the voter) and “partially” strategy-proof under general additive utilities. We extend Knapsack Voting to more general settings with revenues, deficits, or surpluses and prove a similar strategy-proofness result. To further demonstrate the applicability of our scheme, we discuss its implementation on the digital voting platform that we have deployed in partnership with the local government bodies in many cities across the nation. From voting data thus collected, we present empirical evidence that Knapsack Voting works well in practice.
View PDF Chat

Proportional Justified Representation

2017-02-10
Luis Sánchez Fernández , Edith Elkind , Martin Lackner +4 more
The goal of multi-winner elections is to choose a fixed-size committee based on voters’ preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences … The goal of multi-winner elections is to choose a fixed-size committee based on voters’ preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. Recently, Aziz et al. proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). In this paper, we extend the work of Aziz et al. in several directions. First, we answer an open question of Aziz et al., by showing that Reweighted Approval Voting satisfies JR for k = 3; 4; 5, but fails it for k &gt;= 6. Second, we observe that EJR is incompatible with the Perfect Representation criterion, which is important for many applications of multi-winner voting, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with perfect representation, and a committee that provides PJR can be computed in polynomial time if the committee size divides the number of voters. Moreover, just like EJR, PJR can be used to characterize the classic PAV rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.
View PDF Chat

Incentive Compatible Two Player Cake Cutting

2012-01-01
Avishay Maya , Noam Nisan
View PDF Chat

Approximation Algorithms for Computing Maximin Share Allocations

2015-01-01
Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more
View PDF Chat

A Probabilistic Approach to Voting, Allocation, Matching, and Coalition Formation

2019-01-01
Haris Aziz
View PDF Chat

Phragmén's and Thiele's election methods

2016-01-01
Svante Janson
The election methods introduced in 1894--1895 by Phragmén and Thiele, and their somewhat later versions for ordered (ranked) ballots, are discussed in detail. The paper includes definitions and examples and … The election methods introduced in 1894--1895 by Phragmén and Thiele, and their somewhat later versions for ordered (ranked) ballots, are discussed in detail. The paper includes definitions and examples and discussion of whether the methods satisfy some properties, including monotonicity, consistency and various proportionality criteria. The relation with STV is also discussed. The paper also contains historical information on the methods.

Competitive Division of a Mixed Manna

2017-01-01
Anna Bogomolnaia , Hervé Moulin , Fedor Sandomirskiy +1 more
A mixed manna contains goods (that everyone likes) and bads (that everyone dislikes), as well as items that are goods to some agents, but bads or satiated to others. If … A mixed manna contains goods (that everyone likes) and bads (that everyone dislikes), as well as items that are goods to some agents, but bads or satiated to others. If all items are goods and utility functions are homogeneous of degree 1 and concave (and monotone), the competitive division maximizes the Nash product of utilities (Gale–Eisenberg): hence it is welfarist (determined by the set of feasible utility profiles), unique, continuous, and easy to compute. We show that the competitive division of a mixed manna is still welfarist. If the zero utility profile is Pareto dominated, the competitive profile is strictly positive and still uniquely maximizes the product of utilities. If the zero profile is unfeasible (for instance, if all items are bads), the competitive profiles are strictly negative and are the critical points of the product of disutilities on the efficiency frontier. The latter allows for multiple competitive utility profiles, from which no single-valued selection can be continuous or resource monotonic. Thus the implementation of competitive fairness under linear preferences in interactive platforms like SPLIDDIT will be more difficult when the manna contains bads that overwhelm the goods.
View PDF Chat

NON-NULL RANKING MODELS. I

1957-01-01
C. L. Mallows
Journal Article NON-NULL RANKING MODELS. I Get access C. L. MALLOWS C. L. MALLOWS University CollegeLondon Search for other works by this author on: Oxford Academic Google Scholar Biometrika, Volume … Journal Article NON-NULL RANKING MODELS. I Get access C. L. MALLOWS C. L. MALLOWS University CollegeLondon Search for other works by this author on: Oxford Academic Google Scholar Biometrika, Volume 44, Issue 1-2, June 1957, Pages 114–130, https://doi.org/10.1093/biomet/44.1-2.114 Published: 01 June 1957

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.

A Framework for Approval-Based Budgeting Methods

2019-07-17
Nimrod Talmon , Piotr Faliszewski
We define and study a general framework for approval-based budgeting methods and compare certain methods within this framework by their axiomatic and computational properties. Furthermore, we visualize their behavior on … We define and study a general framework for approval-based budgeting methods and compare certain methods within this framework by their axiomatic and computational properties. Furthermore, we visualize their behavior on certain Euclidean distributions and analyze them experimentally.
View PDF Chat

Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation

2015-02-18
Piotr Skowron , Piotr Faliszewski , Jérôme Lang
We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for … We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.
View PDF Chat

Allocation of Divisible Goods under Lexicographic Preferences

2012-06-20
Leonard J. Schulman , Vijay V. Vazirani
We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of incentive compatibility (strategy-proofness), Pareto efficiency, envy-freeness, … We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of incentive compatibility (strategy-proofness), Pareto efficiency, envy-freeness, and time efficiency.

Participatory Budgeting: Models and Approaches

2020-08-10
Haris Aziz , Nisarg Shah
View PDF Chat

Weighted Maxmin Fair Share Allocation of Indivisible Chores

2019-07-28
Haris Aziz , Hau Chan , Bo Li
We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and … We initiate the study of indivisible chore allocation for agents with asymmetric shares. The fairness concept we focus on is the weighted natural generalization of maxmin share: WMMS fairness and OWMMS fairness. We first highlight the fact that commonly-used algorithms that work well for allocation of goods to asymmetric agents, and even for chores to symmetric agents do not provide good approximations for allocation of chores to asymmetric agents under WMMS. As a consequence, we present a novel polynomial-time constant-approximation algorithm, via linear program, for OWMMS. For two special cases: the binary valuation case and the 2-agent case, we provide exact or better constant-approximation algorithms.
View PDF Chat

The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality

2017-07-28
Haris Aziz , Edith Elkind , Piotr Faliszewski +2 more
We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second … We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.
View PDF Chat

Approximation Algorithms for Maximin Fair Division

2017-06-20
Siddharth Barman , Sanath Kumar Krishna Murthy
We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focussed on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.
View PDF Chat

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

2016-10-01
Haris Aziz , Simon Mackenzie
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer … We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nnnnnn. Even if we do not run our protocol to completion, it can find in at most n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n+1</sup> queries an envy-free partial allocation of the cake in which each agent gets at least 1/n of the value of the whole cake.
View PDF Chat

The Complexity of Enumeration and Reliability Problems

1979-08-01
Leslie G. Valiant
The class of $# P$-complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the … The class of $# P$-complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the $NP$-complete problems. Here we show, for a large number of natural counting problems for which there was no previous indication of intractability, that they belong to this class. The technique used is that of polynomial time reduction with oracles via translations that are of algebraic or arithmetic nature.

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

Possible and Necessary Allocations via Sequential Mechanisms

2014-01-01
Haris Aziz , Toby Walsh , Lirong Xia
A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of … A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for five natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternating, strictly alternating and all policies. We identify characterizations of allocations produced balanced, recursively balanced, balanced alternating policies and strictly alternating policies respectively, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.
View PDF Chat

Envy-Free Cake Divisions Cannot be Found by Finite Protocols

2008-01-07
Walter Stromquist
We show that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single … We show that no finite protocol (even if unbounded) can guarantee an envy-free division of a cake among three or more players, if each player is to receive a single connected piece.
View PDF Chat

A note on the undercut procedure

2014-05-05
Haris Aziz
The undercut procedure was presented by Brams, Kilgour and Klamler (2012) as a procedure for identifying an envy-free allocation when agents have preferences over sets of objects. They assumed that … The undercut procedure was presented by Brams, Kilgour and Klamler (2012) as a procedure for identifying an envy-free allocation when agents have preferences over sets of objects. They assumed that agents have strict preferences over objects and their preferences are extended over to sets of objects via the responsive set extension. We point out some shortcomings of the undercut procedure. We then simplify the undercut procedure of Brams et al. and show that it works under a more general condition where agents may express indifference between objects and they may not necessarily have responsive preferences over sets of objects. Finally, we show that the procedure works even if agents have unequal claims.

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

Proportionality and the Limits of Welfarism

2020-07-09
Dominik Peters , Piotr Skowron
We study two influential voting rules proposed in the 1890s by Phragmen and Thiele, which elect a committee of k candidates which proportionally represents the voters. Voters provide their preferences … We study two influential voting rules proposed in the 1890s by Phragmen and Thiele, which elect a committee of k candidates which proportionally represents the voters. Voters provide their preferences by approving an arbitrary number of candidates. Previous work has proposed proportionality axioms satisfied by Thiele's rule (now known as Proportional Approval Voting, PAV) but not by Phragmen's rule. By proposing two new proportionality axioms (laminar proportionality and priceability) satisfied by Phragmen but not Thiele, we show that the two rules achieve two distinct forms of proportional representation. Phragmen's rule ensures that all voters have a similar amount of influence on the committee, and Thiele's rule ensures a fair utility distribution. Thiele's rule is a welfarist voting rule (one that maximizes a function of voter utilities). We show that no welfarist rule can satisfy our new axioms, and we prove that no such rule can satisfy the core. Conversely, some welfarist fairness properties cannot be guaranteed by Phragmen-type rules. This formalizes the difference between the two types of proportionality. We then introduce an attractive committee rule which satisfies a property intermediate between the core and extended justified representation (EJR). It satisfies laminar proportionality, priceability, and is computable in polynomial time. We show that our new rule provides a logarithmic approximation to the core. On the other hand, PAV provides a factor-2 approximation to the core, and this factor is optimal for rules that are fair in the sense of the Pigou--Dalton principle. The full version of the paper is available at http://arxiv.org/pdf/1911.11747.pdf.
View PDF Chat

On the Computation of Fully Proportional Representation

2013-07-22
Nadja Betzler , Arkadii Slinko , Jeffrey Uhlmann
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. … We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.
View PDF Chat

The capacity constrained facility location problem

2020-10-02
Haris Aziz , Hau Chan , Barton E. Lee +1 more
View PDF Chat

Cutting a Cake for Five People

2009-01-01
Amin Saberi , Ying Wang

Fair division of mixed divisible and indivisible goods

2021-01-05
Xiaohui Bei , Zihao Li , Jinyan Liu +2 more
View PDF Chat

Equitable Allocations of Indivisible Goods

2019-07-28
Rupert Freeman , Sujoy Sikdar , Rohit Vaish +1 more
In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While … In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efficiency. We show that the Leximin algorithm produces an allocation that satisfies equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.
View PDF Chat

Fair Division with Binary Valuations: One Rule to Rule Them All

2020-01-01
Daniel Halpern , Ariel D. Procaccia , Alexandros Psomas +1 more
View PDF Chat

The Conference Paper Assignment Problem: Using Order Weighted Averages to Assign Indivisible Goods

2018-04-25
Jing Wu Lian , Nicholas Mattei , Renee Noble +1 more
We propose a novel mechanism for solving the assignment problem when we have a two sided matching problem with preferences from one side (the agents/reviewers) over the other side (the … We propose a novel mechanism for solving the assignment problem when we have a two sided matching problem with preferences from one side (the agents/reviewers) over the other side (the objects/papers) and both sides have capacity constraints. The assignment problem is a fundamental in both computer science and economics with application in many areas including task and resource allocation. Drawing inspiration from work in multi-criteria decision making and social choice theory we use order weighted averages (OWAs), a parameterized class of mean aggregators, to propose a novel and flexible class of algorithms for the assignment problem. We show an algorithm for finding an SUM-OWA assignment in polynomial time, in contrast to the NP-hardness of finding an egalitarian assignment. We demonstrate through empirical experiments that using SUM-OWA assignments can lead to high quality and more fair assignments.
View PDF Chat

Random matching under priorities: stability and no envy concepts

2019-04-03
Haris Aziz , Bettina Klaus
View PDF Chat

Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond

2004-06-22
Julius B. Barbanel , Steven J. Brams

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

On Envy-Free Cake Division

2000-10-01
Oleg Pikhurko
The old problem introduced by Gamov and Stern [3], to divide a cake among m people so that each person thinks that he has at least as much cake as … The old problem introduced by Gamov and Stern [3], to divide a cake among m people so that each person thinks that he has at least as much cake as anybody else (envy-free division), has been solved by Brams and Taylor [1]. This discovery attracted further interest to the area and, a few years later, Robertson and Webb [4] found a new construction. Here we present another solution, which is similar in spirit to the latter. Let each player Pi define a measure Ai on the cake C such that Ai(C) = 1, i E [m] {1, .. ., m}. We assume that Pi can always cut off a piece B cA with Ai(B) = c for any A c C and 0 < c < ,ui(A). We want to find a procedure for constructing a partition C = W1 u U. U Wm with Ai (W) ? Ai(Wj) for all i, j E [im]. We use the following lemma from [4], for which we present an elementary proof.

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

Fair Allocation of Indivisible Public Goods

2018-06-11
Brandon Fain , Kamesh Munagala , Nisarg Shah
We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume … We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. For feasibility constraints defining an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. As far as we are aware, our work is the first to approximate the core in indivisible settings.
View PDF Chat

Achieving fully proportional representation: Approximability results

2015-01-30
Piotr Skowron , Piotr Faliszewski , Arkadii Slinko
View PDF Chat

On Voting and Facility Location

2016-07-21
Michal Feldman , Amos Fiat , Iddan Golomb
We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of … We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on the real line, but other results of ours are more general.
View PDF Chat

Finding Fair and Efficient Allocations

2018-06-11
Siddharth Barman , Sanath Kumar Krishnamurthy , Rohit Vaish
We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if … We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto efficiency. While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare objective is both EF1 and Pareto efficient. However, the problem of maximizing Nash social welfare is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and Pareto efficient; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally Pareto efficient. Another key contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the Nash social welfare objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al., 2017), and also matches the lower bound on the integrality gap of the convex program of Cole et al. (2017). Unlike many of the existing approaches, our algorithm is completely combinatorial, and relies on constructing integral Fisher markets wherein specific equilibria are not only efficient, but also fair.
View PDF Chat