Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems
We study cost-sharing games in real-time scheduling systems where the server’s activation cost in every time slot is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive congestion effect for the jobs) and when it...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/4/103 |
| _version_ | 1797540119264100352 |
|---|---|
| author | Eirini Georgoulaki Kostas Kollias Tami Tamir |
| author_facet | Eirini Georgoulaki Kostas Kollias Tami Tamir |
| author_sort | Eirini Georgoulaki |
| collection | DOAJ |
| description | We study cost-sharing games in real-time scheduling systems where the server’s activation cost in every time slot is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive congestion effect for the jobs) and when it is greater than one (inducing negative congestion effect for the jobs). For the former case, we provide tight bounds on the price of anarchy, and show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then turn to analyze payment mechanism with arbitrary cost-sharing, that is, when the strategy of a player includes also its payment. We show that our mechanism reduces the price of anarchy of games with <i>n</i> jobs and unit server costs from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Θ</mi><mo>(</mo><msqrt><mi>n</mi></msqrt><mo>)</mo></mrow></semantics></math></inline-formula> to 2. We also show that, for a restricted class of instances, a similar improvement is achieved for monomial server costs. This is not the case, however, for unrestricted instances of monomial costs, for which we prove that the price of anarchy remains super-constant for our mechanism. For systems with load-independent activation costs, we show that our mechanism can produce an optimal solution which is stable against coordinated deviations. |
| first_indexed | 2024-03-10T12:55:34Z |
| format | Article |
| id | doaj.art-d596d715812f441887ced62136856ef9 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T12:55:34Z |
| publishDate | 2021-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-d596d715812f441887ced62136856ef92023-11-21T11:56:09ZengMDPI AGAlgorithms1999-48932021-03-0114410310.3390/a14040103Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling SystemsEirini Georgoulaki0Kostas Kollias1Tami Tamir2National and Kapodistrian University of Athens, 157 72 Athens, GreeceGoogle Research, Mountain View, CA 94042, USAThe Interdisicplinary Center, Herzliya 46150, IsraelWe study cost-sharing games in real-time scheduling systems where the server’s activation cost in every time slot is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive congestion effect for the jobs) and when it is greater than one (inducing negative congestion effect for the jobs). For the former case, we provide tight bounds on the price of anarchy, and show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then turn to analyze payment mechanism with arbitrary cost-sharing, that is, when the strategy of a player includes also its payment. We show that our mechanism reduces the price of anarchy of games with <i>n</i> jobs and unit server costs from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Θ</mi><mo>(</mo><msqrt><mi>n</mi></msqrt><mo>)</mo></mrow></semantics></math></inline-formula> to 2. We also show that, for a restricted class of instances, a similar improvement is achieved for monomial server costs. This is not the case, however, for unrestricted instances of monomial costs, for which we prove that the price of anarchy remains super-constant for our mechanism. For systems with load-independent activation costs, we show that our mechanism can produce an optimal solution which is stable against coordinated deviations.https://www.mdpi.com/1999-4893/14/4/103real-time schedulingcost-sharing gamesprice of anarchy |
| spellingShingle | Eirini Georgoulaki Kostas Kollias Tami Tamir Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems Algorithms real-time scheduling cost-sharing games price of anarchy |
| title | Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems |
| title_full | Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems |
| title_fullStr | Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems |
| title_full_unstemmed | Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems |
| title_short | Equilibrium Inefficiency and Computation in Cost-Sharing Games in Real-Time Scheduling Systems |
| title_sort | equilibrium inefficiency and computation in cost sharing games in real time scheduling systems |
| topic | real-time scheduling cost-sharing games price of anarchy |
| url | https://www.mdpi.com/1999-4893/14/4/103 |
| work_keys_str_mv | AT eirinigeorgoulaki equilibriuminefficiencyandcomputationincostsharinggamesinrealtimeschedulingsystems AT kostaskollias equilibriuminefficiencyandcomputationincostsharinggamesinrealtimeschedulingsystems AT tamitamir equilibriuminefficiencyandcomputationincostsharinggamesinrealtimeschedulingsystems |