Efficient Truthful Scheduling and Resource Allocation through Monitoring



Fotakis, Dimitris, Krysta, Piotr and Ventre, Carmine
(2021) Efficient Truthful Scheduling and Resource Allocation through Monitoring. In: Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21), 2021-2-2 - 2021-2-9, Vancouver, Canada.

[img] Text
AAAI-2021(final)_Elements.pdf - Author Accepted Manuscript

Download (287kB) | Preview

Abstract

<jats:p>We study the power and limitations of the Vickrey-Clarke-Groves mechanism with monitoring (VCGmon) for cost minimization problems with objective functions that are more general than the social cost. 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. However, we show that VCGmon results in computationally efficient approximately truthful mechanisms for binary covering problems.</jats:p>

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 11 Feb 2021 11:13
Last Modified: 15 Mar 2024 14:52
DOI: 10.1609/aaai.v35i6.16683
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3115492