Average-case Analysis of the Assignment Problem with Independent Preferences
Authors: Yansong Gao, Jie Zhang
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 et al., 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. |
| Researcher Affiliation | Academia | 1Applied Mathematics and Computational Science, University of Pennsylvania 2Electronics and Computer Science, University of Southampton gaoyans@sas.upenn.edu, jie.zhang@soton.ac.uk |
| Pseudocode | No | The paper describes the Random Priority mechanism in prose but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not mention releasing source code for the described methodology. |
| Open Datasets | No | The paper is a theoretical analysis of distributions and does not use or refer to any specific publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper presents theoretical analysis and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is a theoretical work and does not describe any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or specific hyperparameters. |