Price of fairness for allocating a bounded resource
From MaRDI portal
(Redirected from Publication:1752883)
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.
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
Cites work
- scientific article; zbMATH DE number 1015852 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- Algorithmic Game Theory
- An exact algorithm for the knapsack sharing problem
- An exact algorithm for the knapsack sharing problem with common items
- An exact decomposition algorithm for the generalized knapsack sharing problem
- Budget-restricted utility games with ordered strategic decisions
- Fairness versus efficiency in charging for the use of common facilities
- Handbook of group decision and negotiation
- Inequity averse optimization in operational research
- Maximin fairness in project budget allocation
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Other Solutions to Nash's Bargaining Problem
- Rate control for communication networks: shadow prices, proportional fairness and stability
- Single-parameter combinatorial auctions with partially public valuations
- Solving the linear multiple choice knapsack problem with two objectives: Profit and equity
- The Subset Sum game
- The efficiency of fair division
- The linear multiple choice knapsack problem with equity constraints
- The price of fairness
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
- The efficiency of fair division
- Kalai-Smorodinsky price of fairness in two-agent single-machine scheduling problem to minimize the number of tardy jobs and maximum cost function
- Equity in genetic newborn screening
- 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
- Inequity-averse stochastic decision processes
- Pricing for fairness: distributed resource allocation for multiple objectives
- Optimal ordering strategy and budget allocation for the COVID-19 vaccination planning
- 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)
