Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time

on YouTube ↗28m

" summary

Proves a polynomial-time algorithm to compute the nucleolus for weighted cooperative matching games on general graphs, not just bipartite or unit-weight cases. Constructs a compact linear description of the optimal face via Edmonds matching polytope, finds a relative interior point to identify tight matchings, and exploits a resulting laminar family structure to reduce constraints. Claims this yields an efficient, implementable procedure that extends prior special-case algorithms to fully weighted, general graphs.

AI-written summary · about

" chapters (13)

1. 0:00Introduction and context
2. 0:45Problem definition
3. 2:52Allocation concepts
4. 4:05Defining the excess vector
5. 7:01The nucleolus concept
6. 7:53Previous work and results
7. 10:47Outline of the method
8. 12:34Linear program formulation
9. 16:01Optimal solution analysis
10. 18:30Using Edmonds' formulation
11. 21:18Properties of optimal face
12. 23:12Key properties of solution
13. 26:00Questions and conclusion