Neural Design of Contests and All-Pay Auctions using Multi-Agent Simulation
Authors: Thomas Anthony
Ian Gemp
Janos Kramar
Tom Eccles
Andrea Tacchetti
Yoram Bachrach
Venue:  (2020)
Keywords: Auctions
Mechanism Design
Multi-Agent
Fictitious Play

Abstract: We propose a multi-agent learning approach for designing crowdsourcing contests and all-pay auctions. Prizes in contests incentivise contestants to expend effort on their entries, with different prize allocations resulting in different incentives and bidding behaviors. In contrast to auctions designed manually by economists, our method searches the possible design space using a simulation of the multi-agent learning process, and can thus handle settings where a game-theoretic equilibrium analysis is not tractable. Our method simulates agent learning in contests and evaluates the utility of the resulting outcome for the auctioneer. Given a large contest design space, we assess through simulation many possible contest designs within the space, and fit a neural network to predict outcomes for previously untested contest designs. Finally, we apply mirror descent to optimize the design so as to achieve more desirable outcomes. Our empirical analysis shows our approach closely matches the optimal outcomes in settings where the equilibrium is known, and can produce high quality designs in settings where the equilibrium strategies are not solvable analytically. 

Under review as a conference paper at ICLR 2020
NEURAL DESIGN OF CONTESTS AND ALL-PAY AUCTIONS USING MULTI-AGENT SIMULATION
Anonymous authors Paper under double-blind review
ABSTRACT
We propose multi-agent learning approach for designing crowdsourcing contests and all-pay auctions. Prizes contests incentivise contestants to expend effort on their entries, with different prize allocations resulting in different incentives and bidding behaviors. In contrast to auctions designed manually by economists, our method searches the possible design space using simulation of the multi-agent learning process, and can thus handle settings where a game-theoretic equilibrium analysis is not tractable. Our method simulates agent learning in contests and eval- uates the utility of the resulting outcome for the auctioneer. Given a large contest design space, we assess through simulation many possible contest designs within the space, and fit neural network to predict outcomes for previously untested contest designs. Finally, we apply mirror descent optimize the design so as to achieve more desirable outcomes. Our empirical analysis shows our approach closely matches the optimal outcomes in settings where the equilibrium known, and can produce high quality designs in settings where the equilibrium strategies are not solvable analytically.
INTRODUCTION
Many economic allocation decisions are determined by a competition for a prize based on expending costly efforts. For example, multiple political candidates may engage in costly political campaigns, but only one candidate wins; though only the winner is rewarded, other candidates cannot recover their expenditure. Similarly, Netflix offered prize of one million dollars in an open competition to improve its recommender system (Bell & Koren 2007). Again, only the winning entry gets the prize, but other participants incur the cost of their effort. Such contests are modelled the economic literature all-pay auctions [Vojnović 2015). where players simultaneously bid for a fixed prize; the highest bidder receives the prize, and every player, including non-winners, pay their bid.
A key question regarding crowdsourcing contests (or equivalently, all-pay auctions) is how to design the contest to optimize the utility achieved by the principal. [ For instance, should the principal give all the reward to the top entry, or does it make sense to give some of the reward to the top entry, and some for the second best? Earlier research has investigated how different contest designs affect the utility of the principal (Archak & Sundararajan 2009 DiPalantino & Vojnovie 2009 Gao al.) 2012 Chawla et al.) 2015). Such work examines a specific model of the aly- auction given a normal-form game and analytically solves for the Nash equilibrium of the bidding strategy, expressed as a probability distribution over the possible bids. This approach has multiple limitations. First, economists have only managed to solve for the Nash equilibrium under very specific auction designs. Secondly, in many settings, participants are likely to adjust their bidding strategy by using learning behaviors based on their experience (Gneezy & Smorodinsky.
al., 1998 Nanduri & Das 2007), so one cannot always assume the Nash equilibrium behaviour as model of participants' behavior when designing the contest.
We propose machine learning method for designing crowdsourcing con- tests, investigating how the principal's utility is affected by the reward allocation. By simulating the behavior of learning participants, and predicting the outcomes of contests with a neural network, our approach constructs a differentiable model for the principal's 's utility under various contest designs.
Our Contribution:
'The all-pay auction literature sometimes refers the principal as the auctioneer.

---

Under review as a conference paper at ICLR 2020
Given the model, we then optimize the design by employing mirror descent (Beck & Teboulle 2003 Nemirovsky & Yudin 1983). which allows optimizing the design while adhering to the fixed budget of the principal. Our approach is flexible: it can be applied to arbitrary mechanism design problems, including analytically intractable settings. It allows using various models for the behavior of par- ticipants. We apply fictitious play (FP) (Brown T951 Fudeeberg & Kreps) T993) independent
reinforcement learning (Littman 1994 Hu et al. 1998 Bu al. 2008).
We empirically evaluate our framework on several auction design problems. We study opti- mally allocating a fixed reward budget in the setting of contests with rank-order allocation of prizes, where the utility of submission has diminishing returns in effort.
We first examine contests with few participants and no performance noise, for which earlier research characterized the Nash equilibrium behavior (Baye al.) [996] Cohen & Sela 2008,, [isak 2009). We find that simulating participants' behavior using fictitious play closely agrees with the Nash equilibrium prediction, and our framework identifies a contest design near the optimal design prescribed by the economic equilibrium analysis.
Finally, we investigate contests where the performance of a participant's s entry determined by their exerted effort perturbed by random noise. Such uncertainty can be more realistic model of contests, but the Nash equilibrium behavior is unknown, highlighting the advantage of using our simulation based approach. We show that designs with multiple prizes outperform awarding single first prize in terms of principal utility. As the variance of the random noise grows, we find that the optimal designs award larger second prizes, acting to protect bidders against the effect of the noise.
1.1 OPTIMIZATION GOAL AND CONTEST DESIGN SPACE
We consider maximizing the principal's 's utility in crowdsourcing contest (or equivalently, the rev- enue of the auctioneer in an all-pay auction). We examine contests that award multiple prizes based on the rank ordering of the performance of the participants. For instance, a contest may award large first prize to the best performing contestant, and a smaller runner-up prize to the second best per- former. Offering more prizes could incentivise more participants exert effort, however smaller top prize means that the maximum bid possible is also reduced.
Consider a contest with n bidders. The principal decides on a division of fixed total prize w. The prize awarded to the htth ranked player is denoted Wk. so n W) = w. We insist that prizes are decreasing with rank, i.e. that w1 2 W2 2 ... 2 Wp. Awarding a last-place prize only reduces performance at equilibrium, as it reduces the incentive to exert more effort than other bidders, so we set w,, = O. Bidders each choose a bid (their effort level), and the vector of all bids is denoted as b. Effort is costly, so the payoff for bidder i is their prize winnings minus their effort:
sb(b) = Σ (b) - b,
j=1
where (b) = when player i's submission is ranked jth in terms of its quality, and 0 otherwise. Allocation is based on the ranking of the realized performance of the bidders. Some earlier work considers the realized performance to be deterministic given the bidder's effort (Baye et al.) 1996). whereas others model the performance as nosiy, stochastic, function of the effort (Amegashie) 2006). We also consider the performance 9: as a noisy function of the effort b,. indicating that participants have uncertainty about the exact effectiveness of their effort in producing high quality work. We model this uncertainty random additive noise on the effort level: d 6, b, where & is a random variable, drawn i.i.d for each contestant. We consider cases where e, 's distribution is either uniform 0). A bidding strategy a; of participant is a distribution over the bid levels. A set of bidding strategies o (o1,..., ...) is Nash equilibrium if for any bidder and any alternative strategy à;
Beta distribution (a 3 = }))) as well the noiseless case (i.c. e;
2 FP is only known to converge to Nash equilibrium in two-player zero-sum games (Papadimitrouu & Roughgarden 2008). and examine pay auctions, which are not zero-sum and have more than two partic- pantts. Nonetheless, empirically show that FP does converge the Nash equilibrium bidding strategies in the restricted settings where the Nash equilibrium is known.
SSmulations using multi-agent reinforcement learners, using simple REINFORCE Williams ers, exhibit noisier behavior. We discuss these results in the appendix.
1992
learn-
2

---

Under review as a conference paper at ICLR 2020
(alternative distribution over bid levels) we have s;(0) 2 s1(o-2,0,), i.. given the bidding strategy of others J-i. no player wants to unilaterally deviate from their strategy o, to any other strategy oz It is only known how to derive Nash equilibria for specific all-pay auction domains.
Given the realized performance of each contestant, the principal receives a utility as a function u of the maximum performance, i.e. u 4)) The utility function u describes how the performance of the bidders translates into value to the principal [ We consider the case of diminishing marginal returns on effort, modelled by a logarithmic utility function. Diminishing returns can also be used to model risk-aversion of the principal. We model a fixed entry cost of & that does not contribute to the solution quality [ Finally, we assume that the principal has some existing default solution with a utility of O. If no bid is better, the principal uses the default solution and receives a utility of O. Hence our principal's 's utility function is u(q) = max (log(a(q b)), 0), where a scale factor.
Goal: we seek to find the allocation w (wi...., w,) .n) of the total prize that maximizes the princi- pal's ss expected utility E,, (u(max; 9:)) (given how participants would behave in the resulting contest).
Multiple Nash equilibria may exist in where all bidders use the same strategy, distribution over bids between 0 and the maximum prize available. In the noiseless case, theoretical analysis of the symmetric Nash is possible; for fewer than 5 bidders the density function of the symmetric equilibrium can be derived exactly, while for larger numbers of bidders it can only be sampled from. We present this analysis in appendix
auctions. We focus on the symmetrrc case,
2
METHODS
Our approach for automating the contest design process is illustrated in Figure [] Shortly, we sim- ulate agent learning in contests under various designs and record the resulting utilities. Next, we generalize from the training data by fitting parameterized mapping from designs utilities. Be- cause the mapping is differentiable, it allows gradient based optimization in the continuous space of designs, so we apply an optimization procedure to identify the optimal design under the model. We provide a detailed discussion of our method, with formal description in Algorithm 2
We begin by investigating set D of possible possible contest designs. As discussed in Section I.] a design for n bidders is characterized by the reward distribution w = -W],... W.,), lying on the simplex (i.e. Σ W; 1). Given a design leam to bid under this design. For the simulation, we use fictitious play (Brown) 1951), one of the
D, our framework simulates how agents would
most prominent models for how an agent may learn and adapt their strategy; We also discuss other alternatives such as independent multi-agent reinforcement learning (Littman] 1994). We emphasize that our method is flcxible and may use any model for agent learning in our simulation.
For design d E D, the output of the simulation are the bidding strategies aa of agents under this design, where σa is a distribution over the bid levels. Given the bidding strategies aa and contest simulation, we can also determine the expected utility us for the principal, as given in Section L.1 (the subscript indicates the bidding strategies and the principal's utility depend on the contest design d). By performing the simulation for many designs di,.. ..,..., dy chosen from the design space D, we obtain a simulation dataset ((de, ud, |/2 where d; E D is a design and u. is the expected utility the simulation shows it would generate for the principal (shown in the left of Figure I..
Using the simulation dataset, we train a differentiable model to predict the principal's utility ua under contest design d E D (including designs not observed during training). In other words, the true model for the principal's utility is a function m : D + R, mapping any possible contest design in D to the utility it would provide to the principal. We approximate m using a neural network, trained on simulation data, yielding the approximate function mø D + RR (where O are model parameters). We use a simple feedforward network trained on many auction designs (see full details regarding architecture and training in Appendix B depicted in the middle of Figure |
Given mp, we aim to identify designs resulting high utility for the principal; Our goal is thus to "reverse engineer" the model, seeking inputs causing the model to output high value reflecting
'In the noiseless case, when is invertible this is equivalent to specifying cost function c(b:) on the bid where e = x= as done in previous work (Vojnović 2015).
'For instance in the Netflix competition, contestants had to perform some work just to enter the contest, e.g. downloading data or reading documentation, efforts that provide no value the principal.
3

---

Under review as a conference paper at ICLR 2020
high utility to the principal. The model is differentiable, output with regard to the inputs Ww (w)) allowing gradient-bad baasen optimization. A key challenge here is that the imput design (W),..... w,) must respect the principal's 's budget, i.c. Σi=1 W; w. As illustrated on the right of Figure I we perform the optimization while adhering to the principal's budget by employing form of entropic mirror ascent (Beck & Teboulle 2003), given in Algorithm[]
can calculate the gradient of the
below. We now describe the data generation (Step 1) and design optimization (Step 3) in more detail.
Simulate Agent Learning and Outcomes under Different Designs
Fit Differentiable Model !
Optimize Over Designs
*un+ + vV
Algori chm
((Design, Utility]]
Figure I: Diagram of the contest design process (Algorithm 2 Step 1) Simulate contests and agent learning to determine the utility of possible designs. Each data point represents an (contest design, utility) pair. Step 2) Fit a deep network to predict utility given contest design. Step 3) Optimize the output (utility) over the input (contest design) of the deep network find the optimal design.
2.1 DATA GENERATION
We generate data train the model me by simulating the learning process of agents in contests of a given design. The simulated contest receives bids as input and returns the rewards carned by the participants, learning. In FP, each the agents adjust distribution over discrete bid levels by computing the best response historical play. We use FP is well-established model of agent learning strategic settings. However, we emphasize that there are many alternative algorithms that can be used as the simulation method in our framework.
well the principal's revenue. We use FP (Brown 195T) as model of agent
Multi-agent independent RL (MARL) is an appealing simulation alternative. We discuss how our empirical results change as we switch from FP to MARL in the appendix. Various surveys contain detailed comparison of FP, MARI. and other methods (Claus & Boutilier] 1998) Shoham et al.) 2003 Yang & Gu 2004). In 3-bidder auctions, we found that MARL agreed with Nash for large first prizes 0.8w), but deviated significantly from Nash with smaller first prizes (< 0.7w)
2.2 DESIGN OPTIMIZATION
As discussed in Section 1.1 the contest design space is a convex set, the simplex E W; w. Entropic Mirror Ascent Beck & Teboulle 20033 is non-euclidean gradient ascent method from the convex optimization literature, specifically designed for simplex constraints. The optimizer update rule for design, w is: w +- softmaa (log( w) 1/Vmg(w)) where ma(w) represents the neural model's predicted utility for input design w. By inspection, w remains the simplex after the update and log(w) w) always defined as long as w = Wo is initialized to the interior of the simplex.
The simplex constraint for (W],-.., -.. wx,) is insufficient. Having prizes that not monotoni- cally decreasing in rank gives participants an incentive to attempt to obtain a lower rank (as they get higher prize for exerting less effort). Hence, we want designs with strictly monotonically decreas- ing prizes and zero last prize (giving prize to the lowest quality submission is wasteful, causing lower efforts). We propose a modified entropic mirror ascent procedure to constrain iterates this region of the simplex with transformation. For example, in an (n=4) four bidder contests, let w = [21 + 22 + 23, 22 + 23, 23, 0) where 2, 0. 2; denotes the marginal increase of the prize from that of rank i- to that of rank This sequence is strictly monotonically decreasing. The simplex constraint implics 21 + 22g- + 323 L. Let e be the vector of coefficients, e.g., e = [1, 2, 3]. and entropic mirror descent ž and transform back to 2 with 2 = ž/c. We formally express this idea in the transformation given in Algorithm where and denote element wise multiplication and division respectively, A denotes the in- ei
define 7, 2 Then E lives on simplex. We can
terior of the n-1 dimensional simplex, w[i:j] [w,.... ., wy-1], softmax(y) Σ, c5 rev reverses array, and cumsum(y) denotes the cumulative sum, i.e., [y1. 1/1 y2 ....... Eg Vg].
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Monotonic Entropic Mirror Ascent (M-EMA)
INPUT: initial design wo. with wo[0:n-1] A utility neural net mo(w): R >R, number of optimization iterations K, learning rate
w00nn11 w[1:n]
= [1, 2, 71
for 1: K do
2 & sof softmax(log(e @ 24) + + ()V=m((2)) ee
end for
Wx 00m-1] rev(cunsum(rev(2))
OUTPUT: WK
2.3 CONTEST DESIGN USING SIMULATION, LEARNING AND OPTIMIZATION
Algorithm describes the overall contest design optimization method, described informally in the beginning of Section It samples contest designs (we use Dirichlet distribution 1 uses FP simulate agent learning on each design, trains a neural network for predicting the princi- pal's revenue and finally uses Algorithmll [ to optimize the design.
Algorithm 2: Neural Auction Design
A agents (bidders), utility metric, presumed optimal design Wo, with wo -nn 1] E int empty dataset DD number auction simulations M, untrained neural net- work mg (w). number of optimization iterations K.
INPUT:
for m = M do
Sample design E D: w|0:n-1] Di=n--(Q=1), w/n- 0. Sort (decreasing).
Use FP to simulate contest until convergence, obtaining participant strategies a. Fix agent strategies ar, simulate contests compute expected auctioneer's utility ua(a). Record (design d, expected utility u.)) pair to dataset K.
end for
Train neural network, ma(w), to regress on M samples from KC
Optimize design using Algorithm [ w + M EMD(Wo, mq)
OUTPUT: w
3 EXPERIMENTS
Section 1.1 describes various assumptions one can make regarding the performance noise model and the utility of the principal in crowdsourcing contests. We applied work to optimize the design of crowdsourcing contests under various such assumptions. our experiments, we consider the principal's utility function to be the one given in Section [.] u(g) = maax(ll((((xaaaa - 0), which reflects a risk averse principal, with a minimal quality bar.
proposed frame- all
Section 3.1 shows empirical results for domain with three four bidders, and noiseless perfor- mance. As discussed in Section in this model the symmetric Nash cquilibrium strategy is known. Our analysis shows that the FP simulation results in agent behavior that is extremely close to the Nash equilibrium prediction. Further, after fitting a differentiable model and optimizing the design using Algorithm
2
we obtain the same optimal design prescribed by equilibrium based analysis.
Section 3.2 considers settings where the equilibrium behavior is not known, so standard economic techniques struggle to recommend an optimal design. We consider settings with 10 participants and various performance noise models, and apply our framework to identify the optimal design. We show that our designs award prize money to a few top entrants. As the variance of performance noise increases, optimal designs award more prizes, and larger prizes to the runner-up in the contest.
3.1 MODELS WITH KNOWN EQUILIBRIUM BEHAVIOUR
Consider a setting with three or four bidders, and with no performance noise. The first step in our framework is simulating agents who leam from repeated interaction in the contest, by applying FP.
5

---

Under review as a conference paper at ICLR 2020
We first investigate whether the predictions of FP agree with the Nash equilibrium strategies. In general FP may not converge to a Nash equilibrium as an all-pay auction is not a constant-sum or dominance solveable game (Jafari et al.] 2001] [Shamma & Arslan 2005). Furthermore, the solution found with fictitious play is to a discrete version of the auction (where bids take one of a discrete set of values), whereas the analytic solution is for the case where bids can take any real value.
The top left of Figure shows the symmetric Nash equilibrium bidding strategy, as the cummulative distribution function (CDF) of the distribution over bid levels, under multiple three bidder contest designs, characterized by the prize for the top rank (the remainder prize goes to the second rank, and the prize for the third rank zero). The remaining plots of Figure 2 each examine one design (characterized by the first rank prize), and plot the bid CDFs of the Nash equilibrium versus those outputted by FP, Figure 2 shows that the FP output closely matches the Nash equilibrium.
Nash Bidder CDF 10.6.103
Bidder CDF Price
Bidder CDF [First Prize
0.5
0.5
02
Nash
Noch FSP (best)
FSP (best)
0.-
Bidder CDr (First 0.8)
(a) Bidder CDI (rirst Prize 0.9)
In Bidder CDI Ohisst Prize
10-
0.-
06.
04
02
Nachh
Narh
(bend)
PSP (bent)
PSP
0.
00
Figure 2: Bidding strategy CDFs, The top left plot shows the CDFs for each of five different contest designs assuming the bidder plays the Nash distribution. The first prize is listed in the legend; the second prize equals one minus the first; no prize is given to the third bidder. The remaining plots compare the Nash CDF with the CDF learned by fictitious self-play for different first prize amounts.
The next phase in our pipeline takes the dataset of simulation outcomes under various designs, and trains a neural network to predict the principal's utility in any given contest design (attempting to generalize to unsimulated designs). Figure 3 compares the principal's 's utility under Nash bidding against the prediction of our trained model for various designs (characterized by the first rank reward, shown on the x-axis). We observe that the simulation results for the principal's 's utility are consistently very slightly below the Nash-based analytical solution. The model has an almost perfect fit to the simulation results. The final step of our method is optimizing the contest design given the model (Algorithm [p. The optimal design is marked in Figure 3 for both the Wash-based curve and our method. These match almost perfectly (the location on the x-axis is almost identical), indicating our method finds the same optimal design as prescribed by the Nash equilibrium analysis.
Finally, we explore a four bidder contest to investigate the effect of possible designs on the princi- pal's utility. Figure 4 shows a heatmap for the principal's 's utility for possible designs. The x-axis is the reward wi. the prize for the first rank, and the y-axis is the reward we for the second rank (the lowest rank gets no reward wy 0, and the third rank reward is W3- w - w1 w2)). Figure shows that the utility is fairly robust to designs with a high first prize, i.c., W1 E [0.7 - 0.9) and third prizes w3 .I. However, good designs with a low first prize (e.g. W1 < 0.7) offer no reward the third rank. This indicates that in settings with many participants we might expect a greater distribution of reward across top prizes, but the principal's I's utility may be fairly robust around the optimal design.
3.2 MODELS WITH UNKNOWN EQUILIBRIUM BEHAVIOUR
We explore contests where the each participant's 's bid is perturbed by random noise to yield their performance. We consider noise following either a uniform or a Beta( } 1) distribution. Due to the noise distribution, the Nash equilibrium bidding strategy is not known for this setting. We apply our method on such contests, and investigate how the optimal design is affected by the noise distribution.
Figure 5 shows heatmaps of the principal's 's utility in the noisy setting (uniform noise the left and Beta noise on the right), under different contest designs. Similarly to Figure the axes are the wi and W2, the last prize is wa 0, and W3 w1 w2- Figure 5 shows that more noise is

---

Under review as a conference paper at ICLR 2020
Auctionear Ltility First
Principal's Utiliyy Heatmap
0.4
6005
0.830
0.28
033
1992
Second
0.822
6061-
0.020
6003
0.018
644
00
0.836
6093
350 0
610
First Prize
Figure 3: Principal's 's utility as a function of the first rank prize, as given by the analytical Nash CDFs, the simulation data, and the trained neural network. Markers denote maxima.
Figure 4: Heatmap for the principal's utility for various four bidder contest designs. The star marks the optimal design.
introduced to the bids, the optimal designs tighten around more evenly distributing reward across the top two bids (in both cases in the optimal design Wy 0). In other words, the noise increases, the optimal design transfers more reward from the top rank to the one below it.
Principal's Ubllit Heatmap
Principal's Utility Heatmap
05
04
0.84
06
g4
05
0.35
03
02
0.811
02
0080
Second Prbze
Second Price
01
0.825
0.855
0.820
022
0.22
0.2
0815
01
0.166
0.1
0.13
0.800
First Prize
First Prize
Figure 5: Heatmaps for the principal's utility in four bidder contests with realized bids drawn from an interval [bid- + either (L) uniformly or (R) according to Beta( 2: 2). d = 0.06. Plotted on top of the heatmap are arrows to the optimal designs for different values of d annotated on the map.
We now investigate contests with more participants, showing how the performance noise affects the optimal design. Figure 6 shows the optimal design for performance noise levels. We only illustrate the top 3 prizes in a 3D plot (lower ranks typically get very little or no reward under the optimal design). Figure 6 shows that increasing the noise makes the optimal design spread the reward more evenly among the top ranks. Table shows the same effect as table. giving the optimal design and inequality in prize levels.
10 participants, under different
Finally, we investigate the limitations of our approach. Our framework may suggest sub-optimal design due multiple issues. First, the simulation of how participants learn may not be accurate model of their behavior. Second, the neural network may may have an approximation error in predicting the principal's utility. Third, the optimization procedure (Algorithm I may converge on a local rather than global optimum. Figure 7 illustrates the generalization error contrasting the principal's 's utility when running the FP simulation and when predicting it using the trained model on previously unobserved designs. We note that the neural network's 's predictions are slightly different from the simulation data, though they follow similar trends. Further, Falure7also marks the location of the optimized design suggested by Algorithm 2 with star, showing how slight errors occur due to convergence to local rather than global optimum (e.g. in the figure for the third rank prize).
RELATED WORK AND CONCLUSION
Crowdsourcing contests and all-pay auctions have received significant attention in the economic literature, including recently published surveys and books focusing the topic (Vojnović) 2015 Dechenaux et al. 2015). We propose a neural approach to designing crowdsoureing contests. Earlier work has carried out equilibrium analysis for several restricted models of all-pay auctions (Milgrom)
7

---

Under review as a conference paper at ICLR 2020
17
106
w1
102
Gini
0.000
1.000
0.000
0,000
0.900
0.002
0.916
0.084
0.000
0.883
1.0
0.004
0.850
0.075
0,075
0.855
0.8
0.006
0.848
0.152
0.000
0.870
a211 PINL
0.008
0.733
0.260
0.004
0.844
0.010
0.500
0.500
0.000
0.800
0.4
0.020
0.500
0.500
0.000
0.800
0.2
00
0.030
0.500
0.500
0.000
0.800
0.0
0.0
0.2
0.4
0.
First Prize
0g
02
0.050
0.040
0.461
0.471
0.319
0.325
0.204
0.209
0.746
0.753
Second Prize
0.8
10
10
0.060
0.443
0.319
0.152
0.724
Figure 6: First three prizes of the optimized ten bidder contest plotted on top a simplex for refer- ence. Each point denotes the optimal design for a different noise level. The square marks zero noise with the trajectory ending at the star with realized bids drawn uniformly from bid #0.06.
Table 1: First three prizes of the optimal ten bidder auction given by Algorithm 2 Prizes given fifth and higher are all zero Width of the uniform distribution around bidder's bid is specified in w column: Gini index of each design is in the last column.
Pridds by Price
pold Unilit
Prinopol Utilit Prec
Pntocipais Ltiityy
Us
PMCC 2M0 CAR
421
010
Figure 7: Utility for the ten bidder contest vs the top four prizes with realized bids drawn uniformly from bid +.06. Note plots are shown on different scales and for different slices of the design space.
& Weber 1982 Baye et al. 1993: 1996 Krishna & Morgan 1997
Amegashie 22066] Siegel 2209).
including the impact of rvsk-aversion (Fibich et al., | |006]] Gao et al.
(012). Empirical evaluation of
how people actually bid in such settings has revealed significant discrepancies with the predictions of the equilibrium based analysis (Rapoport & Amaldoss) 2004, Gneezy Smorodinsky, 2006)
Liu et al. 2014). Such empirical work suggests that people tend to employ simple learning heuris- ties Rappoprtt& & Amaldoss] 2004; Dechenaux et al. 2015)).
rank reward allocation, in order to maximize its utility. This broadly falls in the field of mechanism design or auction design (Myerson) 1981 Nisan & Ro- nen. 2001), subfield in economics, seeking decide the "rules of the game"
We examine a principal deciding
to achieve desired outcomes. Typically, auctions are designed manually by economists seeking to maximize revenue (Myerson| 1981 Bulow & Roberts 1989 Roth 2002).. In contrast,
aulomate the pro- cess, similarly to the recent field of automated mechanism design (Conitzer & Sandholm, 2002 Sandholm 2003 Conitzer & Saanhholm 2004 Hajiaghayi al. 2007 Guo & Conitzer 2010).
We use machine learning to search the space of designs, akin to recent deep-learning mechanism de- sign frameworks proposed for other auction types (Dütting al., 2017 Feng et al. 2018, Manisha et al., 2018 Tacchetti et al., 2019). In contrast to these, we leverage agent learning of the auc- tion (Mizuta & Steiglitzi 2000; Vorobeychik Wellman (008). Learning agents are increasingly capable of solving complex problems; using such capable agents for mechanism design holds the promise of optimizing the design of mechanisms in more complex settings than previously possible.
Our empirical analysis shows the promise of automated mechanism design based on deep learning- However, our technique has several limitations, such as the dependence on a good model for the learning of agents, and errors introduced by inaccurate function approximation and converging on local optima. Several questions are open for future research. Can our methods generalize well to other mechanism design domains such as other types of auctions? What good models of agent learning in other strategic settings? Do such models do a good job in characterizing the bidding behavior of human participants? Finally, can better methods be devised to optimize over designs?
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
J Atsu Amegashie. A contest success function with a tractable noise parameter. Public Choice, 126 (1-2):135-144, 2006.
Simon P Anderson, Jacob Goeree, and Charles A Holt. Rent seeking with bounded rationality: An analysis of the all-pay auction. Journal of Political Economy, 106(4):828-835 1998.
Nikolay Archak and Arun Sundararajan. Optimal design of crowdsoureing contests. ICIS 2009
proceedings, pp. 200, 2009.
Michael R Baye, Dan Kovenock, and Casper G De Vries. Rigging the lobbying process: appli- cation of the pal-pay auction. The american economic review, 83(1):289-22 294,, 1993.
Michael R Baye, Dan Kovenock, and Casper G De Vries. The all-pay auction with complete infor- mation. Economic Theory, 8(2):291-305, 1996.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Robert M Bell and Yehuda Koren. Lessons from the netflix prize challenge. SIGKDD Explorations, 9(2):75-79, 2007.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Lucian Bu, Robert Babu, Bart De Schutter, et al. A comprehensive survey of multiagent reinforce- ment learning. IEEE Transactions on Systems, Man, and Cybernetics, Part (Applications and Reviews), 38(2): 2008.
Jeremy Bulow and John Roberts. The simple economies of optimal auctions. Journal of Political Economy, 97(5):1066 060-1190,, 1989.
Shuchi Chawla, Jason D Hartline, and Balasubramanian Sivan. Optimal crowdsourcing contests. Games and Economic Behavior, 2015.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems. AAAI/IAAI, 1998(746-752):2, 1998.
Chen Cohen and Aner Sela. Allocation of prizes in asymmetric all-pay auctions. European Journal of Political Economy, 24(1):123-132 2008.
Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. In Proceedings the Eighteenth Conference on Uncertainty in Artificial Intelligence, pp. 103-110. Morgan Kaufmann Publishers Inc., 2002.
Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implica- tions for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference Electronic Commerce, pp. 141. ACM, 2004.
Emmanuel Dechenaux, Dan Kovenock, and Roman M Sheremeta. A survey of experimental re- search on contests, all-pay auctions and tournaments. Experimental Economics, 18()):609-66,, 2015.
Dominie DiPalantino and Milan Vojnovic. Crowdsourcing and all- all-pay auctions. In Proceedings of the 10th ACM conference on Electronic commerce, pp. 119-128. ACM, 2009.
Paul Dütting, Zhe Feng, Harikrishna Narasimhan, and David C Parkes. Optimal auctions through deep learning. arXiv preprint arXiv:1706.034455 2017.
Zhe Feng, Harikrishna Narasimhan, and David C Parkes. Deep learning for revemue-optimal auc- tions with budgets. In Proceedings the 17th International Conference Autonomous Agents and MultiAgent Systems, pp. 354-362, International Foundation for Autonomous Agents and Multiagent Systems, 2018.

---

Under review as a conference paper at ICLR 2020
Gadi Fibich, Arieh Gavious, and Aner Sela. All-pay auctions with risk-averse players. International Journal of Game Theory, 34(4):583-599 2006.
Drew Fudenberg and David M Kreps. Learning mixed equilibria. Games and Economic Behavior, 5(3):320-367, 1993.
Xi Alice Gao, Yoram Bachrach, Peter Key, and Thore Graepel. Quality iopectatioonvariinee trade- off's in crowdsoureing contests, In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
Uri Gneezy and Rann Smorodinsky. All-pay auctionsan experimental study. Journal of Economic Behavior Organization, 61 (2):255-275, 2006.
Mingyu Guo and Vincent Conitzer. Computationally feasible automated mechanism design: General approach and case studies. In Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mecha- nism design and prophet inequalities. In Twenty- Fiesst-FFrrstt AAAI Conference on Artificial Intelligncce volume 7, pp. 58 65, 2007.
John Joseph Horton and Lydia B Chilton. The labor economics of paid crowdsoureing. In Proceed- ings of the 11th ACM conference on Electronic commerce, pp. 209-218. ACM, 2010.
Junling Hu, Michael P Wellman, et al. Multiagent reinforcement learning: theoretical framework and an algorithm. In ICML, volume 98, pp. 242-250. Citeseer, 1998.
Amir Jafari, Amy Greenwald, David Gondek, and Gunes Ercal. On no-regret learning, fictitious play, and nash equilibrium. In ICML, volume 1, pp. 233, 2001.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900 69800, 2014.
Vijay Krishna and John Morgan, An analysis of the war of attrition and the all-pay auction. journal of economic theory, 72(2):343366,, 1997.
Michael L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Tracy Xiao Liu, Jiang Yang, Lada A Adamic, and Yan Chen. Crowdsourcing with all-pay auctions: A field experiment on tasken. Management Science, 60(8):2020-2000 2014.
Padala Manisha, CV Jawahar, and Sujit Gujar. Learning optimal redistribution mechanisms through the 17th International Conference on Autonomous Agents and MulliAgent Systems, pp. 345-353. International Foundation for Autonomous Agents and Multia- gent Systems, 2018.
neural networks. In Proceedings the
Paul R Milgrom and Robert J Weber. A theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society, pp. 1089-1122, 1982.
Hideyuki Mizuta and Ken Steiglitz. Agent-based simulation of dynamic online auctions. In 2000 Winter Simulation Conference Proceedings (Cat. No. 00CH37165), volume pp. 1772-1777.
IEEE, 2000.
Roger B Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73, 1981.
Vishnuteja Nanduri and Tapas K Das. A reinforcement learning model to assess market power under auction- based energy pricing. IEEE transactions on Power Systems, 22(1):85 95, 2007.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Noam Nisan and Amir Ronen. Algorithmic Mechanism Design. Games and Economic Behavior, 35(1-2):166-19, 2001.
Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3):14, 2008.
10

---

Under review as a conference paper at ICLR 2020
Amnon Rapoport and Wilfred Amaldoss. Mixed-strategy play in single-stage first-price all-pay auctions with symmetric players. Journa of Economic Behavior Organization, 54(4):585- 2004.
Alvin Roth. The economist engineer: Game theory, experimentation, and computation as tools for design economics. Economelrica, (14)):341-1331 2002.
Tuomas Sandholm. Automated mechanism design: A new application area for search algorithms. In International Conference on Principles and Practice of Constraint Programming, pp. 19-36. Springer, 2003.
Jeff $ Shamma and Gürdal Arslan. Dynamic fictitious play, dynamic gradient play, and distributed convergence to nash equilibria. IEÉE Transactions on Automatic Control, 50(3):312-377, 2005.
Yoav Shoham, Rob Powers, and Trond Grenager. Multi-agent reinforcement learning: critical survey. Web manuscript, 2003.
Ron Siegel. All-pay contests. Econometrica, 77(1):11-2,, 2009.
Dana Sisak. Multiple-priiee contests - the optimal allocation of prizes. Journal of Economic Surveys, 23(1):82-1 114, 2009.
Andrea Tacchetti, DJ Strouse, Marta Garnelo, Thore Graepel, and Yoram Bachrach. A neural archi- tecture for designing truthful and efficient auctions. arXiv preprint arXiv:1907.08 2019.
Milan Vojnović. Contest theory: Incentive mechanisms and ranking methods. Cambridge University Press, 2015.
Yevgeniy Vorobeychik and Michael Wellman. Stochastic search methods for nash equilibrium approximation in simulation-bart based games. In Proceedings of the 7th international joint con- ference on Autonomous agents and multiagent systems- Dystems-Volume 2, pp. 1055-1062. International Foundation for Autonomous Agents and Multiagent Systems, 2008
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229 1992.
Erfu Yang and Dongbing Gu. Multiagent reinforcement learning for multi-robot systems: A survey. Technical report, tech. rep, 2004.
Haichao Zheng, Dahui Li, and Wenhua Hou. Task design, motivation, and participation in crowd- sourcing contests. International Journal of Electronic Commerce, 15(4):57-83 -8, 2011.

---

Under review as a conference paper at ICLR 2020
A SIMULATIONS USING FICTITIOUS PLAY AND INDEPENDENT MULTI-AGENT REINFORCEMENT LEARNING
The discussion in the main text has focused no applying Fictitious Play (FP) (Brown 1931 Fuden-
berg & Kreps 1993) for the simulation phase. As we discussed, an alternative is applying indepen- dent multi-agent reinforcement learning (Littman 1994 Hu et al. 1998: Bu et al. 2008). We now
provide an empirical analysis of the choice regarding the simulation phase.
We first note that FP operates by applying simple learning rule: each agent assumes the opponents play stationary (mixed) strategy. In each each round, every player chooses the best response to the empirical frequency of play of their opponents. The key parameter determining the computational cost of the simulation is this the number of such simulation rounds. Figure X investigates the impact of the number of rounds on the learned bidding strategies (distribution over bid levels), contrasting with the Nash equilibrium for the game. It shows that same results as Figure in the main text, but for varying number of FP rounds and discretization granularities for bid levels.
(al Nash Bidder CDF (First Prize (0.6.003
[b) Bidder CDF (First Prize 0.
(c) Bidder CDF [First Prize 0.7)
1.-
0.0
0.6
294
04
FSP (vary kers) (very levelo) (best)
Nach
Nach
FSP (vary itrs) Evary level)) (sest)
10
Bidder CDF (First 0.8)
(e) Bidder CDF (First Prize
In Bidder CDF tiisst Price 1.0)
100 iters
Nash
Nash
Nush
1000
PSP (vary Bers]
PSP (very hams)
FSP (very iteo)
ters
HSP teary lovcto)
PSP teary loxcha) (best)
HSP owary lovob)
PSP (test)
Obestt
0.
04
0.
08
0.0
bed
bid
bd
Figure& 8: This figure compares the bidder CDFs. The top left plot shows the CDFs for each of five different auction designs assuming the bidder plays the Nash distribution. The first prize is listed in the legend; the second prize equals one minus the first; prize is given the third bidder. The remaining plots compare the Nash CDF with the CDF learned by fictitious self-play for different first prize amounts. Figures (b-d) also show the effect of training iterations and discretization granularity on the final CDF. The arrow in Figure (c) highlights a common trend where the CDF converges to Nash from above as a finer discretization is introduced. In other words, coarser discretizations lead to under bidding and, in turn, underestimates of the auctioneer utility. Figure (d) shows that increasing training iterations reduces error, but a less structured manner than bid granularity.
Figure 8 indicates that the number of FP rounds and the granularity of discretization of bid levels have an impact the learned bidding strategies. However, the results are somewhat robust to the choice of these parameters, yielding relatively similar bidding strategies under many settings (and in most settings the results are qualitatively very similar the Nash equilibrium).
We now turn to investigate using multi-agent reinforcement learning (MARL) for the simulation phase. Independent MARL based methods have recently become very popular means of modeling agent behavior in multi-agent environments. Such approaches have the advantage of being simple and relatively easy to implement. We have used independent REINFORCE agents (Williams) 1992), and investigate the bidding strategies learned by the agents. The bidding strategies learned using MARL are shown in Figure g and are contrasted with both the Nash equilibrium bidding strategies and the bidding strategies learned via FP (similarly to Figure and Figure 88. These results show that for large first prizes (where the first prize is 0.8 or higher), all three methods yield a relatively similar distribution. However, there is a significant deviation for lower top prizes, where the RL distribution has a step function curve.
The results in Figure 9 indicates that the model for agent learning may have significant impact on the assumed bidding strategies (and hence on the choice of a design). Ultimately, we feel like this is a modelling decision the user's side. In other words, in order to choose a good design, one must first determine what is a reasonable model of the learning behavior of agents. In the case of crowdsourcing contests (all-pay auctions), using the FP learning rule yields results that
12

---

Under review as a conference paper at ICLR 2020
Nash (0.6.00))
0.6)
Prize 0.7)
02-
PSP
00
10
Bidder CDF IFins Price 0.8)
Bioder CDF (First Prize 0.9)
Bidder CDF (First Prize 1.0)
160 b90
0.-
06
0.
02
0.
00
02
Figure 9: This figure compares the bidder CDFs. The top left plot shows the CDFs for each of five different auction designs assuming the bidder plays the Nash distribution. The first prize is listed in the legend; the second prize equals one minus the first; no prize is given to the third bid- der. The remaining plots compare the Nash CDF with the CDFs learned by fictitious self-play and REINFORCE respectively using their optimal hyperparameter configurations (iterations, bid levels, learning rate, batch size). Both REINFORCE and fictitious self-play agree closely with the Nash equilibrium when the first prize 2 0.8. For smaller prizes, there is a larger discrepancy. We see that FP is consistently closer to the Nash equilibrium than REINFORCE.
are more similar to those used in traditional Nash equilibrium based analysis. In contrast, if one believes agents are more likely to be reinforcement learners, an alternative bidding strategy a likely outcome. One possible choice is conservative approach, where one only considers design where there a consensus between simulation learning rules (e.g. FP or MARL). In this case, one may opt for a large top prize, in this case, the different models for agent learning behaviour agree with each other.
B DESIGN PROCESS ARCHITECTURE AND HYEPRPARAMETERS
To aid reproducability, we now provide full details regarding our network architecture and hyperpa- rameters.
For our neural network mp, we have used a simple feedforward network with 2 hidden layers, 256 neurons per layer, and ReLU nonlinearities. We trained the network for 10, 000 iterations using the Adam optimizer Kingma & Ba (2014) with a learning rate= using with default 31 = 0.9, B2 0.999 and mini-batches of size 51 for the 3 bidder auction and 1000 for the 10 bidder auction.
Design Optimization (E-EMA): We initialized designs such that the first prize was given 0.9 and all remaining marginals were given constant 2;>1 We performed 100, 000 iterations of E-EMA with learning rate of 0.1 for the bidder auction and 200, 000 iterations with a learning rate of 0.001 for the 10 bidder auctions.
Principal Utility Fuction: We set a 50 and b 0.1 (see Figure 10
Fictitious Play: We fictitious play for 100, 000 iterations with discretization of 1001 ef- fort levels for the bid interval [0, 1]. We were searching for a symmetric equilibrium so all bidders played using the same bid distributions, i.e. using fictitious self-play.
C ANALYTIC RESULTS ON NOISELESS AUCTIONS
We now very briefly discuss how ing contests. A more detailed discussion of this can be found in contest theory textbooks (Vojnovid) 2015) and in various papers all- all-pay pay auctions (Milgrom & Weber 1982 Baye et al. 1993 1996
solve for the closed form bidding strategies in crowdsoure-
13

---

Under review as a conference paper at ICLR 2020
Principal's Utility Max Quality Bid
1.0
0.8
Principal's Utility
0.6
0.4
0.2
0.0
r
0.0
0.2
0.4
0.6
0.8
1.0
quality bid (q)
Figure 10: The principal's utility function: max(log(a(q - b)),
Krishna & Morgan 1997.
Siegel
2009
DiPalantino
Vojnovic
2009 Horton & Chilton 2010
Zheng et al. 2011p.
We are interested in finding the symmetric Nash equilibrium for an all ply-pay auction, as discussed in Section [.] In symmetric Nash equilibrium, all bidders use the same bidding strategy a, which simply a distribution over the bid levels. symmetric Nash equilibrium, no bidder i wants to unilaterally deviate from to alternative bidding strategy ō;.
We write the CDF bidding strategy as B(b), and attempt to identify the symmetric Nash equi- librium. First note that this equilibrium strategy is atomless. If it weren't, agents bidding at the atom could achieve non-infinitesimal increases their expected prize money by increasing their bid infinitesimally as to outperform all other bids at the atom, therefore B would not be Nash.
The expected prize money from bidding b when all bidders are following the bidding strategy B is given by:
n my (Bbb)B())) where G,(z) = 100-0111 (1-1)
2 n- zn z)-11
Each term of the sum is simply the value of the jth prize wy times the probability G, (B(b)) that bid of percentile (b)) achieves rank against set of n independent bids drawn from B.
Proposition:
The symmetric Nash equilibrium results in expected value of 0 to all participants.
Proof: B(0) = 0 and B is continuous because B is atomless.
We write the expected utility when bidding against opponents bidding according B as s(b; B)
Choose 5 > O. The value s(b; B) of bids b < (8) is bounded by the expected prize money under those bids, i.e.
s(b; B) < wi (B(()) < Σ G5())
Since G, tends to 0 as tends to 0, for any >> 0, 36 > 0 s.t. bids b < B (8) have an expected
value s(b; B) < e. Furthermore, because ò > some such bids are in the support of B. Therefore
'Some prior work, such as Amegashie 2006). has made progress analytically for specific noise models, hut for the models considered this work.
14

---

Under review as a conference paper at ICLR 2020
there are bids in the Nash with value arbitrarily close to O. Therefore bid b can have s(b; B) O, since this would imply that there were bids that outperformed bids in the support the Nash.
Finally note that bid of O cannot win prize, but also incurs cost, has value of O. Therefore the value to bidders of the Nash must also at least 0.
The proposition tells that the symmetric Nash equilibrium ((b) satisfies:
s(b; B) Σ (BC) = ==1
This equation is polynomial of order n - in B()) for each value of b. Polynomials of up to order 4 can be solved analytically, therefore the CDF of the symmetric Nash can be expressed analytically for auctions with 5 or fewer bidders.
For any number of bidders, can easily express the inverse-CDF using equation Tas follows:
w (B(b)) b=
b = Σ wrG,(B(b) j=1
B
(²) = (,
3=1
This allows sampling directly from the Nash equilibrium bid distribution in the noiseless setting, but relies on the fact that the probability of winning with a bid of depends on B only through the value of B(b), which is not true noisy auction.
A final result of interest to this work concerns settings for which the optimal design in the noiseless auction is to award the entire prize budget the first place prize:
Theorem: If the principal's utility function u : R4 r> R is strictly increasing, continuously dif- ferentiable and its inverse u -1 is log-concave, then Elu (max 6;)] under the symmetric Nash equi- librium is maximized by allocating the entire prize budget to the first prize.
proof can be found in Vojnović (2015).
Note however, that the inverse of log[a(æ b)) is nowhere log-concave for b > 0. Therefore the utility function considered in this work not covered by this theorem. Indeed, we often found superior designs that awarded prizes to multiple places.
15


Reviews:
[{"review_id": "r1g0zMbRKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary\n\nThe authors employ a multi-agent learning approach for learning how to set payoffs optimally for crowdsourcing contests\nand auctions. Optimality means e.g. incentive alignment (the principal problem) between the principal (e.g. the organizer) and participants (e.g. bidders), assuming e.g. that participants can be strategic about their behavior. In this work the principal uses ReLU-log utility.\n\nFirst, the authors use fictitious play and multi-agent RL to train agents on a distribution of payoffs. Then, a neural net is fitted to the samples (payyoffs, expected principal utility), and finally iteratively attempts to improve the payoffs using mirror ascent within the convex set of admissable payoffs.\n\nThe authors compare the payoffs with theoretically known solutions and in situations where the optimal solution is not known.\n\n3, 4-agent all-pay auction (Nash eq known).\nSame as above, but with noise added to bids (Nash eq not known).\nThe authors analyze in some detail how the principal's utility and bidder ranking behave as the participants' bids change.\n\n1. Decision (accept or reject) with one or two key reasons for this choice.\n\nReject. Although the high-level approach is interesting (use learning to design auctions for cases where no theoretical solution is known), the actual experimental results and methodological improvement over e.g. Dutting 2017 are weak. The authors only consider 3, 4-agent auctions. There are no other learned baselines (e.g., constrained optimization without neural nets) that the authors could consider.\n\n3. Supporting arguments\n\nSee above.\n\n4. Additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\nM-EMA and M-EMD: ascent and descent? in Algo 1, 2?\n\n\n--- \nI've read the rebuttal, but still lean towards reject. The scope/analysis of the experiments (e.g. auction type), still seems limited, even though both agents and mechanism are adaptive.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkegGTPZcS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After reading the rebuttal, I increased my score to weak accept, since it addressed my concern.\n----------------------------------------\nSummary\nThis paper presents a general machine learning method for contest / auction problems. The underlying idea is to collect data pairs (i.e., [design, utility]), fit a model to the data, and then optimize over all the designs to figure out the best one. The authors mainly applied their method on an auction design problem, and finished a few experiments. However, due to lack of novelty, I lean to vote for rejecting this paper.\nWeaknesses\n- My major concern of this paper is the lack of novelty. As the authors stated in the introduction, the contribution of this paper is a machine learning method for designing crowdsourcing contest. However, as the authors demonstrated in Figure 1, the main idea of this approach is: collect the data, fit a model, and finally optimize the objective, which is a pretty common approach. I do not see something special or interesting in this approach.\n- The authors spend a lot of space discussing how to deal with the auction, but I do not see their relationship with the machine learning algorithm, or how can these tricks be generalizable to other scenarios. It seems all these discussions are specific to this auction scenario, and there is almost no relationship between these tricks with the machine learning algorithm. However, if these tricks can be applied to other scenarios, these discussions will make sense.\nPossible Improvements\nI am very happy to increase my score if the authors could demonstrate why their approach in Figure 1 is novel, and how their discussion about the auction can be generalized to other scenarios.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJg_1FfTtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a scenario of bidding contest where the goal os to find optimal allocation w = (w_1, w_2, ..., w_n) of the total prize that maximizes the principal’s expected utility function. The problem is formulated into an optimization task within the simplex where the total allocation is fixed at w. Then the authors proposed simulation methods to solve this problem and use experiments to demonstrate the method's advantages. The paper is sound an clear, but it's not clear to me which part is novel and which part is from existing work, hence I doubt the contribution level of this paper. Furthermore, I'm not quite sure whether the topic fits ICLR as it's more related to game theoretic society and not related to representation learning.\n\nThanks for the response from the authors. I have read it carefully, especially regarding the novelty part. My review remains unchanged based on the author feedback.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper demonstrates a framework for optimizing designs in auction/contest problems. The approach relies on considering a multi-agent learning process and then simulating it. 

To a large degree there is agreement among reviewers that this approach is sensible and sound, however lacks substantial novelty. The authors provided a rebuttal which clarified the aspects that they consider novel, however the reviewers remained mostly unconvinced. Furthermore, it would help if the improvement over past approaches is demonstrated in a more convincing way, for example with increased scope experiments that also involve richer analysis.

Decision: Reject