Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling

Christoph Dürr; Łukasz Jeż; Óscar C. Vásquez

doi:10.1016/j.tcs.2017.07.020

Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling

Christoph Dürr
, Łukasz Jeż
, Óscar C. Vásquez

Discrete Mathematics

Research output: Contribution to journal › Article › Academic › peer-review

5 Citations (Scopus)

Abstract

We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the given deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.

Original language	English
Pages (from-to)	28-41
Number of pages	14
Journal	Theoretical Computer Science
Volume	695
DOIs	https://doi.org/10.1016/j.tcs.2017.07.020
Publication status	Published - 26 Sept 2017

Funding

Christoph D?rr and Oscar C. V?squez were partially supported by grant ANR-11-BS02-0015. Oscar C. V?squez was partially supported by FONDECYT grant 11140566. ?ukasz Je? was partially supported ERC consolidator grant 617951, Israeli Centers for Research Excellence (I-CORE) program, Center No.4/11, NCN grant DEC-2013/09/B/ST6/01538, and FNP Start scholarship.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

Energy management
Mechanism design
Optimization
Quality of service
Scheduling

Access to Document

10.1016/j.tcs.2017.07.020

Cite this

@article{febd4212df0c452ca41cb73de2155158,

title = "Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling",

abstract = "We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the given deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.",

keywords = "Energy management, Mechanism design, Optimization, Quality of service, Scheduling",

author = "Christoph D{\"u}rr and {\L}ukasz Je{\.z} and V{\'a}squez, \{{\'O}scar C.\}",

year = "2017",

month = sep,

day = "26",

doi = "10.1016/j.tcs.2017.07.020",

language = "English",

volume = "695",

pages = "28--41",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling

AU - Dürr, Christoph

AU - Jeż, Łukasz

AU - Vásquez, Óscar C.

PY - 2017/9/26

Y1 - 2017/9/26

N2 - We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the given deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.

AB - We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the given deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.

KW - Energy management

KW - Mechanism design

KW - Optimization

KW - Quality of service

KW - Scheduling

UR - https://www.scopus.com/pages/publications/85027448240

U2 - 10.1016/j.tcs.2017.07.020

DO - 10.1016/j.tcs.2017.07.020

M3 - Article

AN - SCOPUS:85027448240

SN - 0304-3975

VL - 695

SP - 28

EP - 41

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling

Abstract

Funding

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this