Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
Provides a theoretical characterization linking proportional allocations to matching-covered bipartite graphs, of interest to combinatorial optimization and algorithmic game theory.
The paper characterizes bipartite graphs that admit perfect proportional allocations, proving they are exactly matching-covered graphs, and extends the result to non-matching-covered graphs.
Given a bipartite graph that has a perfect matching, a prefect proportional allocation is an assignment of positive weights to the nodes of the right partition so that every left node is fractionally assigned to its neighbors in proportion to their weights, and these assignments define a fractional perfect matching. We prove that a bipartite graph has a perfect proportional allocation if and only if it is matching covered, by using a classical result on matrix scaling. We also present an extension of this result to provide a simple allocation strategy in non-matching covered bipartite graphs.