Multiagent Matroid Upgrading: Greedy is Fair and Efficient
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917552690561024 |
|---|---|
| author | Ma, Qingwen Peng, Chao Xu, Changfeng Xu, Chenyang Zhang, Ruilong |
| author_facet | Ma, Qingwen Peng, Chao Xu, Changfeng Xu, Chenyang Zhang, Ruilong |
| contents | This paper introduces a general multiagent matroid upgrading problem that models a broad class of real-world resource allocation tasks. In this setting, there are multiple agents and a ground set of elements, where each element is assigned to a specific agent and has two associated costs: a default cost and a reduced (upgraded) cost. Upgrading an element lowers its cost to the upgraded value, while non-upgraded elements retain their default costs. Each agent is associated with its own matroid, with the goal of finding a minimum-cost basis. The central task is to select at most k elements to upgrade so as to minimize a non-decreasing convex function over the agents' minimum basis costs, capturing both efficiency and fairness objectives in multiagent systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_01309 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Multiagent Matroid Upgrading: Greedy is Fair and Efficient Ma, Qingwen Peng, Chao Xu, Changfeng Xu, Chenyang Zhang, Ruilong Data Structures and Algorithms This paper introduces a general multiagent matroid upgrading problem that models a broad class of real-world resource allocation tasks. In this setting, there are multiple agents and a ground set of elements, where each element is assigned to a specific agent and has two associated costs: a default cost and a reduced (upgraded) cost. Upgrading an element lowers its cost to the upgraded value, while non-upgraded elements retain their default costs. Each agent is associated with its own matroid, with the goal of finding a minimum-cost basis. The central task is to select at most k elements to upgrade so as to minimize a non-decreasing convex function over the agents' minimum basis costs, capturing both efficiency and fairness objectives in multiagent systems. |
| title | Multiagent Matroid Upgrading: Greedy is Fair and Efficient |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2606.01309 |