Matroid packing games provide efficient fair allocation methods
Matroid Packing Games: The Core and the Nucleolus
Computer Science and Game Theory
Summary
Matroid packing problems involve selecting groups of elements without overlap, with many real-world uses. The researchers study these problems through cooperative game theory to find fair ways to share resources. They create a method to check when fair divisions exist and how to find the best fair division efficiently. Their approach works for broad cases beyond previous network-specific models, even when fair solutions are hard to find.
What this means in practice
- •For network designers: Find stable and fair resource allocations in network systems based on general combinatorial constraints.
- •For operations research analysts: Efficiently check feasibility and compute fair cost or profit divisions in complex allocation problems modeled by matroids.
Authors
Pengfei Liu, Han Xiao, Xin Chen, Qizhi Fang
Abstract
In this paper, we study the matroid base packing problem from the perspective of cooperative game theory and define the associated matroid base packing game. This model extends the network strength game of Baiou and Barahona (2020) from graphic matroids to general matroids. Building on the exchange structure of matroid, we develop a graph theoretic framework for analyzing the core and the nucleolus in this game. This framework yields a compact characterization of core nonemptiness and enables polynomial time algorithms for testing core nonemptiness, finding a core allocation, and computing the nucleolus. In particular, the approach provides a broader and more structured framework for the nucleolus computation problem arising in network strength games studied by Baiou and Barahona (2020), covering both the nonempty core and empty core cases.