How to Resolve Envy by Adding Goods
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908485401182208 |
|---|---|
| author | Bentert, Matthias Bredereck, Robert Deltl, Eva Jain, Pallavi Kellerhals, Leon |
| author_facet | Bentert, Matthias Bredereck, Robert Deltl, Eva Jain, Pallavi Kellerhals, Leon |
| contents | We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomial-time algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. Notably, although not every instance admits an envy-free solution, our approach allows us to efficiently determine, in polynomial time, whether a solution exists-an aspect that is both theoretically interesting and far from trivial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08682 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How to Resolve Envy by Adding Goods Bentert, Matthias Bredereck, Robert Deltl, Eva Jain, Pallavi Kellerhals, Leon Computer Science and Game Theory Computational Complexity We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomial-time algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. Notably, although not every instance admits an envy-free solution, our approach allows us to efficiently determine, in polynomial time, whether a solution exists-an aspect that is both theoretically interesting and far from trivial. |
| title | How to Resolve Envy by Adding Goods |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2508.08682 |