This paper introduces a general framework to find a truthful, (approximately)
revenue-maximizing combinatorial auction mechanism inside a given class of
mechanisms. A typical situation where this is useful is when considering
a parametrized class of mechanisms for which the optimal value of the parameter
depends on the (unknown) distribution of bidders and thus needs to be learned.

The framework is based on the general idea of random sampling, where we learn
the optimal mechanism on a portion of the population but apply it to another
portion. The main idea of the framework—which can be thought of as a way to
make it more robust to variability in the bidders' population—is to first draw
a set of participatory bidders and then learn on the complement set of bidders
by repeatedly drawing samples of bidders from the complement set and finding
a mechanism which maximizes revenue *on average* over the samples. The
mechanism thus identified is then applied to the set of participatory bidders.

In addition to the introduction of this general framework, the main
contribution of the papers are:

1. a general bound on the revenue of the mechanisms output by this method,
   which depends on various parameters quantifying the complexity of the
   auction class and the variability in the population of bidders.

2. a specific instantiation of the framework to a new class of auctions
   introduced by the authors, bundling-boosted auctions, for which it is
   possible to quantify more finely the various parameters described in item 1.

3. an algorithm to efficiently find the mechanism maximizing expected revenue
   (as required by the framework) for sparse bundling-boosted auctions.

Detailed comments
=================

The problem considered in this paper is important and the paper brings a nice
unifying perspective to it by the introduction of a general framework and
analysis of its performance through learning-theoretic complexity measures.
Furthermore, the paper is very clear and nicely written (despite the sadly
restrictive 7 page limit…).

* an important feature of the framework, is that it completely gives up on
  extracting any revenue from non-participatory bidders. While I understand
  that this might be a necessary feature given the generality of the scheme,
  some prior work partially avoid this loss, albeit in much more restrictive
  settings. Maybe more could be said as a motivation about the trade-off
  between generality of the scheme and how much revenue we can hope to extract.

* relatedly, I was a bit surprised to see that the bounds on the revenue of the
  scheme were expressed with respect to the efficient allocation on the entire
  population. Why use this as a benchmark, as opposed to, for example, the
  optimal revenue that could be obtained on the entire population? This might
  be standard in this line of work but adding a sentence of two about this
  choice might be helpful.

* a drawback of the scheme, which again might be due to its generality is that
  its guarantees depend of parameters which might be hard to compute or even
  bound in practice. Although the authors try to explicitate them for specific
  auction classes, they still remain somewhat opaque. This is particularly true
  of the partition discrepancy quantity.

* the scheme is reminiscent of the bootstrap method in statistics where
  multiple samples are drawn with replacement from the same initial sample to
  account for variability in the population. Maybe this could be mentioned
  somewhere to connect the paper to the broader statistics/learning literature.