Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A New Derandomization of Auctions
verfasst von : Oren Ben-Zwi, Ilan Newman, Guy Wolfovitz
Erschienen in: Algorithmic Game Theory
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
Let
A
be a randomized, unlimited supply, unit demand, single-item auction, which given a bid-vector
b
∈ [
h
]
n
, has expected profit
${\mathbb E}[P(b)]$
. Aggarwal et al. showed that given
A
, there exists a deterministic auction which given a bid-vector
b
, guarantees a profit of
${\mathbb E}[P(b)]/4 - O(h)$
. In this paper we show that given
A
, there exists a deterministic auction which given a bid-vector
b
of length
n
, guarantees a profit of
${\mathbb E}[P(b)]- O(h\sqrt{n \ln hn})$
. As is the case with the construction of Aggarwal et al., our construction is not polynomial time computable.