NDLI: Non-monetary fair scheduling: a cooperative game theory approach

Please wait, while we are loading the content...

Fast greedy algorithms in mapreduce and streaming

Storage and search in dynamic peer-to-peer networks

Brief announcement: truly parallel burrows-wheeler compression and decompression

IRIS: a robust information system against insider dos-attacks

Coalescing-branching random walks on graphs

Work-efficient matrix inversion in polylogarithmic time

Profitable scheduling on multiple speed-scalable processors

Cloud scheduling with setup cost

Reduced hardware transactions: a new approach to hybrid transactional memory

Broadcasting in logarithmic time for ad hoc network nodes on a line using mimo

Brief announcement: locality in wireless scheduling

SybilCast: broadcast on the open airwaves (extended abstract)

Parallel rotor walks on finite graphs and applications in discrete load balancing

Communication optimal parallel multiplication of sparse random matrices

Nonclairvoyant sleep management and flow-time scheduling on multiple processors

Efficient online scheduling for deadline-sensitive jobs: extended abstract

Recursive design of hardware priority queues

Expected sum and maximum of displacement of random sensors for coverage of a domain: extended abstract

Brief announcement: universally truthful secondary spectrum auctions

On-the-fly pipeline parallelism

Parallel graph decompositions using random shifts

Communication efficient gaussian elimination with partial pivoting using a shape morphing data layout

Reallocation problems in scheduling

Locality-aware task management for unstructured parallelism: a quantitative limit study

Drop the anchor: lightweight memory management for non-blocking data structures

On dynamics in selfish network creation

Brief announcement: online batch scheduling for flow objectives

Reducing contention through priority updates

A constant factor approximation algorithm for the storage allocation problem: extended abstract

Optimal patrolling of fragmented boundaries

Efficient scheduling to minimize calibrations

Balls-into-bins with nearly optimal load distribution

Scalable statistics counters

Brief announcement: set it and forget it - approximating the set once strip cover problem

HEX: scaling honeycombs is easier than scaling clock trees

Non-monetary fair scheduling: a cooperative game theory approach

Brief announcement: between all and nothing - versatile aborts in hardware transactional memory

Brief announcement: towards a fully-articulated pessimistic distributed transactional memory

Brief announcement: a game-theoretic model motivated by the darpa network challenge

Non-monetary fair scheduling: a cooperative game theory approach

Content Provider	ACM Digital Library
Author	Skowron, Piotr Rzadca, Krzysztof
Abstract	We consider a multi-organizational system in which each organization contributes processors to the global pool but also jobs to be processed on the common resources. The fairness of the scheduling algorithm is essential for the stability and even for the existence of such systems (as organizations may refuse to join an unfair system). We consider on-line, non-clairvoyant scheduling of sequential jobs. The started jobs cannot be stopped, canceled, preempted, or moved to other processors. We consider identical processors, but most of our results can be extended to related or unrelated processors. We model the fair scheduling problem as a cooperative game and we use the Shapley value to determine the ideal fair schedule. In contrast to the current literature, we do not use money to assess the relative utilities of jobs. Instead, to calculate the contribution of an organization, we determine how the presence of this organization influences the performance of other organizations. Our approach can be used with arbitrary utility function (e.g., flow time, tardiness, resource utilization), but we argue that the utility function should be strategy resilient. The organizations should be discouraged from splitting, merging or delaying their jobs. We present the unique (to within a multiplicative and additive constants) strategy resilient utility function. We show that the problem of fair scheduling is NP-hard and hard to approximate. However, for unit-size jobs, we present a fully polynomial-time randomized approximation scheme (FPRAS). We also show that the problem parametrized with the number of organizations is fixed parameter tractable (FPT). In cooperative game theory, the Shapley value is considered in many contexts as "the" fair solution. Our results show that, although the problem for the large number of organizations is computationally hard, this solution concept can be used in scheduling (for instance, as a benchmark for measuring fairness of heuristic algorithms).
Starting Page	288
Ending Page	297
Page Count	10
File Format	PDF
ISBN	9781450315722
DOI	10.1145/2486159.2486169
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Shapley value Fair scheduling Cooperation Inapproximability Approximation algorithms Strategy resistance Cooperative game theory Fairness
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

3 Non-monetary fair scheduling — cooperative game theory approach

A metaheuristic based fair dynamic spectrum allocation policy

The Shapley value

Fair bandwidth sharing using Shapley value

Cooperative games: core and shapley value (2007).

The Shapley value

Mechanisms for Fair Attribution

Early contributors, cooperation and fair rewards in crowdfunding

An Anytime Approximation Method for the Inverse Shapley Value Problem

Non-monetary fair scheduling: a cooperative game theory approach

Similar Documents

3 Non-monetary fair scheduling — cooperative game theory approach

A metaheuristic based fair dynamic spectrum allocation policy

The Shapley value

Fair bandwidth sharing using Shapley value

Cooperative games: core and shapley value (2007).

The Shapley value

Mechanisms for Fair Attribution

Early contributors, cooperation and fair rewards in crowdfunding

An Anytime Approximation Method for the Inverse Shapley Value Problem

Non-monetary fair scheduling: a cooperative game theory approach