Ordinal Maximin Share Approximation for Goods
Authors: Hadi Hosseini, Andrew Searns, Erel Segal-Halevi
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In Appendix A, we conduct simulations with valuations generated randomly from various distributions. For several values of ℓ, we compute a lower bound on the ℓ-out-of(ℓ+ 1/2)n MMS guarantee using a simple greedy algorithm. We compare this lower bound to an upper bound on the (3/4 + 1/12n)-fraction MMS guarantee, which is currently the best known worst-case multiplicative MMS approximation. We find that, for any ℓ 2, when the number of goods is at least 20n, the lower bound on the ordinal approximation is better than the upper bound on the multiplicative approximation. In experimental simulations on instances generated uniformly at random, Algorithm 3 significantly outperforms the theoretical guarantee of 1-out-of3n/2 MMS. In Appendix C, we provide detailed experimentations and compare the bidirectional bag-filling algorithm with other bag-filling methods (e.g. the unidirectional bag-filling algorithm). |
| Researcher Affiliation | Academia | Hadi Hosseini EMAIL Pennsylvania State University, University Park; Andrew Searns EMAIL Johns Hopkins University Applied Physics Laboratory; Erel Segal-Halevi EMAIL Ariel University, Ariel |
| Pseudocode | Yes | ALGORITHM 1: The Lone Divider algorithm. Based on Kuhn (1967).; ALGORITHM 2: Finding an ℓ-out-of(ℓ+ 1/2)n MMS allocation.; ALGORITHM 3: Bidirectional bag-filling |
| Open Source Code | Yes | Source code for the experiments is available at https://github.com/erelsgl/ordinal-maximin-share. |
| Open Datasets | No | In Appendix A, we conduct simulations with valuations generated randomly from various distributions. For several values of ℓ, we compute a lower bound on the ℓ-out-of(ℓ+ 1/2)n MMS guarantee using a simple greedy algorithm. In each experiment, we generated 1,000 instances for each pair of n [3, 20] and m [n, 100]13 where the valuations were uniformly distributed from [0, 1000] and then ordered. |
| Dataset Splits | No | The paper describes generating 1,000 instances for various 'n' and 'm' values with uniformly distributed valuations for simulations, but it does not specify any training/test/validation dataset splits for these instances. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, processor types, memory amounts) are mentioned in the paper for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers (e.g., library or solver names with versions like Python 3.8, CPLEX 12.4) needed to replicate the experiment. |
| Experiment Setup | Yes | We chose m random integers to use as the good values. We performed three simulations, in which the values were distributed (a) uniformly at random in [1, 1000], (b) uniformly at random in [1000, 2000], and (c) geometrically with mean value of 1000. We modified n between 4 and 20, and m between 4n and 80n. In each experiment, we generated 1,000 instances for each pair of n [3, 20] and m [n, 100] where the valuations were uniformly distributed from [0, 1000] and then ordered. |