1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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.
|
