The Taub Faculty of Computer Science Events and Talks

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.