Send mixed signals : earn more, work less

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 -