Advertisement
Published in:
2010 | OriginalPaper | Chapter
Truthful Auction for CPU Time Slots
Authors : Qiang Zhang, Minming Li
Published in: Frontiers in Algorithmics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the task of designing a truthful auction mechanism for CPU time scheduling problem. There are
m
commodities (time slots)
T
= {
t
1
,
t
2
, ...,
t
m
} for
n
buyers
I
= {1,2,...,
n
}. Each buyer requires a number of time slots
s
i
for its task. The valuation function of buyer
i
for a bundle of time slots
T
i
is
v
i
(
T
i
) =
w
i
(
m
−
t
), where
t
is the last time slot in
T
i
and |
T
i
| =
s
i
. The utility
u
i
of buyer
i
is
v
i
(
T
i
) −
p
(
T
i
). It is well-known that Vickrey-Clarke-Groves (VCG) mechanism gives the incentive to bid truthfully. Although optimal social welfare is computationally feasible in CPU time scheduling problem, VCG mechanism may produce low revenue. We design an auction which also maintains the incentives for bidders to bid truthfully. In addition, we perform simulations and observe that our truthful mechanism produces more revenue than VCG on average.