Universal and Tight Online Algorithms for Generalized-Mean Welfare
Authors: Siddharth Barman, Arindam Khan, Arnab Maiti4793-4800
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study fair and efficient allocation of divisible goods, in an online manner, among n agents. ... Parameterized by an exponent term p ( , 1], these means encapsulate a range of welfare functions, including social welfare (p = 1), egalitarian welfare (p ), and Nash social welfare (p 0). We present a simple algorithmic template that takes a threshold as input and, with judicious choices for this threshold, leads to both universal and tailored competitive guarantees. First, we show that one can compute online a single allocation that O( n log n)-approximates the optimal p-mean welfare for all p 1. ... We complement our positive results by establishing lower bounds to show that our guarantees are essentially tight for a wide range of the exponent parameter. ... In this paper we develop both upper bounds and lower bounds for online welfare maximization. ... Theorem 1. For the p-mean welfare maximization problem with divisible goods and scaled valuations one can compute online a single allocation that O ( n log n) approximates the optimal p-mean welfare, simultaneously for all p 1. ... Theorem 2. For any p < 1, the p-mean welfare maximization problem does not admit an online algorithm that computes optimal allocations, i.e., the competitive ratio of any online algorithm is strictly greater than one. ... Theorem 3. For any p < 0, there does not exist an online algorithm with competitive ratio strictly less than 2 (2+2/|p|) |p| 2|p|+1 for the p-mean welfare maximization problem. |
| Researcher Affiliation | Academia | Siddharth Barman1, Arindam Khan2, Arnab Maiti3 1Indian Institute of Science 2Indian Institute of Science 3Indian Institute of Technology, Kharagpur barman@iisc.ac.in, arindamkhan@iisc.ac.in, maitiarnab9@gmail.com |
| Pseudocode | Yes | Algorithm 1: ALG(Φ) |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., links to repositories or explicit statements of code release) for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or specify any publicly available datasets for training. It discusses assumptions about agent valuations within its model, such as "we assume throughout that, for every agent, the cumulative value of the entire set of goods is equal to one" and "the value vt i 1 n2". |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs; it does not describe any experiments that would require specific hardware, and therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and designs an algorithm; it does not describe an empirical experimental setup with hyperparameters or system-level training settings. It defines algorithmic parameters like the threshold Φ, but these are not experimental setup details in the typical sense. |