Conflict and Fairness in Resource Allocation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929267550453760 |
|---|---|
| author | Bandopadhyay, Susobhan Banik, Aritra Gupta, Sushmita Jain, Pallavi Sahu, Abhishek Saurabh, Saket Tale, Prafullkumar |
| author_facet | Bandopadhyay, Susobhan Banik, Aritra Gupta, Sushmita Jain, Pallavi Sahu, Abhishek Saurabh, Saket Tale, Prafullkumar |
| contents | In the standard model of fair allocation of resources to agents, every agent has some utility for every resource, and the goal is to assign resources to agents so that the agents' welfare is maximized. Motivated by job scheduling, interest in this problem dates back to the work of Deuermeyer et al. [SIAM J. on Algebraic Discrete Methods'82]. Recent works consider the compatibility between resources and assign only mutually compatible resources to an agent. We study a fair allocation problem in which we are given a set of agents, a set of resources, a utility function for every agent over a set of resources, and a {\it conflict graph} on the set of resources (where an edge denotes incompatibility). The goal is to assign resources to the agents such that $(i)$ the set of resources allocated to an agent are compatible with each other, and $(ii)$ the minimum satisfaction of an agent is maximized, where the satisfaction of an agent is the sum of the utility of the assigned resources. Chiarelli et al. [Algorithmica'22] explore this problem from the classical complexity perspective to draw the boundary between the cases that are polynomial-time solvable and those that are \NP-hard. In this article, we study the parameterized complexity of the problem (and its variants) by considering several natural and structural parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04265 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conflict and Fairness in Resource Allocation Bandopadhyay, Susobhan Banik, Aritra Gupta, Sushmita Jain, Pallavi Sahu, Abhishek Saurabh, Saket Tale, Prafullkumar Computer Science and Game Theory Data Structures and Algorithms In the standard model of fair allocation of resources to agents, every agent has some utility for every resource, and the goal is to assign resources to agents so that the agents' welfare is maximized. Motivated by job scheduling, interest in this problem dates back to the work of Deuermeyer et al. [SIAM J. on Algebraic Discrete Methods'82]. Recent works consider the compatibility between resources and assign only mutually compatible resources to an agent. We study a fair allocation problem in which we are given a set of agents, a set of resources, a utility function for every agent over a set of resources, and a {\it conflict graph} on the set of resources (where an edge denotes incompatibility). The goal is to assign resources to the agents such that $(i)$ the set of resources allocated to an agent are compatible with each other, and $(ii)$ the minimum satisfaction of an agent is maximized, where the satisfaction of an agent is the sum of the utility of the assigned resources. Chiarelli et al. [Algorithmica'22] explore this problem from the classical complexity perspective to draw the boundary between the cases that are polynomial-time solvable and those that are \NP-hard. In this article, we study the parameterized complexity of the problem (and its variants) by considering several natural and structural parameters. |
| title | Conflict and Fairness in Resource Allocation |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.04265 |