Abstract: We consider the problem of an auctioneer who faces the task of selling a good (drawn from a known distribution) to a set of buyers, when the seller does not have the capacity to describe to the buyers the exact identity of the good that he is selling. Instead, he must come up with a constrained signalling scheme: a (non injective) mapping from goods to signals, that satisfies the constraints of his setting. For example, the auctioneer may be able to communicate only a bounded length message for each good (equivalently, he may be constrained to using only a fixed number of signals in total). The auctioneer may also face additional exogenously imposed constrains on the signaling scheme – for example, he might be legally constrained to truthfully advertise the item being sold. Each candidate signaling scheme induces an incomplete-information game among the buyers, and the goal of the mechanism designer is to choose the signaling scheme that optimizes either welfare or revenue. We give algorithms for computing constrained signaling schemes, as well as hardness results, for both of these objectives for a variety of constrained signaling problems. This is joint work with Nicole Immorlica (Microsoft Research) and Aaron Roth (UPenn).
Bio: Shaddin Dughmi completed his PhD at Stanford University in 2011, where he was advised by Professor Tim Roughgarden. After a short postdoc at Microsoft Research, he joined USC as an assistant professor of computer Science in the Fall of 2012. His research interests are in algorithm design broadly, and in algorithmic game theory and mechanism design specifically.