{"ID":2921781,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T05:56:00.181519634Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01309","arxiv_id":"2606.01309","title":"Multiagent Matroid Upgrading: Greedy is Fair and Efficient","abstract":"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.","short_abstract":"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 (...","url_abs":"https://arxiv.org/abs/2606.01309","url_pdf":"https://arxiv.org/pdf/2606.01309v1","authors":"[\"Qingwen Ma\",\"Chao Peng\",\"Changfeng Xu\",\"Chenyang Xu\",\"Ruilong Zhang\"]","published":"2026-05-31T15:57:38Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}