Contention resolution, matrix scaling and fair allocation

A contention resolution (CR) scheme is a basic algorithmic primitive, that deals with how to allocate items among a random set S of competing players, while maintaining various properties. We consider the most basic setting where a single item must be allocated to some player in S. Here, in a seminal work, Feige and Vondrak (2006) designed a fair CR scheme when the set S is chosen from a product distribution. We explore whether such fair schemes exist for arbitrary non-product distributions on sets of players S, and whether they admit simple algorithmic primitives. Moreover, can we go beyond fair allocation and design such schemes for all possible achievable allocations. We show that for any arbitrary distribution on sets of players S, and for any achievable allocation, there exist several natural CR schemes that can be succinctly described, are simple to implement and can be efficiently computed to any desired accuracy. We also characterize the space of achievable allocations for any distribution, give algorithms for computing an optimum fair allocation for arbitrary distributions, and describe other natural fair CR schemes for product distributions. These results are based on matrix scaling and various convex programming relaxations.

• View at Publisher