Improved Results for Stackelberg Scheduling Strategies. Page: 2 of 22
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
Improved Results for Stackelberg Scheduling Strategies
V.S. ANIL KUMAR3 MADHAV V. MARATHE3
November 12, 2001
Abstract
We continue the study initiated in [Ro01] on Stackelberg Scheduling Strategies. We are given a set of
n independent parallel machines or equivalently a set of n parallel edges on which certain flow has to be
sent. Each edge e is endowed with a latency function le (-). The setting is that of a non-cooperative game:
players choose edges so as minimize their individual latencies. Additionally, there is a single player who
control as fraction a of the total flow. The goal is to find a strategy for the leader (i.e. an assignment of
flow to indivual links) such that the selfish users react so as to minimize the total latency of the system.
Building on the recent results in [RoOl, RT00], we show the following:
1. We devise a fully polynomial approximate scheme for the problem of finding the cheapest Stackel-
berg Strategy: given a performance requirement (1 + E), our algorithm runs in time polynomial in
n and E and produces a Stackelberg strategy s, whose associated cost is within a 1 + E factor of the
optimum stackelberg strategy s*.
The result is extended to obtain a polynomial-approximation scheme when instances are restricted
to layered directed graphs in which each layer has a bounded number of vertices.
2. We then consider a two round Stackelberg strategy (denoted 2SS). In this strategy, the game consists
of three rounds: a move by the leader followed by the moves of all the followers folowed again by a
move by the leader who possibly reassigns some of the flows. We show that 2SS always dominates
the one round scheme, and for some classes of latency functions, is guaranteed to be closer to the
global social optimum. We also consider the variant where the leader plays after the selfish users
have routed themselves, and observe that this dominates the one-round scheme.
Extensions of the results to the special case when all the latency functions are linear are also presented.
Our results extend the earlier results and answer an open question posed by Roughgarden [RoO1].
'Basic and Applied Simulation Science (D-2) Los Alamos National Laboratory, P. O. Box 1663, MS M997, Los
Alamos NM 87545. The work is supported by the Department of Energy under Contract W-7405-ENG-36. Email:
anil,marathe@lanl.gov.
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Kumar, Anil; Marathe, Madhav V. & Kapernick, Richard J. Improved Results for Stackelberg Scheduling Strategies., article, January 1, 2001; United States. (https://digital.library.unt.edu/ark:/67531/metadc930620/m1/2/: accessed April 24, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.