Cost-Sharing Methods for Scheduling Games under Uncertainty


Christodoulou, G, Sgouritsa, A and Gkatzelis, V (2017) Cost-Sharing Methods for Scheduling Games under Uncertainty. In: Eighteenth ACM conference on Economics and Computation (ACM EC’17), 2017-6-26 - ?.

[img] Text
CostSharingMethods_EC17.pdf - Author Accepted Manuscript
Download (806kB)
[img] Text (admin)
2017-05-12T18:01:48Z.atom - Unspecified
Access to this file is embargoed until Unspecified.
Download (9kB)
[img] Text (admin)
2017-05-12T18:02:06Z.atom - Unspecified
Access to this file is embargoed until Unspecified.
Download (9kB)
[img] Text (admin)
2017-05-12T19:47:11Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T20:46:13Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T21:46:22Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T22:47:44Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T23:54:25Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T01:49:07Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T02:47:37Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T03:47:42Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T05:12:04Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T05:47:52Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T06:46:39Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T07:47:06Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T08:47:55Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T09:46:44Z.atom - Unspecified
Download (0B)

Abstract

We study the performance of cost-sharing protocols in a selfish scheduling setting with load-dependent cost functions. Previous work on selfish scheduling protocols has focused on two extreme models: omnipotent protocols that are aware of every machine and every job that is active at any given time, and oblivious protocols that are aware of nothing beyond the machine they control. The main focus of this paper is on a well-motivated middle-ground model of resource-aware protocols, which are aware of the set of machines that the system comprises, but unaware of what jobs are active at any given time. Apart from considering budget-balanced protocols, to which previous work was restricted, we augment the design space by also studying the extent to which overcharging can lead to improved performance. We first show that, in the omnipotent model, overcharging enables us to enforce the optimal outcome as the unique equilibrium, which largely improves over the Θ(log n)-approximation of social welfare that can be obtained by budget-balanced protocols, even in their best equilibrium. We then transition to the resource-aware model and provide price of anarchy (PoA) upper and lower bounds for different classes of cost functions. For concave cost functions, we provide a protocol with PoA of 1+ε for arbitrarily small ε0. When the cost functions can be both convex and concave we construct an overcharging protocol that yields PoA ≤ 2; a spectacular improvement over the bounds obtained for budget-balanced protocols, even in the omnipotent model. We complement our positive results with impossibility results for general increasing cost functions. We show that any resource-aware budget-balanced cost-sharing protocol has PoA of Θ(n) in this setting and, even if we use overcharging, no resource-aware protocol can achieve a PoA of o(√n).

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: theory of computation, quality of equilibria, cost-sharing, price of anarchy, resource-aware protocols
Depositing User: Symplectic Admin
Date Deposited: 17 May 2017 14:12
Last Modified: 19 Jan 2023 07:04
DOI: 10.1145/3033274.3085151
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007449
Dimensions
Altmetric
CORE (COnnecting REpositories)