Core-Pricing in Large Multi-Object Auctions : A Market Design for Selling TV-Ads

Motivated by markets for television advertising time-slots, we introduce a new combinatorial auction format, including a general method for approximating core-selecting payments for hard problems. Given the size and complexity of ad markets in practice, an enumerative XOR bidding language (widely discussed in the literature and used in recent government spectrum auctions) grows too quickly to be practical. We therefore propose a compact bidding language for coverage or demographic reach, and investigate the resulting winner determination (a form of multi-knapsack problem) using numerical experiments. For realistic instances of the problem, very good solutions can be found relatively quickly, though closing the integrality gap to find marginally better solutions or prove optimality can take a prohibitively large amount of time. Our subsequent adaptation of the core-selecting payment technique to this environment of nearly-optimal optimization results is a new, practically viable paradigm by which competitive market outcomes can be achieved despite computational limitations