Fair Coordination in Strategic Scheduling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908712396914688 |
|---|---|
| author | Lee, Wei-Chen Bullinger, Martin Abate, Alessandro Wooldridge, Michael |
| author_facet | Lee, Wei-Chen Bullinger, Martin Abate, Alessandro Wooldridge, Michael |
| contents | We consider a scheduling problem of strategic agents representing jobs of different weights. Each agent has to decide on one of a finite set of identical machines to get their job processed. In contrast to the common and exclusive focus on makespan minimization, we want the outcome to be fair under strategic considerations of the agents. Two natural properties are credibility, which ensures that the assignment is a Nash equilibrium and equality, requiring that agents with equal-weight jobs are assigned to machines of equal load. We combine these two with a hierarchy of fairness properties based on envy-freeness together with several relaxations based on the idea that envy seems more justified towards agents with a higher weight. We present a complete complexity landscape for satisfiability and decision versions of these properties, alone or in combination, and study them as structural constraints under makespan optimization. For our positive results, we develop a unified algorithmic approach, where we achieve different properties by fine-tuning key subroutines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_13244 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair Coordination in Strategic Scheduling Lee, Wei-Chen Bullinger, Martin Abate, Alessandro Wooldridge, Michael Computer Science and Game Theory Computational Complexity Multiagent Systems Theoretical Economics We consider a scheduling problem of strategic agents representing jobs of different weights. Each agent has to decide on one of a finite set of identical machines to get their job processed. In contrast to the common and exclusive focus on makespan minimization, we want the outcome to be fair under strategic considerations of the agents. Two natural properties are credibility, which ensures that the assignment is a Nash equilibrium and equality, requiring that agents with equal-weight jobs are assigned to machines of equal load. We combine these two with a hierarchy of fairness properties based on envy-freeness together with several relaxations based on the idea that envy seems more justified towards agents with a higher weight. We present a complete complexity landscape for satisfiability and decision versions of these properties, alone or in combination, and study them as structural constraints under makespan optimization. For our positive results, we develop a unified algorithmic approach, where we achieve different properties by fine-tuning key subroutines. |
| title | Fair Coordination in Strategic Scheduling |
| topic | Computer Science and Game Theory Computational Complexity Multiagent Systems Theoretical Economics |
| url | https://arxiv.org/abs/2512.13244 |