{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:13:34Z","timestamp":1760202814643},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>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.\u00a0The mainstream mechanism \\textit{Random Priority} is asymptotically the best mechanism for this purpose, when comparing its welfare\u00a0 to the optimal social welfare using the canonical \\textit{worst-case approximation ratio}.\u00a0\n\nSurprisingly, the efficiency loss indicated by the worst-case ratio does not have a constant bound \\cite{FFZ:14}.Recently, \\cite{DBLP:conf\/mfcs\/DengG017} shows that when the agents' preferences are drawn from a uniform distribution, its \\textit{average-case approximation ratio} is upper bounded by 3.718.\u00a0They left it as an open question of whether a constant ratio holds for general scenarios.\u00a0In this paper, we offer an affirmative answer to this question by showing that the ratio is bounded by $1\/\\mu$ when the preference values are independent and identically distributed random variables, where $\\mu$ is the expectation of the value distribution. This upper bound improves the results in \\cite{DBLP:conf\/mfcs\/DengG017} for the Uniform distribution as well. Moreover, under mild conditions, the ratio has a \\textit{constant} bound for any independent\u00a0 random values.\n\nEn route to these results, we develop powerful tools to show the insights that for most valuation inputs, the efficiency loss is small.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/41","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"287-293","source":"Crossref","is-referenced-by-count":2,"title":["Average-case Analysis of the Assignment Problem with Independent Preferences"],"prefix":"10.24963","author":[{"given":"Yansong","family":"Gao","sequence":"first","affiliation":[{"name":"Applied Mathematics and Computational Science, University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Electronics and Computer Science, University of Southampton"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2019","name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","start":{"date-parts":[[2019,8,10]]},"theme":"Artificial Intelligence","location":"Macao, China","end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:25Z","timestamp":1564285585000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/41"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/41","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}