Send mixed signals : earn more, work less

Peter Bro Miltersen; Or Sheffet

doi:10.1145/2229012.2229033

Send mixed signals : earn more, work less

Peter Bro Miltersen, Or Sheffet

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Abstract

Emek et al presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) pure signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal mixed signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.

Original language	English
Title of host publication	EC '12 Proceedings of the 13th ACM Conference on Electronic Commerce
Editors	Boi Faltings, Kevin Leyton-Brown, Panos Ipeirotis
Number of pages	14
Publisher	Association for Computing Machinery
Publication date	2012
Pages	234-247
ISBN (Print)	978-1-4503-1415-2
DOIs	https://doi.org/10.1145/2229012.2229033
Publication status	Published - 2012
Event	ACM Conference on Electronic Commerce - Valencia, Spain Duration: 4 Jun 2012 → 8 Jun 2012 Conference number: 13

Conference

Conference	ACM Conference on Electronic Commerce
Number	13
Country/Territory	Spain
City	Valencia
Period	04/06/2012 → 08/06/2012

Access to Document

10.1145/2229012.2229033

Cite this

@inproceedings{c982e103fe1d465aa0cd65c2381751cb,

title = "Send mixed signals : earn more, work less",

abstract = "Emek et al presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) pure signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal mixed signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.",

author = "Miltersen, {Peter Bro} and Or Sheffet",

year = "2012",

doi = "10.1145/2229012.2229033",

language = "English",

isbn = "978-1-4503-1415-2 ",

pages = "234--247",

editor = "Faltings, {Boi } and Leyton-Brown, {Kevin } and { Ipeirotis}, Panos",

booktitle = "EC '12 Proceedings of the 13th ACM Conference on Electronic Commerce",

publisher = "Association for Computing Machinery",

address = "United States",

note = "ACM Conference on Electronic Commerce, EC ; Conference date: 04-06-2012 Through 08-06-2012",

}

Send mixed signals : earn more, work less. / Miltersen, Peter Bro; Sheffet, Or.
EC '12 Proceedings of the 13th ACM Conference on Electronic Commerce . ed. / Boi Faltings; Kevin Leyton-Brown; Panos Ipeirotis. Association for Computing Machinery, 2012. p. 234-247.

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Send mixed signals : earn more, work less

AU - Miltersen, Peter Bro

AU - Sheffet, Or

N1 - Conference code: 13

PY - 2012

Y1 - 2012

N2 - Emek et al presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) pure signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal mixed signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.

AB - Emek et al presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) pure signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal mixed signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.

U2 - 10.1145/2229012.2229033

DO - 10.1145/2229012.2229033

M3 - Article in proceedings

SN - 978-1-4503-1415-2

SP - 234

EP - 247

BT - EC '12 Proceedings of the 13th ACM Conference on Electronic Commerce

A2 - Faltings, Boi

A2 - Leyton-Brown, Kevin

A2 - Ipeirotis, Panos

PB - Association for Computing Machinery

T2 - ACM Conference on Electronic Commerce

Y2 - 4 June 2012 through 8 June 2012

ER -

Send mixed signals : earn more, work less

Abstract

Conference

Access to Document

Fingerprint

Cite this