On the Max-Min Fair Stochastic Allocation of Indivisible Goods
Authors: Yasushi Kawase, Hanna Sumita2070-2078
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fairly allocating a set of indivisible goods to risk-neutral agents in a stochastic setting. We propose an (approximation) algorithm to find a stochastic allocation that maximizes the minimum utility among the agents. The algorithm runs by repeatedly finding an (approximate) allocation to maximize the total virtual utility of the agents. This implies that the problem is solvable in polynomial time when the utilities are gross-substitutes (which is a subclass of submodular). When the utilities are submodular, we can find a (1 1/e)-approximate solution for the problem and this is best possible unless P=NP. We also extend the problem where a stochastic allocation must satisfy the (ex ante) envy-freeness. Under this condition, we demonstrate that the problem is NP-hard even when every agent has an additive utility with a matroid constraint (which is a subclass of grosssubstitutes). Furthermore, we propose a polynomial-time algorithm for the setting with a restriction that the matroid constraint is common to all agents. |
| Researcher Affiliation | Academia | Yasushi Kawase,1,2 Hanna Sumita3 1Tokyo Institute of Technology 2RIKEN AIP Center 3Tokyo Metropolitan University kawase.y.ab@m.titech.ac.jp, sumita@tmu.ac.jp |
| Pseudocode | Yes | Algorithm 1: Approximate separation algorithm; Algorithm 2: Approximate algorithm for (4) |
| Open Source Code | No | The paper does not provide any information or links regarding the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or refer to any specific datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical validation or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |