Multistage interval scheduling games
| Autor: | Michael Hopf, Arne Herzel, Clemens Thielen |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
Computer Science::Computer Science and Game Theory Mathematical optimization 021103 operations research Supply chain management Computer science 0211 other engineering and technologies General Engineering TheoryofComputation_GENERAL 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Profit (economics) symbols.namesake 010201 computation theory & mathematics Artificial Intelligence Nash equilibrium Price of anarchy symbols Interval scheduling Price of stability Computer Science::Operating Systems Software |
| Zdroj: | Journal of Scheduling. 22:359-377 |
| ISSN: | 1099-1425 1094-6136 |
| DOI: | 10.1007/s10951-018-0568-y |
| Popis: | We study a game theoretical model of multistage interval scheduling problems in which each job consists of exactly one task (interval) for each of t stages (machines). In the game theoretical model, the machine of each stage is controlled by a different selfish player who wants to maximize her total profit, where the profit for scheduling the task of a job j is a fraction of the weight of the job that is determined by the set of players that also schedule their corresponding task of job j. We provide criteria for the existence of pure Nash equilibria and prove bounds on the Price of Anarchy and the Price of Stability for different social welfare functions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink