Mode Connectivity in Auction Design
Authors: Christoph Hertrich
Yixin Tao
László A. Végh
Venue: NeurIPS 2023 poster (2023)
Keywords: Differentiable Economics
Mechanism Design
Neural Network Theory
Mode Connectivity
RochetNet
TL;DR: We prove that for certain neural networks used in mechanism design, two local optima are always connected via an almost optimal path.

Abstract: Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that they satisfy mode connectivity, i.e., locally optimal solutions are connected by a simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima. Mode connectivity has been recently investigated as an intriguing empirical and theoretically justifiable property of neural networks used for prediction problems. Our results give the first such analysis in the context of differentiable economics, where neural networks are used directly for solving non-convex optimization problems.

Mode Connectivity in Auction Design
Christoph Hertrich
Department of Mathematics
London School of Economics and Political Science, UK c.hertrich@
Yixin Tao
ITCS, Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University Finance and Economics, China taoyixin@mail. shufe edu.
László A. Végh
Department of Mathematics
London School of Economics and Political Science, UK 1. veghelee.ac...... ac.
Abstract
Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and generalized version for affine maximizer auctions. We prove that they satisfy mode connectivity, i.c., locally optimal solutions are connected by simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima. Mode connectivity has been recently investigated as intriguing empirical and theoretically justifiable property neural networks used for prediction problems. Our results give the first such analysis in the context of differentiable economies, where neural networks are used directly for solving non-convex optimization problems.
Introduction
Auction design is problem in mechanism design, with immense applications in electronic commerce (such as sponsored search auctions) as well as in the public sector (such as spectrum auctions). In revenue maximizing auction, the auctioneer needs design mechanism allocate resources to buyers, and set prices in order to maximize the expected revenue. The buyers' preferences private and they may behave strategically by misreporting them. For this reason, often desirable to devise dominant strategy incentive compatible (DSIC) and individually rational (IR) mechanisms. By definition, in DSIC mechanism, dominant strategy for the buyers report the true valuations; in an IR mechanism, each participating truthful buyer receives a nonnegative payoff.
We focus on DSIC and IR mechanisms that maximize the expected revenue, assuming that the buyers' preferences drawn from distribution known the auctioneer. A classical result of
Moved to Université Libre de Bruxelles, Belgium, and Koethe-Unniversing Frankfurt, Germany, after submission of this article.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Myerson [981 provides the optimal mechanism for the case of single item and arbitrary number of buyers. Finding the optimal mechanisms for more general settings is a tantalizingly difficult problem.
We refer the reader to the surveys by |Rochet and Stole [2003] Manelli and Vincent [007]] and
Daskalakis [015] for partial results and references.
particular, no analytic solution is known even
for two items and two buyers. Selling multiple items to single buyer is computationally intractable
[Daskalakis et al. 2014]. Already for two items and a single buyer, the description of the optimal
mechanism may be uncountable (Daskalakis et al., 2013). Recent work gives number of important partial characterizations, e.g. Daskalakis et al.) [013]] Giannakopoulos and Koutsoupias [0014), as
well as results for weaker notions of Bayesian incentive compatibility, e.g. Cai et al. 2012b 2013
Bhalgat et al. [2013).
Comitzer and Sandholm 2002 2004] proposed the approach of automated mechanism design to use
optimization and computational methods to obtain (near) optimal mechanisms for specific problems; see also Sandholmm and Likhodedov 20155. An active recent area of research uses machine learning tools. In particular, Dütting et al. 2019] designed and trained neural networks to automatically find optimal auctions. They studied two network architectures, and showed that several theoretically optimal mechanisms can be recovered using this approach, as well as interesting new mechanisms can be obtained. The first network they studied is RochetNes. This is a simple two-layer neural network applicable to the single buyer case, leveraging Rochet|s [1987] characterization of the optimal mechanism. The second network, RegretNer does not require such a characterization and is applicable for multiple buyers; however, it only provides approximate incentive compatibility.
Dütting et al. [2199] coined the term 'differentiable economics' for this approach, and there has been significant further work this direction. These include designing auctions for budget constrained buyers (Feng et al., 20188: multi multi-facility location Golowich et al. [2018); balancing fairness and revenue objectives [uuo et al. 2020]; incorporating non-linear utility functions and other networks trained from interaction data (Shen et al., 2019 designing evenue-maximizing auctions with
differentiable matchings [Curry et al. 2022a contextual auction design [Duan et al. 2022]; designing
taxation policies (Zheng et al. 2022 and more.
The purpose of this work is to supply theoretical evidence behind the success of neural networks in differentiable economics. The revenue is a highly non-convex function of the parameters in the neural network. Curiously, gradient approaches seem to recover globally optimal auctions despite this non-convexity. Similar phenomena have been studied more generally in the context of deep networks, and theoretical explanations have been proposed, in particular, overparametrization [Allen-Zhu et al., 2019
Du et al. 2019]
Mode connectivity Recent work has focused on striking property of the landscape of loss functions of deep neural networks: local optimal solutions (modes) found by gradient approaches are connected by simple paths in the parameter space. We provide an informal definition of mode connectivity here.
Definition 1 (s-mode connected (informal)). We say that nwo solutions are e-mode connected, if they are connected by continuous path of solutions, such that the loss function does not worsen by more than & compared to one of the end points on the entire path.
This phenomenon was identified by Garipov et al. [218]] and by Draxler et al. [2018]. Mode connectivity can help to explain the empirical performance of stochastic gradient descent (sgd) (or ascent, in case of revenue maximization). To some extent, mode connectivity prevents a poor local minimal valley region on the function value, from which the sgd method cannot escape easily. Suppose such a bad local minimum exists. Then mode connectivity implies that there exists a path from this bad local minimum to a global minimum on which the loss function does not significantly increase. Therefore, the intuition is that from every bad local minimum, a (stochastic) gradient method would eventually be able to find way to escape. However, we would like to emphasize that mode connectivity does not provide a formal proof of the success of sgd. It only provides a useful intuition of why sgd does not completely trapped in local optima.
Kuditipudi et al. [019 gave strong theoretical arguments for mode connectivity. They introduce the notion of E-dropout stability: solutions to neural network such that in each layer, one can remove
"MenuNet, developed by (Shen et al. 2019). also encodes menu items as RochetNet. However, unlike RochetNet's iss approach of repeatedly sampling valuations from the underlying distribution, MenuNet discretizes the buyer's valuation space into discrete values.
2

---

at least half the neurons and rescale the remaining units such that the loss function increases by at most E. Solutions that are e-dropout stable are then shown be E-mode connected. Moreover, they show that noise stability (see e.g., Arora et al. (2018) implies dropout stability, and hence, mode connectivity. Nguyen| [2019] showed mode connectivity when there is a hidden layer larger than the training dataset. [Shevchenko and Mondelli] (2020) shows that stochastic gradient descent solutions to sufficiently overparametrized neural networks are dropout stable even if we only keep a small, randomly sampled set of neurons from each layer.
1.1 Our contributions
RochetNet In this paper, we first establish mode connectivity properties of RochetNer, the archi- tecture in Dütting et al. (2019) for multiple items and a single buyer. These networks have a single hidden layer, corresponding to the menu. Within this hidden layer, each neuron directly corresponds to an option in the menu: which contains an allocation and a price offered to the buyer (see Figure J. The buyer is assigned the single option, including the allocation and the price, maximizing the buyer's utility. Such an option is called active for the buyer. The loss function of RochetNer the revenue, the expected price paid by the buyer. Despite its simplicity, the experiments on RochetNer in Dütting et al. [2019) gave impressive empirical results in different scenarios. For example, in the experiments with up to six items and uniform value distributions. RochetNer achieves almost the same revenue (99.9%) as the Straight-Jacket Auctions Giannakopoulos and Koutsoupias (2018), which are known to be optimal in this case. This success not limited to single example, RochetNer also consistently performs well in other scenarios, including when infinite menu size is necessary. Furthermore. Dütting et al. 2019 demonstrated the usefulness of RochetNer in discovering optimal auctions in situations that were previously unexplored from a theoretical perspective.
First, in Theorem 9 we show that for linear utilities, e-mode connectivity holds between two solutions that are e-reducible: out of the K ++1 I menu options (neurons), there exists a subset of at most /K + II containing an active option for the buyer with probability least 1 E. Assuming that the valuations are normalized such that the maximum valuation of any buyer is at most one, it follows that if we remove all other options from the menu, most E of the expected revenue lost. The assumption of being e-reducible is stronger than e-dropout stability that only drops a constant fraction of the neurons. At the same time, experimental results in Dütting et al. [019)] show evidence of this property being satisfied in practice. They experimented with different sized neural networks in setting when the optimal auction requires infinite menu size. Even with 10, 000 neurons available, only 59 options were active, i.e., used at least once when tested over large sample size. We note that this property also highlights an advantage of RochetNel over RegretNei and other similar architectures: instead of a black-box neural network, it returns compact, easy to understand representation of a mechanism.
Our second main result (Theorem 10p shows that for n items and linear utilities, if the number of menu options K is sufficiently large, namely, (2/z)tm, then e-mode connectivity holds between any two solutions for any underlying distribution. The connectivity property holds pointwise: for any particular valuation profile, the revenue may decrease by at most along the path. A key tool in this e-mode connectivity result is discretization technique from Dughmi et al. [2014). We note that such a mode connectivity result can be expected to need a large menu size. In Appendix example with two disconnected local maxima for K 1.
C
we present an
Affine Maximizer Auctions We also extend our results and techniques to neural networks for affine maximizer auctions (AMA) studied in Curry et al. [2022b). This a generalization of RochetNet for multi-buyer scenarios. It can also be seen as weighted variant of the Vickrey Vickrey-Clarke- Starke-Groves, (VCG) mechanism [Vickrey] 1961 Clarke 1971 Groves 1973). AMA offers various allocation options. For given valuation profile, the auctioneer chooses the allocation with the highest weighted sum of valuations, and computes individual prices for the buyers; the details are described in Section 2.2
AMA is DSIC and IR, however, is not rich enough to always represent the optimal auction.
For AMA networks, we show similar results (Theorem 13 and [4p as for RochetNet. We first prove e-mode connectivity holds between two solutions that are E- E-reducible (see Definition IT) Curry ct al. 2022b) provides evidence of this property being satisfied in practice, observing (in Sec. 7.1) "Moreover, we found that starting out with a large number of parameters improves performance, even though by the end of training only a finy number of these parameters were actually used.". ". Secondly, also show that if the number of menu options K is sufficiently large, namely, (16m²) /22 2)2mm
3

---

then e-mode connectivity holds pointwise between any two solutions. That is, it is valid for any underlying distribution of valuations, possibly correlated between different buyers.
Relation to previous results mode connectivity Our results do not seem to be deducible from previous mode connectivity results, as we outline as follows. Previous literature on mode connectivity investigated neural networks used for prediction. The results in Kuditipudi et al. [2019), Nguyen [2019] Shevchenko and Mondelli [2020) and other papers crucially rely on the properties that the networks minimize a convex loss function between the predicted and actual values, and require linear transformations in the final layer. RochetNet and AMA networks are fundamentally different. The training data does not come as labeled pairs and these network architectures are built directly for solving an optimization problem. For an input valuation profile, the loss function is the negative revenue of the auctioneer. In RochetNet, this is obtained as the negative price of the bundle; for AMA it requires an even more intricate calculation. The objective is to find parameters of the neural network such that the expected revenue is as large as possible. The menu options define a piecewise linear surface of utilities, and the revenue in RochetNet can be interpreted as the expected bias of the piece corresponding to a randomly chosen input.
Hence, the landscape of the loss function is fundamentally different from those analyzed in the above mentioned works. The weight interpolation argument that shows mone-connettivity from dropout stability is not applicable in this context. The main reason is that the loss function is not a simple function of the output of the network, but is defined by choosing the price of the argmax option. We thus need a more careful understanding of the piecewise linear surfaces corresponding to the menus.
Significance for Practitioners We see the main contribution of our paper in explaining the empirical success and providing theoretical foundations for already existent practical methods, and not in inventing new methods. Nevertheless, two insights a practitioner could use are as follows: (i) It is worth understanding the structure of the auction in question. If one can, e.g., understand whether e-reducibility holds for a particular auction, this might indicate whether RochetNet or AMA are good methods to apply to this particular case. (ii) Size helps: If one encounters bad local optima, increasing the menu size and rerunning RochetNet or AMA might be potential fix and will eventually lead to a network satisfying mode connectivity.
2 Auction Settings
We consider the case with buyers and one seller with divisible items each in unit supply. Each buyer has an additive valuation function (5) := İjes U,j, where fij E V represents the valuation of the buyer on item j and V is the set of possible valuations. Throughout the paper, we normalize the range to the unit simplex: we assume V = [0, 1]. and |0:]h = Eg Dig S 1 for every buyer i. With
slight abuse of notation, we let v = (V11, V12 Viy. ..... Umn) and U; = (Ua1. 022, ... van) The buyers' valuation profile is drawn from distribution F E P(Vmx"). Throughout, assume that the buyers have quasi- minsi-linearnnn utilities: if a buyer with valuation v; receives an allocation [0, 1 price p. their utility is v. x-p.
The seller has access to samples from the distribution F, and wants to sell these items to the buyers through DSIC and IR auction and maximize the expected revenue. In the auction mechanism, the i-th bidder reports a bid b, E [0, 1]". The entire bid vector E [0, 1]mxx will be denoted as b (bi...., bm)) (b;, b-i), where b-; represents all the bids other than buyer i. In a DSIC mechanism, it is dominant strategy for the agents to report 63 = Ug i... reveal their true preferences.
Definition 2 (DSIC and IR auction). An auction mechanism requires the buyers to submit bids b, E [0, 1]", and let b b= (by,..., .,.....,. dm). The outpul is a set of allocations x(b) = (a1 (b),... Fm (b)), rr(bb) E [0, 11",, and prices p(b) (pr (b)...., pmmb))) (b)) R Since there is unit supply of each item, we require E, (b) < 1. where Zzy (b) is the allocation of buyer of item j.
'There exists weaker notion of incentive compatibility: Bayesian incentive compatible (BIC). a BIC mechanism, it is a dominant strategy for the buyers to report the true valuations if all other buyers also report truthfully. This paper focuses on DISC mechanisms, as DSIC is considered to be more robust than BIC, which assumes common knowledge of buyers' distributions on valuations.

---

(i) An auction is dominant strategy incentive compatible (DSIC) if u. (i(us,bb)) p:(er,b,)) T r;;b,, b-4) - p:(6,, for any buyer i and any bid b = (b,, b-i).
(ii) An auction is individually rational (IR) if of 22(22, b-i) Pa( b_.) 2 0.
The revenue of a DSIC and IR auction is
Rev EN Emccol
2.1 Single Buyer Auctions: RochetNet
Dütting et al. [2019] proposed RochetNet as a DISC and IR auction for the case of a single buyer.
We omit the subscript for buyers in this case. A (possibly infinite sized) menu M comprises set
In each option (xx(k) pp))), x(()) [0, 1] represents the amount of items, and pl*) E IR+ represents the price. We assume that 0 E K, and
of options offered to the buyer: M = {2x
)) (()))))))))))))))))))
(z) p (0. 0) to guarantee IR. We call this the default option, whereas all other options
called regular options. We will use K to denote the number of regular options; thus, [K] = K + 1.
A buyer submits bid b E [0, 1J" representing their valuation, and is assigned to option k(b) E IC that maximizes the utility
(b) arg max b 22(k) (k))
kEÆ.
This is called the active option for the buyer. Note that option 0 guarantees that the utility is nonnegative, implying the IR property. It is also easy to see that such an auction DSIC. Therefore, one can assume that 6 = v, i.e., the buyer submits their true valuation; or equivalently, the buyer is allowed to directly choose among the menu options one that maximizes their utility. Moreover, follows from Rochet [987] that every DSIC and IR auction for single buyer can be implemented with (possibly infinite size) menu using an appropriate tie-breaking rule.
Given menu M, the revenue is defined as
Rev(M) = E [pttws)]
RochetNet RochetNet (see Figure 1 is neural network with three layers: an input layer (n neurons), a middle layer (K neurons), and an output layer (1 neuron):
1. the input layer takes an n-dimensional bid b E V", and sends this information to the middle layer;
2. the middle layer has K neurons. Each neuron represents regular option in the menu M, which has parameters (xk)) E [0, 1]" and ( E R,, where (k) E [0, 1J" represents the allocation of option & and pl represents the price option Neuron & maps from E V
to (R)) (A)), i.e., the utility of the buyer when choosing option k;
3. the output layer receives all utilities from different options and maximizes over these options and O: max (max { ((x(k))T T (.))) 03.
We will use Rev (M) to denote the revenue of the auction with menu options I. = (0, .,, where 0 represents the default option (0, 0).
The training objective for the RochetNet to maximize the revenue Rev(M), which is done by stochastic gradient ascent. Note, however, that the revenue is the price of argmax option, which makes it a non-continuout function the valuations. For this reason, Dütting et al.] [2019] use a softmaxxapproxximatin of the argmax their loss function instead. However, argmax is used for testing. In Appendix B we bound the difference between the revenues computed with these two different activation functions, assuming that the probability density function of the distribution F admits finite upper bound. Lemma 19 shows that the difference between the revenues for sofimax and argmax roughly inverse proportional to the parameter Y of the softmax function. This allows the practitioner to interpolate between smoothness of the loss function and provable quality of the softmax approximation by tuning the parameter Y.
We assume that ties are broken in favor of higher prices, but it is not hard to see that our results transfer to other tie- breaking rules, too. See also the discussion in Section B.2 of Babaioff et al. 2002
5

---

Pi
b2
x (2)
P2
ba
(x)
Pk
Figure I: RochetNet: this architecture maps the bid to the utility of the buyer.
2.2 Affine Maximizer Auctions
Affine Maximizer Auctions (AMA) also provide a menu M with a set of options K. Each option is (k) of the form (g()) E [0, 1| R. where zi E [0, 1] represents the allocation of item to
(k) buyer j. with the restriction that E; ii I 1 for each item j. and g(k) represents 'boost'. We again assume E IC, and (x=(0),3(0)) = (0, 0). and call this the default option; all other options are called the regular options.
Given the bids b; E [0, 1|" of the agents, the auctioneer computes weighted welfare, using weights wi E R4 for the valuations of each agent, and adds the boost g(k), Then, the allocation maximizing the weighted boosted welfare is chosen, i.c., the option with
k<b) E arg max
Σ web oi + g()
REK
This will also be referred to as the active option. The prices collected from the buyers are computed according to the Vickrey Clarke-Groves (VCG) scheme. Namely,
(b(
(b(b-i)) + g(h(b Σ wab xa
1 We
Σ webs xi (b(b)) + g(((b))
(I)
Here, k((b;) represents the option maximizing the weighted boosted welfare when buyer omitted, i... k(bbi) E arg max Ees Web -1 + ((),, It is known that AMA is DSIC and IR. Hence, we can assume that the submitted bids b, represent the true valuations We also assume the ties are broken favor of maximizing the total payment. case of unit weights, this equivalent to Given the menu M, the revenue of the AMA
choosing the smallest, ((k) values, see (2 in Section
Σ pilo))
Rev(M) = E
In this paper, we focus on the case when W, = 1 for all buyers. This is also used in the experiments in Curry al. [2022b]. For this case, AMA can be implemented by a three layer neural network similar to RochetNet, with m n input neurons. For the more general case when the weights can also be adjusted, one can include an additional layer that combines the buyers' allocations.
Note that for single buyer and wi 1, AMA corresponds to RochetNet, with price p = - for each menu option. Indeed, in the formula defining the price p5 (b), the first term is 0, as well as the sum in the second term.
Similarly to RochetNet, the loss function, which is maximized cafimma-approximation of the revenue (ev(M), in order to avoid the discontinuities introduced by the argmax. We bound the difference in the revenue in Appendix [.3] concluding that it decreases with large parameter Y in the RochetNet case.
stochastic gradient ascent, is

---

2.3 Mode Connectivity
One can view the revenue as a function of the menus, i.e., the parameters in the mechanism: (i) in RochetNet, {(x(4, , I (ii) in AMA, 1 B())) JREK. We use M to denote the set of all possible menus.
Definition (Mode connectivity) Two menus M1, M2 M are e-mode-connecte if there is continuous curve π [0,1] + M such that (i) (0) = M1; (ii) T(1) = M2; and (iii) for any e [0, 11, Rev(T(()) 2 min (eeeRR((M))) Rev(Ma)) Reo())) E.
3 Mode Connectivity for the RochetNet
In this section we present and prove our main results for the RochetNet. For some statements, we only include proof sketches. The detailed proofs can be found in Appendix [A]in the supplementary material. The following definition plays an analogous role to s-dropout stability in Kuditipudi et al. 2019].
Definition 4. A menu M with [K] = K + 1 options is called s-reducible there is subset K' C K. with O E K", |KC S VK + 1 such that, with probability at least 1 - over the distribution of the valuation of the buyer, the active option assigned to the buyer contained in K',
As noted in the Introduction, such a property can be observed in the experimental results in Dütting et al. [2019]. The motivation behind this definition is that if menu satisfies this property, then all but v K + options are more or less redundant. In fact, if a menu is e-reducible, then dropping all but the at most /K + many options in K' results in a menu M' with Rev( (") 2 Rev(M) - because the price of any selected option bounded by |el]i S 1.
As a first step towards showing the mode connectivity results, we show that O-reducibility implies O-mode-connectivtty. We will then use this to derive our two main results, namely that two s-reducible menus are always e-mode-comeen connected and that two large menus are always smode-connected
Proposition 5. If two menus Mi and M2 for the RocheiNei are O-reducible, then they are O-mode- connected. Moreover, the curve transforming M1 into M2 is piecewise linear with only three pieces.
To prove Proposition we introduce two intermediate menus M1 and M2, and show that every menu in the piecewise linear interpolation from Mi via M, and M2 to M2 yields revenue of at least min Rev (M Using that menu M1 has only VK + I non-redundant options, menu M, will be defined by repeating each of the VK + options vK derived from M2 similarly. A technical lemma makes sure that this copying can be done in such way that each pair a non-radundant option of M1 and non-redundant option of M2 occurs exactly for one index in Mj and M2.
times. Menu M, will be
To make this more formal, we first assume without loss of generality that K + 1 is square, such that VK II+I is an integer. It is straightforward to verify that the theorem is true for non non-squares K + 1, too. Suppose the options in M1 and M2 are indexed with & E KC {0. 1.... K}. Since M, 0-reducible, there a subset K2 C with E K1, | = /
such that an option with index
in K2 is selected with probability over the distribution of the possible valuations. Similarly, such a set K2 exists for M2. To define the curve that provides mode connectivity, we need the following technical lemma, which is proven in Appendix A
Lemma 6. There exists bijection ip: K. Kr x K2 such that for all k Kr we have that (pk)) E {k) x K2, and all E K2 we have that yp(k) E Kr x (1.).
With this lemma, we can define M, and Mr. Let to the bijection from Lemma 6 and suppose M1 = (*)()) pp(k) )xex- We then define M, = (()(11(()) (ppee))pppppm)))))))) (A)) where yp (k) is the first component of (ok).. Similarly, Mr is derived from M2 by using the second component (k2(k) of <kk) instead of yp (k:). remains to show that all menus on the three straight line segments from Mj via M, and Mr to M2 yield revenue of at least min min [Re((M) (M1). (My(M) }, which is established by the following two propositions: their proofs can be found in Appendix
7

---

Proposition 7. Let M = - be convex combination of the menus M1 and M1. Then Rev(M) 2 MM). Similarly, every corvex combination of the menus M2 and M2 has revenue at least Rev(M2).
The idea to prove Proposition 7 is that, on the whole line segment from Mi to Mi, the only active options are those in K", implying that the revenue does not decrease.
Proposition 8. Ler M AM1 + (1 X) be a convex combination of the menus M1 and M2. Then, M))(M) 2 X + (1 A) A)Rev(M2)
The idea to prove Proposition 8 is that, due to the special structure provided by Lemma 6 linear interpolation between the menus also provides a linear interpolation between the revenues. Note that without the construction of Lemma such a linear relation would be false; such an example is shown in Appendix [
Proposition 5 directly follows from Proposition 7 and Proposition g Based on Proposition 5 we can show our two main theorems for the RochetNet. The first result follows relatively easily from Proposition 5
Theorem 9. If two menus M1 and M2 for the RochetNet are e-reducible, then they are e-mode- connected. Moreover, the curve transforming M1 into M2 is piecewise linear with only five pieces.
Proof. We prove this result by showing that every e-reducible menu M can be linearly transformed into a 0-reducible menu M such that each convex combination of M and M achieves revenue of at least Rev(M)
E. This transformation converting M1 and M2 to M1 and M2, respectively, yields the first and the fifth of the linear pieces transforming M, to M2. Together with Proposition appplie to M1 and M2 serving as the second to fourth linear piece; the theorem then follows.
To this end, let M be an e-reducible menu with options indexed by k E K. By definition, there is a subset K' S IC of at most VK +1 I many options such that, with probability at least 1 - E, the assigned active option is contained in K'. Let M consist of the same allocations as M, but with modified prices. For an option E K', the price p(t) p()) in M is the same as in M. However, for an option & E IC \ K', we set the price p(A) > in M to be larger than the largest possible valuation of any option ||o|| < 1. It follows that such an option will never be selected and M is O-reducible.
To complete the proof, let us look at the reward of convex combination M' = AM + (1 A). If for a particular valuation v the selected option in M was in IC', then the same option will be selected in M'. This happens with probability at least 1 In any other case, anything can happen, but the revenue cannot worsen by more than the maximum possible valuation, which is ||l|| I 1. Therefore, Rev(M) Rev(M') e e, completing the proof.
Theorem 10. If two menus M1 and M2 for the RochetNet have size at least 12,,, then they are e-connected. Moreover, the curve transforming M1 into M2 is piecewise linear with only five pieces.
Proof Sketch. The full proof can be found in Appendix A.2 The intuition behind this theorem is that if menus are large, then they should contain many redundant options. Indeed, as in the previous theorem, the strategy is as follows. We show that every menu M of size at least 1 2 can be linearly transformed into a O-reducible menu M such that each convex combination of M and M achieves a revenue of at least Rev(M (M) e. This transformation converting M, and M2 to M, and Mg. respectively, yields the first and the fifth of the linear pieces transforming M1 M2. Together with Proposition applied to M2 and M2 serving as the second to fourth linear piece, the theorem then follows.
However, this time, the linear transformation of M to M is much more intricate than in the previous theorem. To do so, it is not sufficient to only adapt the prices. Instead, we also change the allocations of the menu options by rounding them discretized values. This technique is inspired by Dughmi ett al. [014], but non-trivially adapted to our setting. Since the rounding may also modify the active option for each valuation, we have carefully adapt the prices in order to make sure that for each valuation, the newly selected option is not significantly worse than the originally selected one. Finally, this property has to be proven not only for M, but for every convex combination of M and M.
8

---

After the above rounding, the number of possible allocations for any option is bounded by 1,1". Out of several options with the same allocation, the buyer would always choose the cheapest one, implying that the resulting menu M is O-reducible.
4 Mode Connectivity for the Affine Maximizer Auctions
Throughout this section, we focus on AMAs with fixed weights wi 1 for all buyers i. Similarly to RochetNet, we have the following definition for AMAs.
Definition 11. A menu M. with K + options is s-reducible if and only if there exists a subset K' K, 0 E K', IK') S VK + such that, with probability least 1 - over the distribution of the valuation of the buyers, (i) k(v=s) E K' for any buyer i; and (ii) k(e) E K
Such phenomena are observed in the experiments in (Curry et al. 2022b Section 6.3].
Our main results, namely that two e-reducible menus always E-connected and two large menus are always e-connected, are based on the following proposition, in which we show that O-reducibility implies 0-connectivity.
Proposition 12. Iwo menus M1 and M2 are O-reducible, then they are O-connected. Moreover, the curve transforming M1 into M2 is piecewise linear with only three pieces.
The proof idea is similar to the proof of Proposition 5 in RochetNet, but requires additional arguments due to the more intricate price structure (see Appendix D.I for more details). Based on this proposition. now, we are able to show our two main results. First, we achieve e-connectivity from e-reducibility.
Theorem 13. If two AMAS M1 and M2 are g-reducible, then they are g-mode-connected. Moreover, the curve transfomming M₁ to M2 is piecewise linear with only five pieces.
Before the proof, we recall how the total payment is calculated for valuation profile v. We choose k(v) the option which maximizes the boosted welfare, Σ, v.7 xx + g(k), According to the total revenue can be written as
[ = Σ 5
Σ Eti
U ot (k(o-M)) + g((( -(m - 1)
TTa
Σ 0 (k(u)) + g(k(w))
g((c))
boosted welfare of V--g
boosted wellare of
Proof of Theorem 13 Similar to the proof of Theorem 9 it is sufficient to show that every s-reducible menu M can be linearly transformed into a O-reducible menu M such that each convex combination of M and M achieves a revenue of at least Rev(M E. This can then be used as the first and fifth linear piece of the curve connecting Mj and M2. while the middle three pieces provided by Proposition 12]
We construct M by (i) keeping all options in XC' unchanged; (ii) for the options à E K. IC', we decrease ((() to be smaller than -m, which implies such an option will never be selected (recall that 0 E K'' is assumed, and the option (0. 0) is better than any such option). Consequently, M is O-reducible.
To complete the proof, let us look at the revenue of M' = ((x gr(()) JeEK, which is a con- vex combination of M and M: M' = AM + (1 A)M for 0 S A < 1. Let k(v)) arg max; Σ; v.T T<(T)) + gr(k), As we decrease g(k) for k K", ((V,((U) X implies k'(v) K and, X" additionally, option k (v(v) and option k(v) achieve the same boosted welfare and same B. Therefore, since M is e-reducible, with probability at least 1 - m the boosted welfare of u as well as the boosted welfare of o for all buyers i the same for M and for M'. According to the formula (2), the total payment for the profile is the same for M and M'. Therefore, the loss on the revenue can only appear with probability at most e. and the maximum loss is at most m, which implies an loss in m
total.

---

Second, we show that mode connectivity also holds for those AMAs with large menu sizes, namely for K + 16m 2nm
Theorem 14. For any 0 O<C c 2. if two AMAs M1 and M2 have at least K + 2 116m 2
options, then they are s-mode-connecte Moreover, the curve transforming M1 10 M2 is piecewise linear with only five pieces.
Proof Sketch. The full proof can be found Appendix D.2 Similar to RochetNet, the idea of proving Theorem 14 is to discretize the allocations in the menu, then one can use Proposition| 12 to construct the low-loss transformation from MI to M2 by five linear pieces. To do this, one wants the loss of revenue to be small during the discretization. Consider the formula (2 of the total payment. The first two terms do not change much by small change of the discretization. However, the last term (((())) might be significantly affected by discretization, which may cause a notable decrease the total payment. To avoid this, we perform proportional discount on B, incentivizing the auctioneer to choose an allocation with small 3. By this approach, the original revenue will be approximately maintained. Furthermore, we show a linear path, connecting the original menu and the menu after discretizing, which will suffer small loss.
5
Conclusion
We have given theoretical evidence of mode-comeettiitty in neural networks designed to learn auction mechanisms, Our results show that, for sufficiently wide hidden layer, e-mode-connectivity holds in the strongest possible sense. Perhaps more practically, we have shown e-mode-comnectivity under e-reducibilityy i.e., the assumption that there is sufficiently small subset of neurons that preserve most of the revenue. There is evidence for this assumption in previous work in differentiable economies. A systematic experimental study that verifies this assumption under various distributions and network sizes is left for future work.
Our results make a first step in providing theoretical arguments underlying the success of neural networks in mechanism design. Our focus was on some of the most basic architectures. A natural next step is to extend the arguments for AMA networks with variable weights w;. Such a result will need to analyze a four layer network, and thus could make headway into understanding the behaviour of deep networks. Besides RochetNet, Dütting et al. [2019] also proposed RegretNet, based on minimising regret objective. This network is also applicable to multiple buyers, but only provides approximate incentive compatibility, and has been extended in subsequent work, e.g., Feng et al. (2018), Golowich et al. (2018). Duan al. [0022). The architecture is however quite different from RochetNer: it involves two deep neural networks in conjunction, an allocation and a payment network, and uses expected ex post regret the loss function. We therefore expect mode-connectivity analysis for RegretNer to require a considerable extension of the techniques used by us. We believe that such an analysis would be significant next step in the theoretical analysis of neural networks in differentiable economics.
Acknowledgments and Disclosure of Funding
All three authors gratefully acknowledge support by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (for all three authors via grant agreement ScaleOpt-757481, for Christoph Hertrich additionally via grant agreement ForEFront-615640), Yixin Tao also acknowledges the Grant 0023110522 from SUFE.
References
Z. Allen-Zhu, Y. Li, and Song. convergence theory for deep learning via over- prrmmttattttii.iinnn. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference on Machine Learning, pages 254 PMIR, 2018.
10

---

M. Babaioff, Y. A. Gonczarowski, and N. Nisan. The minu-size complexity of revenue approximation. Games and Economic Behavior, 134:281-307, 2022.
A. Bhalgat, S. Gollapudi, and K. Munagala. Optimal auctions via the multiplicative weight method. In Proceedings of the fourteenth ACM Conference Electronic Commerce, pages 73-90, 2013.
Y. Cai, C. Daskalakis, and S. M. Weinberg. An algorithmic characterization of multi-dimennsooal mechanisms. In Proceedings of the forty-fourth Annual ACM Symposium on Theory of Computing, pages 459-478, 2a.
Y. Cai, C. Daskalakis, and M. Weinberg. Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. In IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 130-139. IEEE, 2012b.
Y. Cai, C. Daskalakis, and S. M. Weinberg. Understanding incentives: Mechanism design becomes algorithm design. In IEEE 54th Annual Symposium on Foundations of Computer Science, pages 618-627. IEEE, 2013.
E. H. Clarke. Multipart pricing of public goods. Public Choice, pages 17-33, 1971.
V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence, pages 103-110, 2002.
V. Conitzer and T. Sandholm. Self-interested automated mechanism design and implications for opti- mal combinatorial auctions. In Proceedings of the 5th ACM Conference on Electromic Commerce, pages 132-141, 2004.
M. Curry, U. Lyi, T. Goldstein, and J. Dickerson. Learning revenue-maximizing auctions with differentiable matching. In International Conference on Artificial Intelligence and Statistics, pages 6062-6073, PMLR, 2022a.
M. Curry, T. Sandholm, and Dickerson. Differentiable economics for randomized affine maximizer auctions. arXiv preprint arXiv:2202.02872, 2022b.
C. Daskalakis. Multi-item auctions defying intuition? ACM SIGecom Exchanges, 14(1):41-75, 2015.
C. Daskalakis, A. Deckelbaum, and C. Tzamos. Mechanism design via optimal transport. In Proceedings of the fourteenth ACM Conference on Electronic Commerce, pages 269-286, 2013.
C. Daskalakis, A. Deckelbaum, and C. Tzamos. The complexity of optimal mechanism design. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete Algorithms, pages 1302-1318. SIAM, 2014.
C. Daskalakis, A. Deckelbaum, and C. Tzamos. Strong duality for multiple-gos monopolist. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 449-450, 2015.
F. Draxler, K. Veschgini, M. Salmhofer, and F. Hamprecht. Essentially no barriers in neural network energy landscape. In International Conference on Machine Learning, pages 1319-1318. PMLR, 2018.
S. Du, Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
Z. Duan, J. Tang, Y. Yin, Z. Feng, X. Yan, M. Zaheer, and X. Deng. A context-integratee transformer- based neural network for auction design. International Conference on Machine Learning, pages PMLR, 2022.
S. Dughmi, L. Han, and N. Nisan. Sampling and representation complexity of revenue maximization. In Web and Internet Economics: 10th International Conference, WINE 2014, pages 277-291. Springer, 2014.
Dütting, Z. Feng, H. Narasimhan, D. Parkes, and S. Ravindranath. Optimal auctions through deep learning. In International Conference Machine Learning, pages 1706-1715. PMLR, 2019.
11

---

Z. Feng, H. Narasimhan, and D. C. Parkes. Deep learning for revenue-optimal auctions with budgets. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pages 354-362, 2018.
T. Garipov, P. Izmailov, D. Podoprikhin, D. P. Vetrov, and A. G. Wilson. Loss surfaces, mode connectivity, and fast ensembling of DNNs. Advances in Neural Information Processing Systems, 31, 2018.
Y. Giannakopoulos and E. Koutsoupias. Duality and optimality of auctions for uniform distributions. In Proceedings of the fifteenth ACM Conference on Economics and Computation, pages 259-276, 2014.
Y. Giannakopoulos and E. Koutsoupias. Duality and optimality of auctions for uniform distributions. SIAM Journal on Computing, 47(1):121-165, 2018.
N. Golowich, H. Narasimhan, and D. C. Parkes. Deep learning for multi-facility location mechanism design. In International Joint Conference on Artificial Intelligence, pages 261-267, 2018.
T. Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617-631, 1973.
R. Kuditipudi, X. Wang, H. Lee, Y. Zhang. Z. Li, W. Hu, R. Ge, and Arora. Explaining landscape connectivity of low-cost solutions for multilayer nets. Advances in Neural Information Processing Systems, 32, 2019.
K. Kuo, Ostuni, E. Horishny, M. Curry, S. Dooley, P.yy. Chiang, Goldstein, and Dickerson. Proportionnet: Balancing fairness and revenue for auction design with deep learning, arXiv preprint arXiv:2010.063398, 2020.
A. M. Manelli and D. R. Vincent, Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly. Journal of Economic Theory, 137(1):153-185, 2007.
R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
Q Nguyen. On connected sublevel in deep learning. In International Conference on Machine Learning, pages 4799-4799. PMLR, 2019.
J.-C. Rochet. A necessary and sufficient condition for rationalizability in quasi-linear context. Journal of Mathematical Economics, 16(2):191-200 1987.
J.-C. Rochet and L. A. Stole. The economics of multidimensional screening. Econometric Society Monographs, 35:150 150-197, 2003.
T. Sandholm and A. Likhodedov. Automated design of revenue-maximizing combinatorial auctions. Operations Research, 6305):1000-1025, 2015.
W. Shen, P. Tang, and S. Zuo. Automated mechanism design via neural networks. In Proceedings of the I 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 215-223, 2019.
A. Shevchenko and M. Mondelli. Landscape connectivity and dropout stability of sgd solutions for over over-parani wer-parameterized neural networks. In International Conference on Machine Learning, pages PMLR, 2020.
W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8-37, 1961.
S. Zheng, A. Trott, S. Srinivasa, D. C. Parkes, and R. Socher. The Al economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8(18), 2022.
12


Reviews:
[{"review_id": "foHF43V9pj", "reviewer": "Reviewer_Cnd8", "summary": "This paper focuses on justifying the empirical success of this differentiable economics, particularly in the context of menu-based methods like RochetNet and Differentiable AMA auctions.\n\nThe authors introduce the concept of the $\\epsilon$-mode connectivity property, which establishes that two locally optimal menus are connected by a simple path where the revenue loss along the path is at most $\\epsilon$. The paper demonstrates that this property holds true under two conditions:\n- If the valuations are normalized, and the menus are $\\epsilon$-reducible, meaning that there exists a small subset of menus that are active for a buyer with a probability of $1-\\epsilon$.\n- If the number of menu options is sufficiently large.\n", "questions": "Please see Weaknesses.", "limitations": "N/A ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**Significance:** Although menu-based approaches for differentiable economics show promising empirical performance, there is a lack of understanding regarding their theoretical properties. This paper takes the first stride towards exploring these theoretical aspects. \n\n**Originality:**  While mode-connectivity has primarily been studied in the context of prediction problems involving convex losses with linear transformations in the final layer, RochetNet and Differentiable AMA minimize negated revenue loss, which involves more complex calculations. This fundamental difference sets them apart in their analysis.\n\n**Clarity and Quality:** The paper is well written and easy to follow. ", "weaknesses": " - This paper would benefit a lot from a discussion on how exactly mode connectivity can be used to justify empirical performance. While I agree that this is a cool theoretical property, it is very unclear to me how this exactly would help\n- There is also no discussion/comments what practitioners should make of this property at all - (are there any insights on how to initialize these networks better to break permutation symmetry of menus etc or anything that would help improve training)\n- The optimal allocations are not necessarily finite (this assumption isn't state clearly wherever used). See Example 3 in [*]\n\n[*] Daskalakis, C., Deckelbaum, A., and Tzamos, C. (2017). Strong duality for a multiple-good monopolist. Econometrica, 85:735–767.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading and assessing our paper and for the valuable feedback. In the following we respond to the three questions/weaknesses raised by the reviewer.\n\n>This paper would benefit a lot from a discussion on how exactly mode connectivity can be used to justify empirical performance. While I agree that this is a cool theoretical property, it is very unclear to me how this exactly would help\n\nA: We will add such a discussion to the final version. Basically, the intuition why mode connectivity is desirable is the same as for previous mode connectivity results. In the following we outline our perspective on this.\n\nMode connectivity can help to explain the empirical performance of stochastic gradient descent (sgd) (or ascent, in case of revenue maximization). To some extent, mode connectivity prevents a poor local minimal valley region on the function value, from which the sgd method cannot escape easily. Suppose such a bad local minimum exists. Then mode connectivity implies that there exists a path from this bad local minimum to a global minimum on which the loss function does not significantly increase. Therefore, the intuition is that from every bad local minimum, a (stochastic) gradient method would be able to find a way to escape.\n\nIn fact, such a very bad local minimal valley region does appear in the auction setting when the menu size is 1 (see Appendix C), which seems to counter the empirical performance of achieving the global optimum eventually. This paper proves that this will not appear when the menu size is big.\n\nHowever, we agree that the mode connectivity cannot fully justify the success of gradient descent, and there is a gap here, which also exists in the previous work on mode connectivity for neural networks. Mode connectivity only suggests that the local search algorithms are unlikely to get completely trapped. \n\n> There is also no discussion/comments what practitioners should make of this property at all - (are there any insights on how to initialize these networks better to break permutation symmetry of menus etc or anything that would help improve training)\n\nA: We see the main contribution of our paper in explaining the empirical success and providing theoretical foundations for already existent practical methods, and not in inventing new methods. Nevertheless, two insights a practitioner could use are as follows: (i) It is worth understanding the structure of the auction in question. If one can, e.g., understand whether $\\epsilon$-reducibility holds for a particular auction, this might indicate whether RochetNet or AMA are good methods to apply to this particular case.\n(ii) Size helps: If one encounters bad local optima, increasing the menu size and rerunning RochetNet/AMA might be a potential fix (and will eventually lead to a network satisfying mode connectivity).\n\n> The optimal allocations are not necessarily finite (this assumption isn't state clearly wherever used). See Example 3 in [...].\n\nA: We agree, and we do mention this in our paper, e.g. in the second paragraph of the introduction: \"Already for two items and a single buyer, the description of the optimal mechanism may be uncountable [...].\" However, our statements are not missing any assumptions as our proofs do not require the optimal allocation to be finite. Even if the optimal allocation is infinite, mode connectivity between any two considered menus (stemming from RochetNet or AMA) holds under the stated assumptions."}, {"review_id": "A83Qfz6w7A", "reviewer": "Reviewer_aV1n", "summary": "This paper studies the mode connectivity in neural networks for design auction mechanisms. Specifically, the authors prove that locally optimal solutions are connected by a simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima.", "questions": "Please address the weakness above. I would like to increase the score if it can be cleared.", "limitations": "Please see the weaknesses above.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper proposes to address a significant problem: how to design an auction mechanism via machine learning.\n\nThe proof is given in detail and looks all correct.\n\nThe presentation is clear and well-structured.", "weaknesses": "The novelty and significance are not clear. Is the mode connectivity in auction mechanism just a special case of the mode connectivity of neural networks in general? Following this intuition, the proof seems straightforward:\n\nThe functional from a neural network to its corresponding revenue is a bounded (continuous) functional; the functional from this neural network to its training loss is also a bounded functional. Thus, it is a continuous function from training loss to revenue. Therefore, the mode connectivity of neural networks in term of the training loss implies the mode connectivity of auction mechanism in term of revenue. Some may argue that these bounded/continuous properties may not always hold, but given the neural networks are usually trained by SGD or its variants, these properties should stand. \n\n------\n\nPOST-REBUTTAL: my concerns are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading and assessing our paper and for the valuable feedback. As we state in the paper already, we do not believe that mode connectivity in auction settings follows as a special case from general mode connectivity results. We will make this clearer in the final version.\n\nIn response to the question raised by the reviewer, in the following, we explain (i) why we think the argument suggested by the reviewer is not sufficient to deduce mode connectivity for auction design from previous mode connectivity results and (ii) why we do not think that a similar reasoning is possible at all.\n\n(i) We are not sure what exactly the reviewer means by \"training loss\" in the suggested argument, but we suppose it is some loss function on some training data in a setting for which mode connectivity is known. We would like to point out that this setting is structurally very different from our setting, in which training data does not really come as labeled pairs. Instead, in the auction setting, the expected revenue is directly maximized via stochastic gradient ascent by sampling from the valuation distribution.\n\nMoreover, even if one were able to define a meaningful notion of \"training loss\" as suggested by the reviewer, for which mode connectivity holds by previous results and which depends continuously on the network parameters, the reasoning suggested by the reviewer does not work at two different points: 1. the revenue is NOT a continuous function of the network parameters due to the involved, discontinuous argmax. 2. Even if it was, there cannot exist a well-defined mapping from \"training loss\" to revenue (or vice versa): different values of revenue would correspond to the same values of \"training loss\" and vice versa. Therefore it does not even make sense to speak about continuity of such a mapping.\n\n(ii) More generally, deducing mode connectivity for auction settings from previous mode connectivity results appears to be infeasible for the following reason. To our best knowledge, previous works on the mode connectivity of neural networks crucially rely on the properties that the networks minimize a convex loss function between the predicted and actual values, and require linear transformations in the final layer. However, these properties do not hold in RochetNet and AMA networks, where the structures are fundamentally different. For example, the loss function of RochetNet is not even a function of the network's output, but is defined by choosing the price of the argmax option, which is neither a linear transformation nor convex. We do not see how previous techniques can be applied here with a simple modification.\n\nActually, other than mode connectivity, many properties or characterizations of neural networks cannot be applied to auction settings. For example, we know, for neural networks, the optimal training loss tends to 0 with sufficient over-parameterization. In contrast, the optimal revenue of auction mechanisms is extremely challenging: it remains largely unknown for most buyers' valuation distributions, even in the RochetNet case."}, {"review_id": "CpszPRJ7E2", "reviewer": "Reviewer_hKdM", "summary": "The starting point for the paper is recent work in the area of “differentiable economics”, in which high-revenue strategyproof auction mechanisms are found by optimizing parameters using machine-learning-inspired gradient descent techniques.\n\nThe authors consider the problem of selling multiple goods to a single buyer. In such setting, strategyproof mechanisms can always be identified with a “menu” of (allocation, price) pairs — the bidder chooses their best choice from the menu, and carefully optimizing the menu can increase revenue. The neural architecture that represents these menu items is called “RochetNet”. They also consider multi-buyer versions of this problem, in particular searching through the space of affine maximizer auctions (AMA), which are structurally similar (there is a “menu” of possible outcomes, and a “boost” which roughly plays the role of the price, although actual per-bidder payments are calculated according to a VCG-style rule).\n\nIn these classes of auctions, the performance goal (revenue) is a very non-convex function of the auction parameters. Nevertheless, first-order optimization seems to work well in finding good or even known-optimal mechanisms. Also, empirically, allowing the auctions to learn over thousands of menu items helped performance, even though at the end of training, only a handful of these menu items were actually used (and in some cases known-optimal mechanisms might only have 3-4 menu items). The authors of this paper aim to explain these phenomena.\n\nThey build on existing work in deep learning for more standard tasks, where things work similarly: even though loss landscapes are not convex, it is possible to optimize over them using first-order methods, and overparameterizing the neural networks seems to help with this. One recent direction of theoretical work aims to explain these phenomena using the concept of “mode connectivity” — there are various results showing that if it is possible to remove lots of neurons from a trained network and get almost the same performance, then any two such solutions must be connected by a continuous path where at any point along the path, the loss function is within some constant of the two solutions. Presumably, loss landscapes with such a property should be easier to optimize over.\n\nThe authors establish similar properties for the two types of auction architectures. In particular, between any two menus where there is a small subset of options that would be chosen by a bidder with probability 1-\\epsilon, embedded in a much larger unused or redundant menu, they show that (epsilon) mode connectivity holds. Additionally, any pair of menus with sufficiently large (as a function of epsilon and the number of items) menus is also epsilon-mode connected. Analogous results hold for AMAs.This provides a nice theoretical explanation of why these auctions are unexpectedly easy to optimize successfully, and why using large menus may help optimization.", "questions": "I recommend further discussion of Shen et al. “Automated mechanism design via neural networks”, which presents an architecture that for certain cases is equivalent to RochetNet. It’s cited at one point but the actual neural architecture merits discussion (it also encodes menu items).\n\nIs there an explicit explanation of exactly why mode connectivity helps optimization? Maybe it’s out there in the literature already. If so I think it’s worth devoting a few sentences to this.", "limitations": "Limitations are adequately addressed — in particular, that these techniques probably won’t extend to even more complicated/flexible auction architectures — they rely on the relatively simple “menu based” or “list of allocations + boost” structure of the particular architectures in question.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Two separate papers in this area observed an interesting and useful empirical phenomenon but gave no good explanation for it. This paper gives a very solid explanation, and is extremely interesting for that reason. It also will hopefully motivate better designs and learning techniques for strategyproof auction architectures.", "weaknesses": "Currently I don’t see any significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading and assessing our paper and for the valuable feedback.\n\n> I recommend further discussion of Shen et al. “Automated mechanism design via neural networks”, which presents an architecture that for certain cases is equivalent to RochetNet. It’s cited at one point but the actual neural architecture merits discussion (it also encodes menu items).\n\nA: Thanks for pointing out this. We will incorporate further discussion of Shen et al. into our final version.  MenuNet, developed by Shen et al. also encodes menu items and it generalizes RochetNet as it allows non-linear utility functions and can incorporate other networks trained from interaction data. One difference between MenuNet and RochetNet is their handling of valuation distributions. RochetNet repeatedly samples the valuations from the underlying distribution, whereas MenuNet discretizes the buyer's valuation space to discrete values and treats all possible discrete valuations as a collective input.\n\nOf course, in those cases where RochetNet and MenuNet are equivalent, our results directly apply to MenuNet, too. However, for general, non-linear utilities, we believe that it is interesting to obtain similar results, but this might be much more challenging.\n\n> Is there an explicit explanation of exactly why mode connectivity helps optimization? Maybe it’s out there in the literature already. If so I think it’s worth devoting a few sentences to this.\n\nA: We will add such a discussion to the final version. Basically, the intuition why mode connectivity is desirable is the same as for previous mode connectivity results. In the following we outline our perspective on this.\n\nMode connectivity can help to explain the empirical performance of stochastic gradient descent (sgd) (or ascent, in case of revenue maximization). To some extent, mode connectivity prevents a poor local minimal valley region on the function value, from which the sgd method cannot escape easily. Suppose such a bad local minimum exists. Then mode connectivity implies that there exists a path from this bad local minimum to a global minimum on which the loss function does not significantly increase. Therefore, the intuition is that from every bad local minimum, a (stochastic) gradient method would be able to find a way to escape.\n\nIn fact, such a very bad local minimal valley region does appear in the auction setting when the menu size is 1 (see Appendix C), which seems to counter the empirical performance of achieving the global optimum eventually. This paper proves that this will not appear when the menu size is big.\n\nHowever, note that the mode connectivity cannot fully justify the success of gradient descent, and there is a gap here, which also exists in the previous work on mode connectivity for neural networks. Mode connectivity only suggests that the local search algorithms are unlikely to get completely trapped."}, {"review_id": "ebuSFstVoS", "reviewer": "Reviewer_HRyy", "summary": "This paper studies the mode connectivity for specific neural network architecture, i.e., RochetNet and Affine Maximizer Auctions(AMA), where the local optimal solutions produce close local optimal solutions. To be specific, \n- for linear utilities, $\\epsilon$-reducible solutions implies $\\epsilon$- mode connectivity.\n- for $n$ items and linear utilities, for large menu options $K$, then $\\epsilon$-mode connectivity holds between any solutions for any distribution. \n- Similar results also holds for AMA. ", "questions": "- What's the definition of the word \"option\" studied in this paper?\n- Does this $\\epsilon$ scale with the upper bound of the distribution, of the distribution is not in $[0,1]$, but in $[0,H]? ", "limitations": "This paper is theoretical, hence there are no experiment results. ", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "- The problem studied is a heated topic, and is a really interesting interdisciplinary area between auction design and neural network design. \n- The result is quite novel, and establish some difference against existing work on mode connectivity. ", "weaknesses": "The network architecture difference of existing work and the neural network studied in this paper needs further clarification, and more emphasis. \n\n\nThe current presentation of this paper needs a major revision, especially on our contributions sections. To name a few:\n- There are some concepts that refer to later section of the paper, and the reviewer strongly suggests moving these definitions (or create an informal version) to the introduction section for readability, e.g., $\\epsilon$-reducible appeared for line 85, 89, 110, affine maximizer for line 103. \n- line 73-83 doesn't include the results for this paper, but rather a brief intro of RochetNet. \n- For reviewers unfamiliar with the word \"options\", it's really hard to understand the sentence in line 75. \"single hidden layer where the neurons directly correspond to menu options\".\n- The reviewer strongly suggests to put figure 1 in the intro section, and adding more details to the figure would helps a lot of the understanding of the paper. \n- In section 1.1, many results/theorems are mixed with existing results, which is quite confusing. \n- The definition of mode connectivity doesn't appear until page 6 of the paper...\n\nSome other minor comments:\n- line 21, please replace \"DISC\" by \"DSIC\". \n- line 79, \"straight-jacket auction\" should be supported by citations. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading and assessing our paper and for the valuable feedback.\n\nWe regret that the reviewer perceives the presentation of our paper as poor. We are thankful for the constructive feedback and will do our best to address the issues raised by the reviewer in the final version. We provide a detailed response below.\n\n> The network architecture difference of existing work and the neural network studied in this paper needs further clarification, and more emphasis.\n\nA: We explain these differences in lines 118 to 133 of the initial submission. We also provide formal definitions of the considered architectures in Sections 2.1 and 2.2. Nevertheless, we understand that we should emphasize these differences more (see also our response to reviewer aV1n), and will do so in the final version.\n\n> There are some concepts that refer to later section of the paper, and the reviewer strongly suggests moving these definitions (or create an informal version) to the introduction section for readability, e.g., $\\varepsilon$-reducible appeared for line 85, 89, 110, affine maximizer for line 103.\n\nA: Thanks for the suggestions. We will move corresponding (informal) definitions to earlier points in the paper.\n\n> line 73-83 doesn't include the results for this paper, but rather a brief intro of RochetNet.\n\nA: We agree, but we feel that for a smooth reading flow, it is necessary to provide this brief intro here to understand our contribution. It is not long enough to be moved into a separate (sub)section. See also our explanation further down.\n\n> For reviewers unfamiliar with the word \"options\", it's really hard to understand the sentence in line 75. \"single hidden layer where the neurons directly correspond to menu options\".\n\nA: The word option (an allocation and a price offered to the buyer) is explained in the very same line after the colon. In the final version we will reformulate the sentence to make it more understandable. See also our response to the related question below.\n\n> The reviewer strongly suggests to put figure 1 in the intro section, and adding more details to the figure would helps a lot of the understanding of the paper.\n\nA: The purpose of Figure 1 is to illustrate the formal definition of the RochetNet. Going into such great detail in the intro already seems to be a bit over the top for us. If the reviewer insists, we can add another, simplified version of the figure to the intro in the final version.\n\n> In section 1.1, many results/theorems are mixed with existing results, which is quite confusing.\n\nA: Our impression is that providing the context (previous results) while presenting our own contributions is more important than a clear visual separation. We still carefully state which results are our own ones. If the reviewer insists, we can try to separate this more, but we fear that this makes it harder to understand the context.\n\nOur paper aims to provide a theoretical explanation for the existing empirical success of mechanism design. Therefore, to effectively convey our contribution, we believe it is necessary to first present the key details of the existing empirical results and introduce our theoretical findings subsequently.\n\n> The definition of mode connectivity doesn't appear until page 6 of the paper...\n\nA: It is defined informally in the mode connectivity paragraph. To make it visually more clear, we will convert it to a definition environment in the final version.\n\nSome other minor comments:\n\n> line 21, please replace \"DISC\" by \"DSIC\".\n\nA: Will be fixed. Thanks!\n\n> line 79, \"straight-jacket auction\" should be supported by citations.\n\nA: We will add a citation. Thanks!\n\nQuestions:\n\n> What's the definition of the word \"option\" studied in this paper?\n\nA: An option is a pair consisting of an allocation and a price offered from the seller to the buyer. We define this in line 75 of the original submission. As stated above, we will reformulate this sentence in the final version to avoid confusion.\n\nA set of several options is called a menu. For example, in the two-items case, a menu with two (non-trivial) options could be as follows: the first option is to get the first item and pay 5 dollars. The second option is to get both items and pay 10 dollars. Furthermore, we always assume that the buyer also has the option to buy nothing and pay nothing. Out of all options, the buyer needs to choose a single one.\n\n> Does this scale with the upper bound of the distribution, of the distribution is not in $[0, 1]$, but in $[0,H]$?\n\nA: Yes, it does. Then, one needs to replace $\\varepsilon$ with $H \\varepsilon$."}, {"review_id": "7Jn3gTah9F", "reviewer": "Reviewer_xpkv", "summary": "The paper seeks to provide a theoretical foundation for empirical results demonstrating that optimal auctions (both known and novel) can be discovered by differentiable auction theory.  It proves that two such auction formats satisfy a condition called ‘mode connectivity’: epsilon-mode connectivity is satisfied when two (local) solutions are connected by paths in parameter space.", "questions": " - Dominant strategy incentive compatibility is a strong concept.  I would appreciate a few sentences on what that buys them relative to e.g. Bayesian-Nash incentive compatibility.\n - l.66: re: the link between epsilon-dropout stability and epsilon-mode connectivity, is it useful to think in terms of a Lipschitz constant?\n - l.92 mentions an example with 10,000 neurons and 59 active options: can this be expressed in terms of K?\n - lines 126-127: why do the menu options define a “piecewise linear surface of utilities”?\n - My overall intuition from this is that large neural networks can overfit: a large number of neurons could, further, yield inactive options, which (as they are dominated?) can be thrown away without loss.  Is something like this correct?  If so, it would be worth emphasizing that.\n - My guess is that we need no more than one ‘contract’ per type of bidder: is this correct?  If so, it should be mentioned (if it hasn’t been).\n - To me, the most curious result is the “five pieces” element of some of the RochetNet and AMA theorems: what explains this?  How much more general is it?  (Thus, could the results of S3, S4 be presented as special cases?)  Can anything more specific be said about the pieces?\n", "limitations": "None.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: to my knowledge, this work is novel.\n\n**Quality**: this seems well executed.\n\n**Clarity**: well-written.\n\n**Significance**: the overall significance of the paper is hard to assess.  Insofar as it provides a theoretical basis for existing empirical results, I feel that the bar for significance is cleared.\t\n", "weaknesses": "My main concern about the paper is that it identifies a perplexing regularity - that both the RochetNet and AMA results require \"five pieces\" - but then does not seek to understand that.\n\nMinor:\n - p.1: DSIC printed as DISC\n - l.79: “straight-jacket” or “strait-jacket”?\n- l.135: “each in unit supply” clearer\n - l.166: whenever I see “it is … easy to see”, I want to see at least a hint of explanation: I’ve tried to cover over results that I suspected to be true (but later discovered weren’t) this way.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading and assessing our paper and for the valuable feedback. We provide a detailed response to the raised issues / questions below:\n\n> p.1: DSIC printed as DISC\n\nA: Will be fixed, thanks!\n\n> l.79: “straight-jacket” or “strait-jacket”?\n\nA: This should be “straight-jacket”. We will add a reference for this.\n\n> l.135: “each in unit supply” clearer\n\nA: Will be added. Thanks!\n\n> l.166: whenever I see “it is … easy to see”, I want to see at least a hint of explanation: I’ve tried to cover over results that I suspected to be true (but later discovered weren’t) this way.\n\nA: The auction with a menu is DSIC, as the mechanism will provide the option with the buyer's maximal utility given the bid reported. Therefore, the buyer has no incentive to misreport.\n\nQuestions:\n\n> Dominant strategy incentive compatibility is a strong concept. I would appreciate a few sentences on what that buys them relative to e.g. Bayesian-Nash incentive compatibility.\n\nA: For single buyer cases (i.e. RochetNet), Bayesian-Nash incentive compatibility is equivalent to dominant strategy incentive compatibility. They become different when there are multiple buyers (Affine Maximizer Auctions). For example, in the paper \"Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison\" by Andrew Chi-Chih Yao, it is shown that these two concepts are different in the case when there are two buyers and two items. We want to emphasize that dominant strategy incentive compatibility is more robust than Bayesian one, as Bayesian-Nash incentive compatibility needs full knowledge of buyers' valuation distributions.\n\n> l.66: re: the link between epsilon-dropout stability and epsilon-mode connectivity, is it useful to think in terms of a Lipschitz constant?\n\nA: We are not exactly sure how to understand this question. Here is an attempt of an answer, please let us know if this is helpful: Lipschitz constant indicates that, for any point x, the function value does not change a lot within a neighborhood of x. However, when considering two distant points x and y which are far from each other, the Lipschitz constant does not provide a strong restriction on the function value along any path connecting x and y. It is possible that x and y are local minima of two valleys, and any path from x to y will encounter very high function values. In contrast, epsilon-mode connectiveity ensures this will not happen.\n\n> l.92 mentions an example with 10,000 neurons and 59 active options: can this be expressed in terms of K?\n\nA: Yes, K would be 10,000 in this example, and it seems that much fewer than all K menu options (namely only 59) are active.\n\n> lines 126-127: why do the menu options define a “piecewise linear surface of utilities”?\n\nA: We consider the relationship between valuation v and the utility u. According to the definition of RochetNet (see Section 2.1), $u = \\max_k v^\\top x^{(k)} - p^{(k)}$. This function u is a piecewise linear function in terms of v.\n\n> My overall intuition from this is that large neural networks can overfit: a large number of neurons could, further, yield inactive options, which (as they are dominated?) can be thrown away without loss. Is something like this correct? If so, it would be worth emphasizing that.\n\nA: From what we understand, your intuition is almost correct, and this is actually the main intuition behind Dughmi et al. [2014], which is the key tool in proving Theorem 9. However, one needs to be careful as it is possible that each neuron serves a very small region of valuation, and throwing these neurons may cause a large deviation of revenue. The way to deal with this is we also need to modify the remaining neurons after removing the others. Please let us know if this answers your questions.\n\n> My guess is that we need no more than one ‘contract’ per type of bidder: is this correct? If so, it should be mentioned (if it hasn’t been).\n\nA: Each buyer can only be assigned one option in the menu. However, even in the single-buyer case it might be crucial to offer the buyer many (for global optimality sometimes even infinitely many) options to choose from.\n\n> To me, the most curious result is the “five pieces” element of some of the RochetNet and AMA theorems: what explains this? How much more general is it? (Thus, could the results of S3, S4 be presented as special cases?) Can anything more specific be said about the pieces?\n\nA: The fact that our results work with five pieces stems from how our proofs work: we basically transform one menu into the other one in five linear steps. We do not know whether fewer than five pieces are possible, too. However, it also does not matter much: for us the most important message behind these five pieces is that it is a very simple structure: the path is not very complicated, it is just piecewise linear with very few pieces. It does not seem very relevant whether there are, say, 3, 5, or even 20 pieces.\n\nIt is therefore not surprising, that both cases yield exactly 5 pieces: since the proof strategies are similar, the results are similar, too. It is possible that the results of S3 and S4 could both be derived as special cases of something more general, but we think that this more general framework, if it exists, would be very complicated and unintuitive. It is probably more valuable to have a clean, short, readible proof that only works for RochetNet, and a separate, more technical version for AMA, as we present it in this paper."}]

Author rebuttal:

Meta-review: Recent work has shown that neural networks can be applied to learning optimal auction mechanisms, but their success has been largely demonstrated empirically. This paper attempts to provide a theoretical justification for the use of neural networks for auction design. They focus on a special case of menu-based auctions, and show that the neural network architecture in this case (dubbed as RochetNet) satisfies a property called "mode connectivity". This property has been shown in prior work to aid in better optimization using SGD.

All reviewers agree that the paper makes a solid technical contribution. Multiple reviewers, however, were concerned about the presentation not being clear, especially to an audience unfamiliar with auction design.

We strongly urge the authors to make the following changes to the camera-ready version:
- Make the introduction less technical and build intuition for what follows in the paper (Reviewer HRyy)
- Provide background material for a reader not entirely familiar with auction design and RochetNet (Reviewer HRyy)
- Explain clearly why mode connectivity is a useful property when applying SGD (Reviewers Cnd8, hKdM)
- Add a discussion on how a practitioner may benefit from mode connectivity (Reviewer Cnd8)

Please also incorporate other specific feedback the reviewers have provided.
Decision: Accept (poster)