Source-linked AI summary
Matroid Packing Games: The Core and the Nucleolus
Pengfei Liu, Han Xiao, Xin Chen, Qizhi Fang
TL;DR
The paper studies how to characterize stable allocations and compute the nucleolus for matroid packing games, extending network strength games beyond graphic matroids. It derives exchange-graph structure and local constraints, yielding core characterizations and polynomial-time nucleolus algorithms for both nonempty- and empty-core cases.
Problem
Matroid packing games extend network strength games to general matroids, where characterizing the core and computing the nucleolus requires handling coalition constraints across the game.
Source: §1 · pp. 1–2Method
The paper builds exchange graphs and hierarchy partitions from matroid packings, reducing coalition constraints to polynomially many local constraints.
Source: §1 · p. 2, §2.4 · p. 6Results
The paper characterizes the core and least core and provides polynomial-time algorithms for nucleolus computation in all cases in the independence-oracle model.
Source: §1 · p. 2Takeaways & Limitations
Network strength games are the graphic-matroid special case, and the framework covers nucleolus computation with either a nonempty or empty core.
Source: §1 · pp. 1–2, §6 · p. 17The algorithmic results use the independence-oracle model, in which matroids are presented through independence queries.
Source: §2.2 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends the network strength game to general matroids and studies core stability and nucleolus allocation in the resulting matroid packing game. It uses matroid exchange structure to reduce coalition constraints and address nucleolus computation whether the core is nonempty or empty.
1 Introduction
- The matroid packing game assigns players to matroid elements and values each coalition by its maximum number of pairwise disjoint contained bases, extending the network strength game.The network strength game is the graphic-matroid special case.Source: §1 · p. 1
- Core stability excludes allocations that let a coalition benefit by leaving the grand coalition, but the core can be empty, motivating the least core as a relaxation.The least core maximizes the smallest excess over all coalitions.Source: §1 · p. 1
- Computing the nucleolus by Maschler’s scheme requires sequential linear programs that may have exponentially many coalition constraints.Polynomial-time nucleolus algorithms are known for several game classes, while hardness is established for others.Source: §1 · pp. 1–2
- The paper characterizes the core and least core and gives polynomial-time algorithms for computing the nucleolus in all cases in the independence-oracle model.Its exchange-derived partition and order reduce exponentially many coalition constraints to polynomially many local constraints.Source: §1 · p. 2
- For a nonempty core, a fixed maximum base packing yields an exchange-graph characterization using uncovered elements, arc differences, and strongly connected components.The resulting hierarchy partition determines the unique optimal allocation of a compact second linear program.Source: §1 · p. 2
- For an empty core, a maximum fractional base packing identifies the least core through its dual, while exchange-graph components produce a hierarchy for local constraints.Fractional packing is auxiliary; coalition values remain integer packing numbers, unlike the fractional game in [4, Section 8].Source: §1 · p. 2
2 Preliminaries and Definitions
The preliminaries define cooperative-game solution concepts, the matroid packing game, and integer and fractional base packing. They then introduce exchange graphs and a hierarchy partition that organizes strongly connected components by reachability.
2.1 Cooperative game
- The nucleolus lexicographically maximizes the ordered coalition excesses; the least core instead maximizes the minimum excess, and the nucleolus lies in the core when it is nonempty and in the least core otherwise.A core allocation gives every coalition at least its game value.Source: §2.1 · p. 3
2.3 Matroid base packing
- Integer base packing seeks the largest family of pairwise disjoint bases, while fractional base packing relaxes integrality and has an equal-valued linear-programming dual.A maximum fractional packing can be computed in strongly polynomial time using polynomially many bases and positive rational weights.Source: §2.2 · p. 4, §2.3 · pp. 4–5
2.2 Matroid packing game
- In the matroid packing game, players are elements and a coalition’s value is the maximum number of pairwise disjoint bases it contains.The paper assumes positive rank, excludes the case where the ground set itself is a base, and uses an independence-oracle model.Source: §2.2 · p. 4
2.4 Graph characterization of base packing and fractional base packing
- Exchange graphs encode feasible single-element base swaps; packing graphs take unions of these graphs, and fractional packing graphs use the positive-weight bases.The hierarchy partition repeatedly removes minimal strongly connected components in the reachability order and can be computed in polynomial time.Source: §2.4 · pp. 5–6
3 Characterization of the core of ΓM
The matroid packing game’s core can be characterized through essential coalitions and the exchange graph of a fixed base packing. This yields polynomial-time tests for core nonemptiness, membership, and finding a core allocation.
3.1 The essential coalitions
- The core is determined by essential coalitions, which in the matroid packing game are exactly the singletons and the bases.For any core allocation and maximum base packing, each packed base has allocation 1 and uncovered elements have allocation 0.Source: §3.1 · p. 7
3.2 The characterizations and algorithms for the core
- For any core allocation x and any arc (u, v) in the exchange graph of a fixed base packing, the allocation difference satisfies x(v) − x(u) ≥ 0.Vertices in the same strongly connected component have equal values; if a directed path from v to N0 exists, then x(v) = 0.Source: §3.2 · p. 8
- For a fixed base packing, the core is nonempty exactly when the exchange-graph condition in Theorem 3 holds.The supplied passage states the theorem’s equivalence but does not include the condition itself.Source: §3.2 · p. 9
- Testing core nonemptiness, checking membership, and finding a core allocation are all solvable in polynomial time.When the core is nonempty, assigning equal value across the union of the specified SCCs and zero elsewhere gives a core allocation.Source: §3.2 · pp. 8–9
4 The nucleolus when C(ΓM)̸ = ∅
For games with nonempty core, the paper computes the nucleolus using a compact linear-programming approach based on exchange structure. The hierarchy partition determines the unique optimal allocation, yielding a polynomial-time algorithm.
4 The nucleolus when C(ΓM)̸ = ∅
- In this game, the essential coalitions are exactly the singletons and bases, which determine the nucleolus when the core is nonempty.Consequently, the second program can be written using these coalitions.Source: §4 · p. 9
- The passage states that this leads to a polynomial-size linear program; it defines N* as elements with zero allocation in every core allocation and E* as arcs with zero endpoint-allocation difference in every core allocation.Source: §4 · p. 9
- The hierarchy partition determines the unique optimal allocation of the second program, and that allocation is the nucleolus.The paper states that this partition can be computed in polynomial time.Source: §4 · p. 11
- When the core is nonempty, the matroid packing game’s nucleolus can be computed in polynomial time.The result is established using the first two linear programs in the nucleolus scheme.Source: §4 · pp. 9, 11
5 The least core and nucleolus when C(ΓM) = ∅
For an empty-core matroid packing game, the least core and nucleolus are characterized through the exchange graph of a maximum fractional base packing. Its SCC hierarchy yields a polynomial-time computation of the least core structure and nucleolus.
5.1 The least core
- The least-core allocations correspond, after scaling, to optimal solutions of the fractional packing dual.The least-core LP and the base-constraint LP have the same optimal allocations and value, with the latter linked to the dual optimum.Source: §5.1 · p. 12
- A maximum fractional base packing exchange graph characterizes the least core: allocations are zero on uncovered elements and nondecreasing along its arcs.Within each SCC, element allocations are equal; elements that can reach an uncovered element receive zero.Source: §5.1 · pp. 13–14
5.2 The nucleolus
- The hierarchy partition determines a unique optimal allocation of the second program, which is the nucleolus.The allocation is specified using the hierarchy levels and assigns zero to elements outside N*.Source: §5.2 · p. 16
- The least core value, SCC partition and partial order, and nucleolus can all be computed in polynomial time when the core is empty.The algorithm operates in the independence oracle model.Source: §5.2 · p. 16
6 Conclusion
The paper extends its framework beyond the nucleolus to other solution concepts and matroid covering games. It also places network strength games within the framework as the graphic-matroid special case.
6 Conclusion
- The nucleon coincides either with a core allocation or with the nucleolus in the results obtained by the authors.The nucleon is described as a multiplicative variant of the nucleolus.Source: §6 · p. 16
- Matroid covering games are identified as a direction that generalizes arboricity games from graphic matroids to general matroids.The authors report core characterizations and polynomial-time nucleolus algorithms for these games using their framework.Source: §6 · pp. 16–17
- Network strength games are the graphic-matroid special case of matroid packing games, and the paper gives a structural characterization of their nucleolus without a general ellipsoid framework.The cited recent work [11] instead relies on the ellipsoid algorithm and assumes the family of fixed coalitions is given in advance.Source: §6 · p. 17