# Average-case Analysis of the Assignment Problem with Independent Preferences

arXiv: https://arxiv.org/abs/1906.00182 · HTML: https://mlsanity.com/paper/1906.00182/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [On Scheduling Mechanisms Beyond the Worst Case](https://mlsanity.com/paper/2204.07223/) (2022)

## Abstract (arXiv)

The fundamental assignment problem is in search of welfare maximization mechanisms to allocate items to agents when the private preferences over indivisible items are provided by self-interested agents. The mainstream mechanism textitRandom Priority is asymptotically the best mechanism for this purpose, when comparing its welfare to the optimal social welfare using the canonical textitworst-case approximation ratio. Despite its popularity, the efficiency loss indicated by the worst-case ratio does not have a constant bound. Recently, [Deng, Gao, Zhang 2017] show that when the agents' preferences are drawn from a uniform distribution, its textitaverage-case approximation ratio is upper bounded by 3.718. They left it as an open question of whether a constant ratio holds for general scenarios. In this paper, we offer an affirmative answer to this question by showing that the ratio is bounded by 1/μ when the preference values are independent and identically distributed random variables, where μ is the expectation of the value distribution. This upper bound also improves the upper bound of 3.718 in [Deng, Gao, Zhang 2017] for the Uniform distribution. Moreover, under mild conditions, the ratio has a textitconstant bound for any independent random values. En route to these results, we develop powerful tools to show the insights that in most instances the efficiency loss is small.