Abstract

Inspired by many applications of bipartite matching in online advertising and machine learning, we study a simple and natural iterative proportional allocation algorithm: Maintain a priority score for each node a A on one side of the bipartition, initialized as = 1. Iteratively al cate the nodes on the other side to eligible nodes in in proportion of their priority scores. After each round, for each node a, decrease or increase the score based on whether it is overor underallocated. Our first result is that this simple, distributed algorithm converges to a (1 )-approximate fractional b-matching solution in rounds. We also extend the proportional allocation algorithm and convergence results to the maximum weighted matching problem, and show that the algorithm can be naturally tuned to produce maximum matching with high entropy. High entropy, in turn, implies additional desirable properties of this matching, e.g., it sat fies certain diversity and fairness (aka anonymity) properties that are desirable in a variety of appli tions in online advertising and machine learning.