2010 | OriginalPaper | Buchkapitel
Specializations and Generalizations of the Stackelberg Minimum Spanning Tree Game
verfasst von : Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
Stackelberg Minimum Spanning Tree
(
StackMST
) game is a network pricing (bilevel) optimization problem. The game is played by two players on a graph
G
= (
V
,
E
), whose edges are partitioned into two sets: a set
R
of
red
edges (inducing a spanning tree of
G
) with a fixed non-negative real cost, and a set
B
of
blue
edges which are instead priced by a
leader
. This is done with the final intent of
maximizing
a revenue that will be returned for their purchase by a
follower
, whose goal in turn is to select a minimum spanning tree of
G
.
StackMST
is known to be
APX
-hard already when the number of distinct red costs is 2, as well as min {
k
, 1 + ln
β
, 1 + ln
ρ
}-approximable, where
k
is the number of distinct red costs,
β
is the number of blue edges selected by the follower in an optimal pricing, and
ρ
is the maximum ratio between red costs. In this paper we analyze some meaningful specializations and generalizations of
StackMST
, which shed some more light on the computational complexity of the game. More precisely, we first show that if
G
is complete, then the following holds: (i) if there are only 2 distinct red costs, then the problem can be solved optimally (this contrasts with the corresponding
APX
-hardness of the general problem); (ii) otherwise, the problem can be approximated within 7/4 +
ε
, for any
ε
> 0. Afterwards, we define a natural extension of
StackMST
, namely that in which blue edges have a non-negative
activation
cost associated, and the leader has a global activation budget that must not be exceeded, and, after showing that the very same approximation ratio as that of the original game can be achieved, we prove that if the spanning tree induced by the red edges has
radius
h
(in terms of number of edges), then the problem admits a (2
h
+
ε
)-approximation algorithm.