1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations
Authors: Chandra Chekuri, Pooja Kulkarni , Rucha Kulkarni, Ruta Mehta
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. First, we design an LP-relaxation-based method to find a 1/2-MMS allocation for SPLC valuations in polynomial time. Our result is in fact stronger; the algorithm outputs an allocation that gives each agent a value at least 1/2-APSi (for symmetric agents). Second, we show that a simple greedy algorithm achieves 1/3-APS allocation for submodular valuations. |
| Researcher Affiliation | Academia | Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta University of Illinois at Urbana-Champaign 201 N Goodwin Ave Urbana, Illinois 61801 USA chekuri@illinois.edu, poojark2@illinois.edu, ruchark2@illinois.edu, rutameht@illinois.edu |
| Pseudocode | Yes | Algorithm 1: Rounding the Fractional Optimal of LP (6), Algorithm 2: Existence of 1/2-MMS Algorithm for SPLC valuations, Algorithm 3: Greedy Procedure for APS with Submodular Valuations |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | This is a theoretical paper that does not use or reference any public or open datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical data partitioning or validation splits. |
| Hardware Specification | No | The paper does not provide any specific hardware details used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details (e.g., library or solver names with version numbers) needed to replicate experiments. |
| Experiment Setup | No | This is a theoretical paper and does not include specific experimental setup details such as hyperparameters or training configurations. |