1 files changed, 57 insertions, 0 deletions
diff --git a/ijcai-2021-1821.txt b/ijcai-2021-1821.txt
new file mode 100644
index 0000000..e942f3a
--- /dev/null
+++ b/ijcai-2021-1821.txt
@@ -0,0 +1,57 @@
+This paper considers the problem of designing an efficient (welfare optimal)
+combinatorial auction in the value query model. Specifically, there are
+n bidders and m items, each bidder has preferences over bundles (sets) of
+items, and the goal is to allocate the items to the bidders in a way which
+(approximately) maximizes social welfare and design payments which incentivize
+truthful report of preferences.
+
+Starting from the iterative MLCA mechanism of Brero et al. (2021) (in which
+bidders' value functions are approximated by a neural network trained on their
+answers to previous queries), the mechanism designed in the present paper goes
+one step further by making use of Fourier Analysis for set functions.
+Specifically, motivated by the fact the bidders' valuation are likely to be
+approximately sparse in the Fourier domain (for a well-chosen transform), the
+mechanism finds a Fourier-sparse approximation of the neural networks
+approximating the bidder's preferences. This then requires computing the
+efficient allocation for these Fourier-sparse approximations, for which the
+authors develop an MIP-based algorithm.
+
+On the empirical side, the authors use the STATS test suite of Weiss et al
+(2017) to generate synthetic instances of combinatorial auctions. After
+evaluating the extent to which bidders' valuation are Fourier-sparse, they show
+that their proposed mechanism compares favorably to MLCA.
+
+Detailed comments
+=================
+
+The paper considers an important and difficult problem and brings a fresh and
+interesting perspective by applying ideas from Fourier analysis for set
+functions. The paper was clear and well-written.
+
+My main issue with the proposed method is a conceptual one: while I believe
+that in many situations, it is reasonable to assume that bidders' valuations
+are Fourier-sparse, I find that the Hybrid approach somewhat undermines this
+assumption by having two competing types of approximations for bidders'
+valuations: one based on Neural Networks and one based on Fourier-sparse
+functions. 
+
+While I understand that a purely Fourier-based approximation would be
+prohibitively expensive in terms of number of queries made to the bidders, the
+interaction between the Neural Network approximation and the Fourier-sparse one
+is hard to reason about: for example, it could be that even if the true value
+functions are approximately Fourier-sparse, the Neural network approximation
+which is performed first obfuscates this fact to some extent and makes it
+harder for the Fourier reconstruction to work.
+
+Overall, I would say that this hybrid approximation is not very well motivated
+from a conceptual perspective, and is only justified by the fact that it yields
+some improvement (although arguably fairly minor ones) when evaluated
+experimentally. However it seems much harder to analyze theoretically (although
+this was not a goal of the present paper) and comes at a cost in terms of
+implementation. In particular, there are now more hyperparameters to tune,
+mainly the splits l_1, to l_4 for the number of queries.
+
+In conclusion, while I believe in using more ideas from Fourier analysis in the
+design of combinatorial auctions, I am not convinced that the cost of this
+specific Hybrid instantiation both from a conceptual and implementation
+perspective is justified by the minor improvements observed experimentally.