# Designing Auctions when Algorithms Learn to Bid:
The Critical Role of Payment Rules

Pranjal Rawat
PhD Student in Economics
Georgetown University
Washington DC, USA
<EMAIL_ADDRESS>

###### Abstract

This paper examines the impact of different payment rules on efficiency when
algorithms learn to bid. We use a fully randomized experiment of 427 trials,
where Q-learning bidders participate in up to 250,000 auctions for a commonly
valued item. The findings reveal that the first price auction, where winners
pay the winning bid, is susceptible to coordinated bid suppression, with
winning bids averaging roughly 20% below the true values. In contrast, the
second price auction, where winners pay the second highest bid, aligns winning
bids with actual values, reduces the volatility during learning and speeds up
convergence. Regression analysis, incorporating design elements such as
payment rules, number of participants, algorithmic factors including the
discount and learning rate, asynchronous/synchronous updating, feedback, and
exploration strategies, discovers the critical role of payment rules on
efficiency. Furthermore, machine learning estimators find that payment rules
matter even more with few bidders, high discount factors, asynchronous
learning, and coarse bid spaces. This paper underscores the importance of
auction design in algorithmic bidding. It suggests that computerized auctions
like Google AdSense, which rely on the first price auction, can mitigate the
risk of algorithmic collusion by adopting the second price auction.

_K_ eywords Market Design $\cdot$ Reinforcement Learning

##  1 Introduction

The first price auction, where winners pay the winning bid, is susceptible to
coordinated bid suppression when Q-learning algorithms learn to bid in
repeated auctions. On the other hand, the second price auction, where winners
pay the second highest bid, aligns winning bids with actual values, reduces
the volatility during learning and speeds up convergence. Payment rules play a
critical role in determining auction efficiency under algorithmic bidding,
surpassing the importance of other design elements such as the number of
participants, bid space granularity, information disclosures, as well as
algorithmic factors, including the discount and learning rate,
asynchronous/synchronous updating, feedback, and exploration strategies.

These findings are particularly relevant as intelligent algorithms rapidly
assume control of real-time computerized auctions across various domains,
including online marketplaces for pre-owned items, display advertising,
sponsored search, stock trading, electricity, transportation, and public
procurement. These developments raise concerns about the efficiency of
auctions traditionally designed by and for humans under algorithmic bidding.
To mitigate the risk of bid suppression, exchanges like Google AdSense, which
currently rely on the first price auction, could consider adopting the second
price auction.

Among the various artificial intelligence algorithms available for study, I
specifically concentrate on reinforcement learning. This field has witnessed
remarkable advancements in robotics, self-driving cars, and strategic games
like Chess and Go. The focus centers on the vanilla Q-learning algorithm,
widely recognized as the foundation for many notable breakthroughs. By
investigating the impact of payment rules on auction efficiency within the
context of Q-learning, this study aims to provide valuable insights into the
design of platforms for algorithmic bidding.

However, when algorithms learn using complex strategies, expressing the motion
of the dynamical system in mathematical terms becomes impossible. This issue
motivates the use of an experimental methodology that enables clean
identification and efficient estimation of the effect of auction design on
efficiency while adjusting and controlling for the influence of other factors.
Thus, this study consists of 427 trials, with Q-learning bidders participating
in up to 250,000 auctions for a commonly valued item in each trial.

Auction efficiency lies in ensuring that the item sells to the individual who
values it the most and at their private valuation. In this study, auction
efficiency is defined as the average winning bid to true value ratio in the
last 1000 auctions of each trial. Notably, transitioning from a second to a
first-price auction leads to a reduction in bids, approximately amounting to
20% of the item’s actual value. Moreover, machine learning estimators reveal
that this reduction is magnified in auctions characterized by fewer bidders,
higher discount factors and learning rates, asynchronous learning dynamics,
and coarser bid spaces.

Previous studies have considered the effect of various factors on algorithmic
collusion. Waltman and Kamyak (2008), Dopologov (2021), and Abada et al.
(2022) have shown how specific exploration strategies can lead to collusive
outcomes. Asker et al. (2021) highlighted asynchronous vs synchronous
learning. Calvano (2020) studied retaliatory strategies in simultaneous
pricing games. Klein (2021) focused on sequential pricing games and the
granularity of action spaces. Hansen et al. (2021) investigated collusion
arising from misspecified prediction and correlated price experimentation.
Hettich (2021), Han (2022), and Zhang (2021) delved into deep reinforcement
learning and compared different sampling strategies. Ittoo and Petit (2017)
discussed the gap between experimental research and practice.

While Banchio and Skrzypacz (2022) were the first to study auction design in a
similar setting and found that the first price auction can lead to collusive
outcomes while the second price auction does not, their approach did not
control for other design elements and algorithmic factors that could also lead
to bid suppression. Additionally, they did not explore how other factors
interact with payment rules in determining auction efficiency. This paper
addresses this limitation via a randomized experiment that not only controls
for other covariates but also estimates how the effect of payment rules varies
with them.

To summarize, in this paper, I conduct a controlled random experiment with
Q-learning bidders and find that second-price auctions improve efficiency,
reduce volatility and speed up learning. These findings can help improve
auction design for algorithms. In the following sections, I survey the
literature, describe the methodology, present the results and conclude.

##  2 Literature

There are a few kinds of literature that are relevant. First, a theoretical
literature on auctions that assumes rational actors. Second, experimental
literature replaces rational actors with humans or algorithms. Third,
empirical evidence on algorithmic adoption and collusion. Fourth, legal
literature on possible gaps.

The first thread is theoretical literature on auctions (Milgrom and Weber
1982, Krishna 2009). The second price auction is superior to the first price
auction when bidders only have a noisy signal about the actual value of the
item. The first price auction suffers from the risk of the winner’s curse,
which leads to conservative bidding, and this reduces auction revenues. These
results can break down in repeated games, and the Folk Theorem says that if
bidders are patient enough, any average winning bid can be supported by a
suitable and credible threat of punishment e.g., tit-for-tat or grim trigger.
Tacit collusion in repeated auctions will take the form of symmetrically
suppressed bids or asymmetric bid rotation.

Oligopoly theory also offers some insight into the determinants of tacit
collusion in repeated games. Ivaldi et al. (2002) show that in repeated games,
the degree of tacit collusion rises with a higher discount rate, fewer market
participants, symmetric conditions, higher entry barriers, a high frequency of
interaction, greater transparency, and data availability. The last three
factors are magnified with algorithms and are often cited as the reason for
concern for algorithmic collusion.

The second thread consists of experiments. The experimental evidence with
humans shows a distinctive departure from theory (Kagel and Levin 2011). Bids
are generally above Nash prediction in both the first and second price
auctions. Experiments with noisy signals show a significant presence of the
winner’s curse, which even experienced bidders are unable to avoid (Levin et
al., 1996). Sequential auctions of identical items often show declining prices
(Keser et al., 1996, Neugebauer et al., 2007).

Experiments with algorithms have highlighted different mechanisms through
which tacit collusion can occur. Waltman and Kamyak (2008), Dopologov (2021)
and Abada et al (2022) show how certain exploration strategies can lead to
collusive outcomes. Asker et al (2021) highlight asynchronous vs synchronous
learning. Calvano (2020) studies retaliatory strategies in simultaneous
pricing games. Klein (2021) studies sequential pricing games and granularity
of action spaces. Hansen et al (2021) study collusion arising from
misspecified prediction and correlated price experimentation. Hettich (2021),
Han (2022) and Zhang (2021) study deep reinforcement learning and compare
different sampling strategies.

A few papers look at algorithms learning to bid in auctions. Bandyopadhyay et
al. (2008), study reverse auctions with reinforcement learning and find that
in simple cases mixed strategy equilibrium can be attained. Tellidou et
al.,(2007) study electricity markets and find that tacit collusion is easy to
sustain even under competitive conditions. Banchio and Skrzypacz (2022) study
auction design with Q-learning bots and found that the first price auction can
lead to collusive outcomes while the second price auction does not. Criticisms
of simulation-based studies are that settings are too stylized, using
competitive rather than monopolistic benchmarks is unrealistic, and algorithms
tested are too unrealistic (Kühn & Tadelis 2017, Schwalbe 2018).

The third thread looks at the pervasive adoption of algorithms and actual
evidence for algorithmic collusion. Chen et al. (2016) studied 1,641 best-
seller products on Amazon and detected that about 543 had adopted some form of
algorithmic pricing. A 2017 OECD report titled “Algorithms and Collusion"
found that “Two-thirds of them [ecommerce firms] use automatic software
programs that adjust their own prices based on the observed prices of
competitors". A 2023 eMarketer report shows that algorithms are dominating
bidding in display and sponsored search auctions across the globe. Brogaard et
al., (2014) find that algorithms have come to dominate trading in the double
auction markets.

These developments have led to limited evidence of algorithmic collusion.
Assad et al. (2020) study the adoption of algorithmic pricing in German
gasoline markets. They find that adoption increases margins by 9% in
competitive markets and upto 28% in duopolies. Brown and Mackay (2021) five
largest online retailers in over-the-counter allergy medications. The use of
automated software to change prices quickly leads to prices that are 10
percent higher than otherwise. Musoloff (2022) studied data from Amazon
Marketplace and found that adopting algorithmic pricing reduces prices on
average but leads to “resetting" price cycles where participants regularly
increase prices at night to cajole the others into following suit. We also see
a few legal cases already. 111The 2015 Topkins (US) and 2016 GB Posters (UK)
cases brought to light price fixing via pricing algorithms on Amazon. In 2018,
after the insolvency of Air Berlin, Lufthansa abused its temporary monopoly
power by raising prices roughly by 25% through pricing algorithms. In 2021,
Google was fined 2.42 billion Euro for using algorithms to exclusively place
its own Shopping services on Google search while demoting rival providers.
Similarily, Amazon is currently defending a claim that its algorithms put its
own products over rivals on its lucrative ‘Featured Offer’ placement. There
have also been hub-and-spoke conspiracies. In 2016, e-Turas the Lithuanian
travel website, was charged for imposing caps on discount rates proposed by
travel agencies. In 2018, Accenture was accused of using its software Partneo
to coordinate price increases on auto parts, dramatically increasing revenue
for major carmakers.

The fourth thread looks at possible gaps in regulation. Tacit algorithmic
collusion is currently not prohibited by law. In the United States, anti-
collusion laws require evidence of “actionable agreement" over mere
interdependent behavior. A report at the OECD Competition Committee
222“Algorithms and Collusion” - A note submitted by the United States to the
OECD Competition Committee. reiterates that in the U.S. firms have the freedom
to decide their own prices and implement any kind of pricing technology; only
decisions taken with an understanding with other competitors is prosecutable.
Similarily, European Law (Article 101 TFEU) outlaws three types of collusion:
agreements, decisions, and concerted practices. Again, this does not include
tacit collusion.

There are many ways in which algorithms can participate in collusion (Ezrachi
and Maurice 2017). First, they can act as messengers and conduits for human
collusion and cartels e.g., price fixing on Amazon via algorithms. Here, an
agreement to collude is established clearly. Second, they can be part of a
hub-and-spoke conspiracy where the developers of the hub use a single
algorithm to set prices for many spokes e.g., Uber’s algorithm setting taxi
rates. Agreement to collude is harder to establish in such vertical
agreements, and so evidence for intent must be found. Third, humans can
unilaterally set up to behave in predictable ways, and some of them lead to
coordination with others e.g. gasoline pricing algorithms in Brown and MacKay
(2021). Here agreement is nonexistent, and intent to collude must be
established. Lastly, algorithms are given the objective to maximize profits
and, through sophisticated learning and experimentation, begin to collude with
other similar algorithms e.g. Deep Q-learning. In this case, neither agreement
nor intent can be established, and the case would be difficult to prosecute.
This paper addresses this last case.

To summarize, second-price auctions are theoretically superior to first-price
auctions, but in repeated auctions this may not be true. There has been
widespread adoption of algorithms but only a few examples of algorithmic
collusion. Simulations highlight many mechanisms through which it is possible.
And there is a gap in regulation with regards tacit collusion.

##  3 Methodology

###  3.1 Markov Decision Processes

The problem of a single agent is described by a Markov Decision Processes
(MDP). A MDP is ($S$, $P$, $R$, $\gamma$, $B$). $S$ is the set of possible
states. $B$ is a set of actions. $R$ is reward matrix that measures
$R(b_{i},b_{-i},s)$ or the reward obtained at state $s$, taking action $b_{i}$
(and others’ playing $b_{-i}$). $P$ is transition matrix that measures
$P(s^{\prime}|s,a)$ or the probability of moving to state $s^{\prime}$ when
taking action $b$ at state $s$. And $\gamma$ is the discount factor. Agents
follow policies to move through the environment. A policy $\pi$ is a strategy
of choosing actions given states such that $\pi_{b,s}=Prob(B_{t}=b|S_{t}=s)$.
Let $\pi(b_{t})$ be the action taken at time $t$ according to policy $\pi$.
Then the discounted reward from starting out at state $s_{0}$ is going to be
$\sum_{t=0}^{\infty}{\gamma^{t}r(s_{t},\pi(s_{t}))}$, the return from
following policy $\pi$ onwards from state $s_{0}$ in one history. The quality
of state-action pair is defined as,

$Q^{\pi}(s,a)=r(s,a)+\mathbb{E}\left[\sum_{t=1}^{\infty}{\gamma^{t}r(s_{t},\pi(s_{t}))\mid\pi}\right]$

$Q^{\pi}(s_{0},a)$ allows us to study the impact of choosing different actions
$a$ at $s_{0}$ even while continuing to following $\pi$ after the first step.
There can be an infinite number of possible policies but only one can be the
best (as long as the maximum expected return is not infinite). The $Q$
function of the optimal policy satisfies the Bellman Equation:

$Q(s,a)=r(s,a)+\gamma E[\max_{a^{\prime}}Q(s^{\prime},a^{\prime})]$

such that $s^{\prime}\sim p(\cdot\mid s,a)$. Each bidder maintains an estimate
of the $Q$ that they refine over time and use to choose bids. Once the
learning process ends, each bidder reaches the optimal $Q$ (given all others’
$Q$-tables). Converged $Q$-tables may be suboptimal for the auctioneer but
they are always optimal for the bidder given what competitors are doing. In
this way there is no communication between bidders and they learn
independently.

###  3.2 Experimental Setup

The experiment consists of 427 trials. Each trial $i$ consists of $N_{i}$
bidders competing in upto 250,000 auctions in a sequential manner. Each bidder
can bid $b\in B=\\{b_{0}<b_{1}<....b_{K}\\}$, such that $b_{K}=1$ and
$b_{0}=0$, for a commodity that is commonly-valued to be $1$. $K$ represents
the granularity of the bid space $B$. Each bidder $j$ has a valuation
$Q_{j}(b,s)$ for each possible bid which represents the “long term" reward for
playing bid $b$ in state $s$ (see Appendix). Here $s$ represents the state or
feedback that each bidder recieves from the environment. For instance, it can
represent the winning bid in the previous auction. It can also be omitted
completely.

The $Q$-table is initial with random values for all bidders and for a while
bidders play randomly. Depending on the auction rules and the bids played
$(b_{1},b_{2}...b_{N})$, each bidder $i$ gets reward
$r_{i}(b_{1},b_{2}...b_{N})$ from that game. For instance, under the first
price auction the winner $w$ gets $1-b_{w}$, while all others get $0$. This is
because everyone values the commodity at 1. In case of a ties, there is a
random winner. As bidders gain experience from playing in auctions they update
their valuations $Q_{j}(b,s)$. This can be done in a piece-meal asynchronous
fashion (only at particular bid $b$) or for all bids $b\in B$. The latter is
only possible when the winning bid and number of winners is known.

Once bidders gain sufficient experience they begin to cease playing randomly.
They begin to choose bids $b$ in state $s$ that have higher valuation
$Q_{i}(b,s)$. Towards the end the bidders play
$b_{j}(s)=argmax_{b}Q_{j}(b,s)$. At the end of the trial data is collected
regarding the initial conditions (auction design, learning rate, etc.) and the
outcomes. This process is repeated for each trial.

###  3.3 Q-learning

One of the most popular algorithms to approximate the $Q$ function is the
Q-learning algorithm which can be operationalised in an “online" setup.

  * •

Guess $Q_{0}(s,a)$

  * •

at $t$, do:

    * –

observe $s_{t}$

    * –

take action $a_{t}$ from suitable exploratory strategy

    * –

collect reward $r_{t}$

    * –

observe transition $s_{t+1}$

    * –

update $Q$ at point $(s_{t},a_{t})$:

$Q_{t+1}(s_{t},a_{t})=(1-\alpha)Q_{t}(s_{t},a_{t})+\alpha(r_{t}+\gamma
max_{a^{\prime}}Q_{t}(s_{t+1},a^{\prime}))$

Exploratory strategies are methods to take actions given states. In this study
I use two popular exploratory strategies, that pick $a_{t}$ given $s_{t}$.
This first is $\epsilon$-Greedy that plays randomly with $1-\epsilon$ and
greedily with $\epsilon$. The other is Boltzmann exploration which uses the
$Q$-tables to play randomly:
$P(a_{t}|s_{t})=e^{Q_{t}(s_{t},a_{t}/\beta}/\sum_{a^{\prime}}e^{Q_{t}(s_{t},a^{\prime})/\beta}$.
I set $\epsilon=1$ and $\beta=1$ and have them decay at an exponential rate of
0.9999 or 0.99999 until they reach 0.01. This ensures that for active
exploration happens for roughly half of the total 250000 games possible in
each trial. This ensures sufficient exploration and sufficient exploitation. I
set the initial valuation as $Q_{0}\sim UNIF(0,1)$.

Q-learning has some important guarentees. Watkins and Dayan (1992) show that
with sufficient exploration and a stationary environment a single Q-learner
will get to the optimal $Q$ with probability 1. This guarentee does not hold
in multi-agent settings, but practical experience has shown that Q-learning
can solve very complex control problems to a sufficient degree.

###  3.4 Data

Table 1 describes the outcome variables. $bid2val$ is the average winning bid
to true value ratio in the last 1000 auctions, and measures “efficiency".
$vol$ measures the standard deviation of winning bids accross the learning
process. This measures overall volatility during learning. $episodes$ measures
number of games to convergence. Table 2 describes the covariates or initial
conditions for each trial. The treatment in this case is the auction $design$.
It is 1 when I use a first price auction and 0 when I use a second price
auction. Other covariates include: the number of bidders $N$, the speed of
learning $alpha$ in Q-learning, the discount factor $gamma$ which governs how
much current reward bidders are willing to trade off for future rewards, an
indicator for the nature of updating mechanism $asynchronous$ which is 1 when
bidders only update the valuation of bid $b$, the granularity of the bid space
$num\\_actions$, whether prior winning bids are revealed or not $feedback$ and
an indicator for the nature of exploration $egreedy$. The variable $decay$ is
the decay rate for the exploration hyperparameters $\epsilon$ or $\beta$.

Table 1: Outcome Variables Outcome | Range | Description
---|---|---
bid2val | [0,1] | Average winning bid to true value ratio in the last 1000 auctions.
vol | (0,$\infty$) | Standard deviation of winning bids accross the learning process.
episodes | [0, 250000] | Number of games to convergence.
Table 2: Initial Conditions/Covariates Covariate | Values | Description
---|---|---
N | [2,4] | Number of bidders in the auction.
alpha | [0.01,0.1] | Learning rate in learning step.
gamma | [0.0,0.95] | Discount Factor or Patience.
egreedy | [0,1] | 1 if $\epsilon$-greedy, 0 if Boltzmann exploratio.n
design | [0,1] | 0 if second-price, 1 if first-price format.
asynchronous | [0,1] | 0 if synchronous, 1 if asynchronous.
feedback | [0,1] | 1 if previous winning bid is permitted as state variable, else 0.
num_actions | [6,11] | Size of bid space.
decay | [0.9999,0.99995] | Decay rate of exploration parameters $\epsilon$ or $\beta$.

To keep the experiment simple, I permitted only two arms for every covariate
(see Table 2). A single trial consists of randomly drawing a set of initial
conditions, initializing algorithms that begin from scratch and play upto
250,000 auctions sequentially. Upon convergence, which is defined as either
breaching the 250,000 limit or winning bids stabilising, the outcome variables
are measured. I conduct 427 such trials to construct a dataset of
$(bid2val_{i},vol_{i},episodes_{i},design_{i},N_{i},alpha_{i},gamma_{i},asynchronous_{i},num\\_actions_{i},feedback_{i},egreedy_{i},decay_{i})^{427}_{i=1}$
where $i$ indexes the trial. I use this dataset for inference.

###  3.5 Potential Outcomes

I follow Athey and Imbens (2016) in this section. The data I have is
independent and idential observations of $(Y_{i},W_{i},X_{i})^{M}_{i=1}$ where
$Y_{i}$ is the observed outcome, $W_{i}$ is the binary vector of treatment
assignment, $X_{i}$ is a vector of covariates and $M$ is the sample size. Let
$X,W,Y$ be data matrices of corresponding variables. $M_{t}$ and $M_{c}$ are
the size of the treatment and control group respectively. $Y_{i}(0),Y_{i}(1)$
are potential outcomes for any unit $i$ which tell us what would be observed
if treatment was assigned to unit $i$ or not. The treatment effect is defined
on potential outcomes i.e. $\tau_{i}=Y_{i}(1)-Y_{i}(0)$ is the individual
treatment effect and $\tau=E[Y_{i}(1)-Y_{i}(0)]$ is the average treatment
effect.

I make the following assumptions for inference. First, is the Stable Unit
Treatment Value Assumption (SUTVA) which implies that the potential outcomes
of any unit are not affected by other units’ interventions, and interventions
always take one of two values. Secondly, any unit could receive either
intervention with a positive probability. Thirdly, because of the explicit
randomization of the treatment, I are assured of unconfoundedness as well.
Fourthly, since I randomized all other covariates as well I can also estimate
the effect of other possible interventions. Fifthly, I will also impose that
interventions affect potential outcomes in a linear fashion i.e. they “add
up". Machine learning estimators help relax this last assumption.

###  3.6 Regression Analysis

With a suitable definition of $\epsilon_{i}$, the observed outcome can be
written in terms of the treatment as a regression model:

$Y_{i}=\alpha+\tau W_{i}+\epsilon_{i}$

Due to randomization, the zero conditional mean assumption is satisfied,
$E[\epsilon_{i}|W_{i}]=0$. This implies that $\tau$ can be consistently via
the OLS estimator.
$\hat{\tau}_{OLS}=(W^{\prime}W)^{-1}W^{\prime}Y\rightarrow\tau$. Note that in
general homoskedasticity is violated and heteroskedasticity-robust standard
errors are used. Incorporating additional pre-treatment covariates into
regression analysis can improve precision, correct for faulty randomization,
permit interactions and help generalize the results. However, an assumption of
linearity has to be made. Then the model is,

$Y_{i}=\alpha+\tau W_{i}+\beta X_{i}+\epsilon_{i}$

Due to randomization, $E[\epsilon_{i}|W_{i},X_{i}]=0$. This enables consistent
estimation of $\tau$ through OLS. Machine learning methods (Chernozhukhov
2016, Athey and Wagner 2017) further relax the assumptions of linearity and
permit estimation with high dimensional covariates. Consider the partially
linear model,

$Y_{i}=\Theta(X_{i})W_{i}+g(X_{i})+\epsilon_{i}$

with $E[\epsilon_{i}|W_{i},X_{i}]=0$. Here $\Theta(X_{i})$ captures the
heterogenous treatment effect, permitting each unit to have a different causal
impact of $W_{i}$, depending on $X_{i}$. $g$ is a nonlinear function and
$X_{i}$ can now be high dimensional.

##  4 Results

###  4.1 Examples

Figure 1 and 2 presents two separate trials with identical initial conditions
except for the payment rule. The averaging is done over 1000 games. The other
conditions were
$N=4,alpha=0.1,gamma=0.99,egreedy=0,asynchronous=1,feedback=1,num\\_actions=6,decay=0.9999$.
In the first price auction we saw a slow convergence to the second highest bid
possible. In the second price auction we saw a quick convergence to true
value. Once that was attained bidders became indifferent between bids.

Figure 1: Avg Bids in the First Price Auction Figure 2: Avg Bids in the Second
Price Auction

###  4.2 Data Description

Table 3 presents the summary statistics. On average, auction efficiency a the
end of the trial was below 1 and near 0.9. There were cases where auction
efficiency was as low as 0.11. On average it took 170,000 rounds to reach
convergence, but in many iterations, the upper bound of 250000 was breached.
This implies that sometimes winning bids did not stabilize even after a long
period.

Table 3: Summary Statistics Variable | N | Mean | St. Dev. | Min | Max
---|---|---|---|---|---
bid2val | 427 | 0.900 | 0.136 | 0.113 | 1.000
episodes | 427 | 168,617.800 | 86,586.950 | 50,000 | 249,999
vol | 427 | 0.020 | 0.036 | 0.000 | 0.301
N | 427 | 3.073 | 0.999 | 2 | 4
alpha | 427 | 0.054 | 0.045 | 0.010 | 0.100
gamma | 427 | 0.441 | 0.474 | 0.000 | 0.950
egreedy | 427 | 0.494 | 0.501 | 0 | 1
asynchronous | 427 | 0.525 | 0.500 | 0 | 1
design | 427 | 0.511 | 0.500 | 0 | 1
feedback | 427 | 0.513 | 0.500 | 0 | 1
num_actions | 427 | 8.482 | 2.503 | 6 | 11
decay | 427 | 1.000 | 0.00002 | 1.000 | 1.000

Figure 3 presents the boxplot of terminal bid-to-value ratios, volatility over
the learning process and episodes to convergence against the auction design
used. We see that when the second price auction was used (orange boxplots),
regardless of other experimental conditions, auction efficiency was very close
to 1 (but not exactly 1). When the first price auction was used (blue
boxplots) we see that a much broader range of efficiencies that could be
supported. Further, we see that in the first price auction, the volatility
over the learning process was much higher than the second price auction. And
the average episodes to convergence is much lower in the second price auction
and considerably higher in the first price auction. Thus simple mean
comparisions show that the second price auction has (1) greater efficiency,
(2) lower volatility across the learning process and (3) faster convergence.

Figure 3: Boxplot of outcomes vs design.

###  4.3 Regression Analysis

The dataset generated is used to run regression models with three outcomes -
average bid to value ratio in last 1000 games, standard deviation of winning
bids accross the entire learning process and number of episodes until
convergence. In all regressions the covariates remain the same - these are the
trial conditions before the trial was run. With a large sample of trials
narrow confidence intervals can be attained. Since all other covariates were
also randomized their coefficients are also estimates of average treatment
effects.

Table 4: Regression of Bids to Value Ratio in last 1000 games against covariates. | Dependent variable: bid2val
---|---
| (1) | (2)
Intercept | 0.998∗∗∗ | 135.948
N |  | 0.025∗∗∗
alpha |  | -0.079
asynchronous |  | -0.031∗∗∗
decay |  | -135.023
design | -0.192∗∗∗ | -0.193∗∗∗
egreedy |  | -0.015∗
feedback |  | 0.009
gamma |  | -0.032∗∗∗
num_actions |  | 0.003
Observations | 427 | 427
$R^{2}$ | 0.503 | 0.572
F Statistic | 430.471∗∗∗ (df = 1.0; 425.0) | 61.915∗∗∗ (df = 9.0; 417.0)
Note: |  ∗p$<$0.1; ∗∗p$<$0.05; ∗∗∗p$<$0.01

Table 4 presents a regression of the bid-to-value ratio i.e. efficiency on the
covariates. The effect of design on efficiency is negative and statistically
significant. Moving from the first price to the second price increases bids-
to-value by roughly 20% of the actual value. Furthermore, comparing the R2
suggests that auction design is the most important factor behind efficiency.
The number of bidders is statistically significant and is positive. Adding one
extra bidder increases the average efficiency by 2.5% percentage points. The
use of asynchronous learning has a small negative but significant effect on
efficiency. Further, the use of higher discount rates also reduces efficiency.
Other factors like learning rate levels, whether feedback was used, and
exploratory strategies do not matter.

Table 5: Regression of volatility across the entire learning process against covariates | Dependent variable:Vol
---|---
| (1) | (2)
Intercept | 0.010∗∗∗ | -139.829∗∗
N |  | -0.010∗∗∗
alpha |  | 0.100∗∗∗
asynchronous |  | 0.001
decay |  | 139.853∗∗
design | 0.020∗∗∗ | 0.021∗∗∗
egreedy |  | -0.007∗∗
feedback |  | 0.008∗∗
gamma |  | 0.008∗∗
num_actions |  | 0.002∗∗∗
Observations | 427 | 427
$R^{2}$ | 0.081 | 0.224
F Statistic | 37.288∗∗∗ (df = 1.0; 425.0) | 13.360∗∗∗ (df = 9.0; 417.0)
Note: |  ∗p$<$0.1; ∗∗p$<$0.05; ∗∗∗p$<$0.01

Table 5 presents a regression of standard deviation of winning bids across the
entire learning process against covariates. Here moving away from the first
price to the second price reduces overall volatility in the learning process.
The impact of design is not overwhelming and other factors can also play a
role. The volatility of the learning process rises with lesser number of
bidders, faster learning rates, faster decay of exploration parameters, moving
from $\epsilon$-greedy to Boltzmann exploration, when algorithms use feedback
about past winning bids, a higher discount rate and more fine bid spaces.
However, there is much more variation in the volatility in the learning
process that is unexplained.

Table 6: Regression of number of episodes until convergence against covariates. | Dependent variable:Episodes
---|---
| (1) | (2)
Intercept | 122248.536∗∗∗ | -855973322.698∗∗∗
N |  | -11287.328∗∗∗
alpha |  | 42714.500
asynchronous |  | -16849.662∗∗
decay |  | 856174164.216∗∗∗
design | 90824.129∗∗∗ | 89211.029∗∗∗
egreedy |  | 6707.839
feedback |  | 4220.911
gamma |  | 822.856
num_actions |  | 2398.109∗
Observations | 427 | 427
$R^{2}$ | 0.276 | 0.370
F Statistic | 161.684∗∗∗ (df = 1.0; 425.0) | 27.170∗∗∗ (df = 9.0; 417.0)
Note: |  ∗p$<$0.1; ∗∗p$<$0.05; ∗∗∗p$<$0.01

Table 6 presents a regression of the number of episodes until convergence
against covariates. Here moving away from the first price to the second price
ensures that convergence happens much later. Thus the second price auction is
also helpful in enabling faster convergence. The impact of design is large and
only a few factors contribute further. The speed of convergence rises with
fewer bidders. As expected, asynchronous learning is also much slower than
synchronous learning and a faster decay of exploration parameters will lead to
faster convergence. Further, increasing the bid space granularity also reduces
the pace of convergence. However, there is quite a bit of variation in the
speed of the learning process that is unexplained.

To summarize, moving from a first price to a second price auction will (1)
ensure efficiency, (2) reduce volatility in the learning process and (3) speed
up convergence. Another equally important factor that affects volatility in
the learning process is the learning rate. Other factors that can also
influence the speed of convergence are the learning rate and rate of decay of
exploration. All in all, payment rules play a critical role in improving
outcomes even after controlling for algorithmic factors.

###  4.4 Interactions

To dig deeper into the determinants of efficiency, the following model was
estimated using double machine learning methods described in Chernozhukhov
(2016),

$Y_{i}=(\beta_{0}+\sum_{j}\beta_{j}X_{ij})W_{i}+g(X_{i})+\epsilon_{i}$

with the assumption $E[\epsilon_{i}|W_{i},X_{i}]=0$. Machine learning methods
to approximate $g$ and partial out its effect on $Y_{i}$ before estimating
$(\beta_{0},\beta_{j})$. The term $(\beta_{0}+\sum_{j}\beta_{j}X_{ij})$ is the
conditional average treatment effect of design on outcomes.

Table 7: Heterogenous Treatment Effect of Design on Efficiency | point_estimate | stderr | zstat | pvalue | ci_lower | ci_upper
---|---|---|---|---|---|---
N | 0.043 | 0.009 | 4.999 | 0.000 | 0.026 | 0.059
alpha | -0.121 | 0.178 | -0.678 | 0.498 | -0.469 | 0.228
gamma | -0.054 | 0.016 | -3.374 | 0.001 | -0.085 | -0.023
egreedy | -0.024 | 0.016 | -1.495 | 0.135 | -0.055 | 0.007
asynchronous | -0.063 | 0.016 | -3.943 | 0.000 | -0.094 | -0.032
feedback | 0.005 | 0.016 | 0.288 | 0.773 | -0.026 | 0.035
num_actions | 0.007 | 0.003 | 2.255 | 0.024 | 0.001 | 0.013
decay | -285.723 | 321.264 | -0.889 | 0.374 | -915.389 | 343.942
cate_intercept | 285.396 | 321.240 | 0.888 | 0.374 | -344.223 | 915.016

Table 7 presents the estimates for $(\beta_{0},\beta_{j})$. The average effect
of design on efficiency is negative (Table 2). So if $\beta_{j}$ is positive,
it implies that an increase in covariate $j$ shrinks the effect of auction
design by bringing it closer to 0. If $\beta_{j}$ is negative, it implies that
an increase in covariate $j$ raises the effect of auction design by taking it
further away from 0. Thus a smaller number of bidders, a larger discount
factor, asynchronous learning, and a smaller number of possible actions, all
make the bid suppression in the first price auction even worse. Thus payment
rules interact with algorithmic factors in determining efficiency.

##  5 Conclusion

Algorithms are increasingly shaping markets, necessitating a deeper
understanding of their behavior. This research focuses on multi-agent
Q-learning in auctions to explore algorithmic behavior in market settings. Our
study provides strong evidence supporting the superiority of the second-price
auction over the first-price auction under algorithmic learning. The second-
price auction demonstrates better efficiency, accelerated learning, and
reduced volatility. These findings are validated through robust experimental
evidence, improving upon previous literature by utilizing a fully randomized
experiment.

Our study incorporates a large number of covariates and considers the
interaction between auction design and other factors, enhancing our
understanding of the nuanced relationship between auction mechanisms and
algorithmic behavior. The implications of our results suggest potential risks
of algorithmic collusion for platforms like Google AdSense, which currently
use the first-price auction. Platforms are recommended to experiment with
alternative auction rules in controlled environments and policymakers are
advised to consider algorithmic factors that can amplify collusion.

In practice, firms often use forecasting models and reinforcement learning to
predict bids and rewards. Future research can adopt this pragmatic approach
and explore alternative algorithms, such as Deep Q-learning. However, it is
important to acknowledge a limitation of our study: the slow nature of vanilla
Q-learning, making it impractical for real-world scenarios. Overcoming this
limitation calls for further exploration of efficient algorithms.
Additionally, investigating auctions with descending or ascending bids
presents an intriguing avenue for future research.

By incorporating these recommendations and addressing the limitations, future
studies can build upon our findings, advancing our understanding of
algorithmic behavior in market auctions. This research contributes to the
development of effective auction mechanisms within algorithmic environments,
benefiting stakeholders across various auction-based platforms and markets.

##  6 References

Abada, Ibrahim, Xavier Lambin, and Nikolay Tchakarov. 2022. ‘Collusion by
Mistake: Does Algorithmic Sophistication Drive Supra-Competitive Profits?’
SSRN Electronic Journal. https://doi.org/10.2139/ssrn.4099361.

Asker, John, Chaim Fershtman, and Ariel Pakes. 2022. ‘Artificial Intelligence,
Algorithm Design, and Pricing’. AEA Papers and Proceedings 112 (May): 452–56.
https://doi.org/10.1257/pandp.20221059.

Assad, Stephanie, Robert Clark, Daniel Ershov, and Lei Xu. 2020. ‘Algorithmic
Pricing and Competition: Empirical Evidence from the German Retail Gasoline
Market’. SSRN Electronic Journal. https://doi.org/10.2139/ssrn.3682021.

Athey, Susan, and Guido Imbens. 2016. ‘The Econometrics of Randomized
Experiments’. arXiv. http://arxiv.org/abs/1607.00698.

Banchio, Martino, and Giacomo Mantegazza. 2022. ‘Adaptive Algorithms and
Collusion via Coupling’. arXiv. http://arxiv.org/abs/2202.05946.

Banchio, Martino, and Andrzej Skrzypacz. 2022. ‘Artificial Intelligence and
Auction Design’. In Proceedings of the 23rd ACM Conference on Economics and
Computation, 30–31. Boulder CO USA: ACM.
https://doi.org/10.1145/3490486.3538244.

Bandyopadhyay, Subhajyoti, Jackie Rees, and John M. Barron. 2008. ‘Reverse
Auctions with Multiple Reinforcement Learning Agents’. Decision Sciences 39
(1): 33–63. https://doi.org/10.1111/j.1540-5915.2008.00181.x.

, Zach Y, and Alexander MacKay. n.d. ‘Competition in Pricing Algorithms’.

Calvano, Emilio, Giacomo Calzolari, Vincenzo Denicolò, and Sergio Pastorello.
2020. ‘Artificial Intelligence, Algorithmic Pricing, and Collusion’. American
Economic Review 110 (10): 3267–97. https://doi.org/10.1257/aer.20190623.

Cavallo, Alberto. 2018. ‘More Amazon Effects: Online Competition and Pricing
Behaviors’. w25138. Cambridge, MA: National Bureau of Economic Research.
https://doi.org/10.3386/w25138.

Chen, Le, Alan Mislove, and Christo Wilson. 2016. ‘An Empirical Analysis of
Algorithmic Pricing on Amazon Marketplace’. In Proceedings of the 25th
International Conference on World Wide Web, 1339–49. Montréal Québec Canada:
International World Wide Web Conferences Steering Committee.
https://doi.org/10.1145/2872427.2883089.

Freedman, David A. 2008a. ‘On Regression Adjustments in Experiments with
Several Treatments’. The Annals of Applied Statistics 2 (1).
https://doi.org/10.1214/07-AOAS143. ———. 2008b. ‘On Regression Adjustments in
Experiments with Several Treatments’. The Annals of Applied Statistics 2 (1).
https://doi.org/10.1214/07-AOAS143.

Klein, Timo. 2021. ‘Autonomous Algorithmic Collusion: Q-learning under
Sequential Pricing’. The RAND Journal of Economics 52 (3): 538–58.
https://doi.org/10.1111/1756-2171.12383.

Leisten, Matthew. n.d. ‘Algorithmic Competition, with Humans’.

Lin, Winston. 2013. ‘Agnostic Notes on Regression Adjustments to Experimental
Data: Reexamining Freedman’s Critique’. The Annals of Applied Statistics 7
(1). https://doi.org/10.1214/12-AOAS583.

Mehra, Salil K. n.d. ‘Antitrust and the Robo-Seller: Competition in the Time
of Algorithms’. MINNESOTA LAW REVIEW.

Noel, Michael D. 2008. ‘Edgeworth Price Cycles and Focal Prices: Computational
Dynamic Markov Equilibria’. Journal of Economics & Management Strategy 17 (2):
345–77. https://doi.org/10.1111/j.1530-9134.2008.00181.x.

Tesauro, Gerald, and Jeffrey O. Kephart. 2002. ‘Pricing in Agent Economies
Using Multi-Agent Q-Learning’. In Game Theory and Decision Theory in Agent-
Based Systems, edited by Simon Parsons, Piotr Gmytrasiewicz, and Michael
Wooldridge, 5:293–313. Multiagent Systems, Artificial Societies, and Simulated
Organizations. Boston, MA: Springer US.
https://doi.org/10.1007/978-1-4615-1107-6-14.

Zhao, Jun, Guang Qiu, Ziyu Guan, Wei Zhao, and Xiaofei He. 2018. ‘Deep
Reinforcement Learning for Sponsored Search Real-Time Bidding’. In Proceedings
of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data
Mining, 1021–30. London United Kingdom: ACM.
https://doi.org/10.1145/3219819.3219918.