Resource-Aware Cost-Sharing Mechanisms with Priors



Gkatzelis, Vasilis, Pountourakis, Emmanouil and Sgouritsa, Alkmini
(2021) Resource-Aware Cost-Sharing Mechanisms with Priors. In: EC '21: The 22nd ACM Conference on Economics and Computation, 2021-7-18 - 2021-7-23, Budapest, Hungary.

[img] Text
BayesianResourceAware.pdf - Author Accepted Manuscript

Download (430kB) | Preview

Abstract

In a decentralized system with $m$ machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a function of the total load assigned to it, and some cost-sharing mechanism distributes this cost among the machine's users. The users choose a machine aiming to minimize their own share of the cost, so the cost-sharing mechanism induces a game among them. We approach this problem from the perspective of a designer who can select which cost-sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the induced games. Recent work introduced the class of \emph{resource-aware} cost-sharing mechanisms, whose decisions can depend on the set of machines in the system, but are oblivious to the total number of users. These mechanisms can guarantee low PoA bounds for instances where the cost functions of the machines are all convex or concave, but can suffer from very high PoA for cost functions that deviate from these families. In this paper we show that if we enhance the class of resource-aware mechanisms with some prior information regarding the users, then they can achieve low PoA for a much more general family of cost functions. We first show that, as long as the mechanism knows just two of the participating users, then it can assign special roles to them and ensure a constant PoA. We then extend this idea to settings where the mechanism has access to the probability with which each user is present in the system. For all these instances, we provide a mechanism that achieves an expected PoA that is logarithmic in the expected number of users.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: To appear at ACM EC 2021 conference
Uncontrolled Keywords: cs.GT, cs.GT
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 15 Jun 2021 09:35
Last Modified: 18 Jan 2023 22:35
DOI: 10.1145/3465456.3467650
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3126020