Shahar Dobzinski (Weizmann Institute of Science)
Wednesday, 5.12.2012, 12:30
We generalize sealed bid auctions to accommodate combinatorial
auctions. In a sealed bid combinatorial auction each bidder sends to
the auctioneer, simultaneously with the others, a message that depends
only on his own valuation. The auctioneer decides on the allocation
based on these messages alone. The goal is to find an allocation of
the items which maximizes the social welfare. In this simultaneous
communication complexity model we ask: How much information each of
the bidders has to provide so that an allocation that approximates
well the optimal allocation can be found?
Joint work with Sigal Oren.