Price of fairness for allocating a bounded resource

DOI10.1016/J.EJOR.2016.08.013zbMATH Open1394.91252arXiv1508.05253OpenAlexW2215472514WikidataQ61638294 ScholiaQ61638294MaRDI QIDQ1752883FDOQ1752883

Authors: Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy 

Publication date: 24 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: In this paper we study the problem of allocating a scarce resource among several players (or agents). A central decision maker wants to maximize the total utility of all agents. However, such a solution may be unfair for one or more agents in the sense that it can be achieved through a very unbalanced allocation of the resource. On the other hand fair/balanced allocations may be far from being optimal from a central point of view. So, in this paper we are interested in assessing the quality of fair solutions, i.e. in measuring the system efficiency loss under a fair allocation compared to the one that maximizes the sum of agents utilities. This indicator is usually called the Price of Fairness and we study it under three different definitions of fairness, namely maximin, Kalai-Smorodinski and proportional fairness. Our results are of two different types. We first formalize a number of properties holding for any general multi-agent problem without any special assumption on the agents utility sets. Then we introduce an allocation problem, where each agent can consume the resource in given discrete quantities (items), such that the maximization of the total utility is given by a Subset Sum Problem. For the resulting Fair Subset Sum Problem, in the case of two agents, we provide upper and lower bounds on the Price of Fairness as functions of an upper bound on the items size.

Full work available at URL: https://arxiv.org/abs/1508.05253

Recommendations

• Pricing for fairness: distributed resource allocation for multiple objectives
• Pricing for fairness
• Optimal bounds on the price of fairness for indivisible goods
• Fair resource allocation for demands with sharp lower tail inequalities
• Fairness in resource allocation: foundation and applications
• Fairness Measures for Resource Allocation
• scientific article; zbMATH DE number 3997494
• Fair resource allocation in a volatile marketplace
• Fair resource allocation: using welfare-based dominance constraints
• A new fairness notion in the assignment of indivisible resources

zbMATH Keywords

multi-agent systemsprice of fairnesssubset sum problem

Mathematics Subject Classification ID

Decision theory (91B06) Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Title not available (Why is that?)
• Algorithmic Game Theory
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The price of fairness
• Other Solutions to Nash's Bargaining Problem
• Rate control for communication networks: shadow prices, proportional fairness and stability
• Handbook of group decision and negotiation
• An exact algorithm for the knapsack sharing problem
• The Subset Sum game
• Title not available (Why is that?)
• An exact algorithm for the knapsack sharing problem with common items
• Inequity averse optimization in operational research
• Solving the linear multiple choice knapsack problem with two objectives: Profit and equity
• An exact decomposition algorithm for the generalized knapsack sharing problem
• The efficiency of fair division
• Maximin fairness in project budget allocation
• The linear multiple choice knapsack problem with equity constraints
• Fairness versus efficiency in charging for the use of common facilities
• Budget-restricted utility games with ordered strategic decisions
• Single-parameter combinatorial auctions with partially public valuations

Cited In (28)

• Efficiency and fairness criteria in the assignment of students to projects
• Price of fairness in two-agent single-machine scheduling problems
• Minimising inequality in multiagent resource allocation: structural analysis of a distributed approach
• Fairness and rank-weighted utilitarianism in resource allocation
• Towards Copeland optimization in combinatorial problems
• The price of fairness
• On the Stackelberg knapsack game
• Fair resource allocation: using welfare-based dominance constraints
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• An exact algorithm for large knapsack sharing problems
• Quantifying the Burden of Exploration and the Unfairness of Free Riding
• A Stackelberg knapsack game with weight control
• The price of fairness with the extended Perles-Maschler solution
• Pricing for fairness
• Computing welfare-maximizing fair allocations of indivisible goods
• Equity in genetic newborn screening
• Kalai-Smorodinsky price of fairness in two-agent single-machine scheduling problem to minimize the number of tardy jobs and maximum cost function
• The efficiency of fair division
• Combining workload balance and patient priority maximisation in operating room planning through hierarchical multi-objective optimisation
• The price of fairness for a small number of indivisible items
• Optimal ordering strategy and budget allocation for the COVID-19 vaccination planning
• Inequity-averse stochastic decision processes
• Pricing for fairness: distributed resource allocation for multiple objectives
• The price of fairness for a two-agent scheduling game minimizing total completion time
• Fairness-oriented train service design for urban rail transit cross-line operation
• Fairness in ambulance routing for post disaster management
• The price of equity with binary valuations and few agent types
• Proportional fairness for combinatorial optimization

This page was built for publication: Price of fairness for allocating a bounded resource

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752883)