Multiagent Matroid Upgrading: Greedy is Fair and Efficient

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𝑘 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. We show that the problem is polynomial-time solvable and that an optimal solution can be obtained via a simple greedy algorithm. Our analysis exploits the structural properties of matroids to establish the existence of optimal substructures, thereby ensuring that greedy upgrading yields optimal outcomes. Building on this insight, we can further extend our result to more general settings, such as scenarios with interval fairness constraints, where the number of elements upgraded for each agent is required to lie within a specified interval.

Authors

• Qingwen Ma School of Software Engineering, East China Normal University
• Chao Peng School of Software Engineering, East China Normal University
• Changfeng Xu School of Software Engineering, East China Normal University
• Chenyang Xu School of Software Engineering, East China Normal University
• Ruilong Zhang Department of Computer Science, City University of Hong Kong (Dongguan)

Keywords

• Matroid upgrading
• Multiagent systems
• Greedy algorithms
• Fair resource allocation