Multiagent Matroid Upgrading: Greedy is Fair and Efficient
Provides a theoretical framework and algorithm for resource allocation problems involving multiple agents with matroid constraints, addressing both efficiency and fairness.
This paper introduces a multiagent matroid upgrading problem and shows that a simple greedy algorithm achieves a (1/2)-approximation for minimizing a convex function of agents' minimum basis costs, balancing efficiency and fairness.
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.