Fair and Efficient Online Allocations with Normalized Valuations
Authors: Vasilis Gkatzelis, Alexandros Psomas, Xizhi Tan5440-5447
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | To prove our results, we leverage the fact that our algorithms have a closed-form expression for the agents allocations and utilities. We can use this fact and write a mathematical program that computes the worst-case approximation to the optimal welfare over all instances. We use variables vt for the value of agent 1 for item t and λt for the ratio between agents values. Even though this program is not itself convex (so at first glance it s unclear how useful it is), we show that under a suitable choice of variables and constraints, fixing some of the variables (i.e. treating them as constants) gives a linear program with respect to the remaining variables. |
| Researcher Affiliation | Academia | Vasilis Gkatzelis,1 Alexandros Psomas, 2 Xizhi Tan 1 1 Drexel University 2 Purdue University gkatz@drexel.edu, apsomas@cs.purdue.edu, xizhi@drexel.edu |
| Pseudocode | No | The paper describes algorithms using mathematical expressions and prose but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use datasets or specify publicly available ones for training. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention specific hardware used for experiments. |
| Software Dependencies | No | The paper mentions using 'numerical solvers' for proofs but does not specify any software names with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and algorithm properties, not on specific experimental setup details like hyperparameters or training configurations. |