Efficient Truthful Scheduling and Resource Allocation through Monitoring
Authors: Dimitris Fotakis, Piotr Krysta, Carmine Ventre5423-5431
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We identify a simple and natural sufficient condition for VCGmon to be truthful for general objectives. As a consequence, we obtain that for any cost minimization problem with non-decreasing objective µ, VCGmon is truthful, if the allocation is Maximal-in-Range and µ is 1-Lipschitz (e.g., µ can be the Lp-norm of the agents costs, for any p 1 or p = ). We apply VCGmon to scheduling on restricted-related machines and obtain a polynomial-time truthful-in-expectation 2-approximate (resp. O(1)-approximate) mechanism for makespan (resp. Lp-norm) minimization. Moreover, applying VCGmon, we obtain polynomial-time truthful O(1)-approximate mechanisms for some fundamental bottleneck network optimization problems with single-parameter agents. On the negative side, we provide strong evidence that VCGmon could not lead to computationally efficient truthful mechanisms with reasonable approximation ratios for binary covering social cost minimization problems. |
| Researcher Affiliation | Academia | Dimitris Fotakis, 1 Piotr Krysta, 2 Carmine Ventre 3 1 National Technical University of Athens, Greece 2 University of Liverpool, UK 3 King s College London, UK |
| Pseudocode | Yes | Algorithm 1: The generic bottleneck algorithm. 1 procedure bottleneck(G, GC, t) ... Algorithm 2: The test procedure. 1 procedure test(G, G, 2) ... |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and algorithm design; it does not use or provide access information for a public dataset for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not report on empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not detail an experimental setup with hyperparameters or specific training configurations. |