TY - CONF

T1 - Average-case analysis of the assignment problem with independent preferences

AU - Gao, Yansong

AU - Zhang, Jie

PY - 2019

Y1 - 2019

N2 - 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 Random Priority is asymptotically the best mechanism for this purpose, when comparing its welfare to the optimal social welfare using the canonical worst-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 average-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 constant 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.

AB - 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 Random Priority is asymptotically the best mechanism for this purpose, when comparing its welfare to the optimal social welfare using the canonical worst-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 average-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 constant 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.

M3 - Paper

ER -