Online mechanism design (randomized rounding on the fly)

Piotr Krysta; Berthold Vöcking

doi:10.1007/978-3-642-31585-5_56

Online mechanism design (randomized rounding on the fly)

Piotr Krysta, Berthold Vöcking

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

38 Scopus citations

Abstract

We study incentive compatible mechanisms for combinatorial auctions (CAs) in an online model with sequentially arriving bidders, where the arrivals' order is either random or adversarial. The bidders' valuations are given by demand oracles. Previously known online mechanisms for CAs assume that each item is available at a certain multiplicity b∈>∈1. Typically, one assumes b∈=∈Ω(logm), where m is the number of different items. We present the first online mechanisms guaranteeing competitiveness for any multiplicity b∈≥∈1. We introduce an online variant of oblivious randomized rounding enabling us to prove competitive ratios that are close to or even beat the best known offline approximation factors for various CAs settings. Our mechanisms are universally truthful, and they significantly improve on the previously known mechanisms.

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Publisher	Springer Verlag
Pages	636-647
Number of pages	12
Edition	PART 2
ISBN (Print)	9783642315848
DOIs	https://doi.org/10.1007/978-3-642-31585-5_56
State	Published - 2012
Externally published	Yes
Event	39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom Duration: Jul 9 2012 → Jul 13 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	7392 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/Territory	United Kingdom
City	Warwick
Period	7/9/12 → 7/13/12

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-31585-5_56

Cite this

Krysta, P., & Vöcking, B. (2012). Online mechanism design (randomized rounding on the fly). In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings (PART 2 ed., pp. 636-647). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7392 LNCS, No. PART 2). Springer Verlag. https://doi.org/10.1007/978-3-642-31585-5_56

Online mechanism design (randomized rounding on the fly). / Krysta, Piotr; Vöcking, Berthold.
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 2. ed. Springer Verlag, 2012. p. 636-647 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7392 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Krysta, P & Vöcking, B 2012, Online mechanism design (randomized rounding on the fly). in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 7392 LNCS, Springer Verlag, pp. 636-647, 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012, Warwick, United Kingdom, 7/9/12. https://doi.org/10.1007/978-3-642-31585-5_56

Krysta P, Vöcking B. Online mechanism design (randomized rounding on the fly). In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 2 ed. Springer Verlag. 2012. p. 636-647. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-31585-5_56

Krysta, Piotr ; Vöcking, Berthold. / Online mechanism design (randomized rounding on the fly). Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 2. ed. Springer Verlag, 2012. pp. 636-647 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{7299b4ba70ec49ca8a6bc5c9c2f9b677,

title = "Online mechanism design (randomized rounding on the fly)",

abstract = "We study incentive compatible mechanisms for combinatorial auctions (CAs) in an online model with sequentially arriving bidders, where the arrivals' order is either random or adversarial. The bidders' valuations are given by demand oracles. Previously known online mechanisms for CAs assume that each item is available at a certain multiplicity b∈>∈1. Typically, one assumes b∈=∈Ω(logm), where m is the number of different items. We present the first online mechanisms guaranteeing competitiveness for any multiplicity b∈≥∈1. We introduce an online variant of oblivious randomized rounding enabling us to prove competitive ratios that are close to or even beat the best known offline approximation factors for various CAs settings. Our mechanisms are universally truthful, and they significantly improve on the previously known mechanisms.",

author = "Piotr Krysta and Berthold V{\"o}cking",

year = "2012",

doi = "10.1007/978-3-642-31585-5\_56",

language = "English (US)",

isbn = "9783642315848",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "PART 2",

pages = "636--647",

booktitle = "Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings",

edition = "PART 2",

note = "39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 ; Conference date: 09-07-2012 Through 13-07-2012",

}

TY - GEN

T1 - Online mechanism design (randomized rounding on the fly)

AU - Krysta, Piotr

AU - Vöcking, Berthold

PY - 2012

Y1 - 2012

N2 - We study incentive compatible mechanisms for combinatorial auctions (CAs) in an online model with sequentially arriving bidders, where the arrivals' order is either random or adversarial. The bidders' valuations are given by demand oracles. Previously known online mechanisms for CAs assume that each item is available at a certain multiplicity b∈>∈1. Typically, one assumes b∈=∈Ω(logm), where m is the number of different items. We present the first online mechanisms guaranteeing competitiveness for any multiplicity b∈≥∈1. We introduce an online variant of oblivious randomized rounding enabling us to prove competitive ratios that are close to or even beat the best known offline approximation factors for various CAs settings. Our mechanisms are universally truthful, and they significantly improve on the previously known mechanisms.

AB - We study incentive compatible mechanisms for combinatorial auctions (CAs) in an online model with sequentially arriving bidders, where the arrivals' order is either random or adversarial. The bidders' valuations are given by demand oracles. Previously known online mechanisms for CAs assume that each item is available at a certain multiplicity b∈>∈1. Typically, one assumes b∈=∈Ω(logm), where m is the number of different items. We present the first online mechanisms guaranteeing competitiveness for any multiplicity b∈≥∈1. We introduce an online variant of oblivious randomized rounding enabling us to prove competitive ratios that are close to or even beat the best known offline approximation factors for various CAs settings. Our mechanisms are universally truthful, and they significantly improve on the previously known mechanisms.

UR - https://www.scopus.com/pages/publications/84884194496

UR - https://www.scopus.com/inward/citedby.url?scp=84884194496&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31585-5_56

DO - 10.1007/978-3-642-31585-5_56

M3 - Conference contribution

AN - SCOPUS:84884194496

SN - 9783642315848

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 636

EP - 647

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

PB - Springer Verlag

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -

Online mechanism design (randomized rounding on the fly)

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this