Algorithmic Signaling of Features in Auction Design

摘要

In many markets, products are highly complex with an extremely large set of features. In advertising auctions, for example, an impression, i.e., a viewer on a web page, has numerous features describing the viewer's demographics, browsing history, temporal aspects, etc. In these markets, an auctioneer must select a few key features to signal to bidders. These features should be selected such that the bidder with the highest value for the product can construct a bid so as to win the auction. We present an efficient algorithmic solution for this problem in a setting where the product's features are drawn independently from a known distribution, the bidders' values for a product are additive over their known values for the features of the product, and the number of features is exponentially larger than the number of bidders and the number of signals. Our approach involves solving a novel optimization problem regarding the expectation of a sum of independent random vectors that may be of independent interest. We complement our positive result with a hardness result for the problem when features are arbitrarily correlated. This result is based on the conjectured hardness of learning k-juntas, a central open problem in learning theory.