\documentclass{llncs}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{algorithmic,algorithm}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{definition}{Definition}[section]
%\newcommand{\qed}{\hfill$\rule{2mm}{3mm}$}
%\newenvironment{proof}{\par{\noindent \bf Proof:}}{\qed \par}

\newcommand{\jenn}[1]{\textbf{JW: #1}}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\R}{\ensuremath{\mathbb R}} % R in blackboard font for the reals.

\newcount\EXTENDED
\newcount\CONTEXT
\EXTENDED = 1 %% Set to 1 for extended version of the paper
\CONTEXT = 1

\sloppy

\title{Maintaining Equilibria During Exploration in Sponsored Search
Auctions}

\author{Jennifer Wortman\inst{1} \and Yevgeniy Vorobeychik\inst{2}
\and \\ Lihong Li\inst{3} \and John Langford\inst{4}}

\institute{
Computer and Information Science, University of Pennsylvania \\
\texttt{wortmanj@seas.upenn.edu}\footnote{This work was done while
J. Wortman, Y. Vorobeychik, and L. Li were at Yahoo$!$ Research, New
York.}
\and
Computer Science \& Engineering, University of Michigan \\
\texttt{yvorobey@umich.edu}\footnotemark[\value{footnote}]
\and
Computer Science, Rutgers University \\
\texttt{lihong@cs.rutgers.edu}\footnotemark[\value{footnote}]
\and
Yahoo$!$ Research \\
\texttt{jl@yahoo-inc.com}
}

\begin{document}

\maketitle

\begin{abstract}
We introduce an exploration scheme aimed at learning advertiser
click-through rates in sponsored search auctions with minimal effect
on advertiser incentives.  The scheme preserves both the current
ranking and pricing policies of the search engine and only introduces
one parameter which controls the rate of exploration.  This parameter
can be set so as to allow enough exploration to learn advertiser
click-through rates over time, but also eliminate incentives for
advertisers to alter their currently submitted bids.  When advertisers
have much more information than the search engine, we show that
although this goal is not achievable, incentives to deviate can be
made arbitrarily small by appropriately setting the exploration rate.
Given that advertisers do not alter their bids, we bound revenue loss
due to exploration.
%When advertisers have much more information than the
%search engine, this goal is not achievable.  Instead, we show that
%incentives to deviate and change bids can be made arbitrarily small by
%appropriately setting the exploration rate.
\end{abstract}

\section{Introduction}

Recent years have seen an explosion of interest in sponsored search
auctions, due in large part to the unique opportunity for targeted
advertising and the resulting billions of dollars in revenue.  Most
sponsored search auctions display a list of advertisements on the
sidebar or other sections of a search engine's results page, ranked by
some function of advertisers' revealed willingness-to-pay for every
click on their ad.  The advertisers in turn pay the search engine for
every click their ad receives.  While several pricing schemes have
been circulated in the literature~\cite{lahaie06}, by far the most
popular is a generalization of second-price auctions, under which each
advertiser pays the lowest bid that is sufficient to ensure that the
ad remain in its current slot.  Typically the number of available
slots for advertisements on the first search page is fixed, and thus
only high ranking advertisements are displayed.

An essential part of both designing sponsored search auction
mechanisms and bidding in them is the knowledge of the probability
that a given ad is clicked each time it is displayed in a particular
slot for a particular search query or keyword.  This probability is
known as the \emph{click-through rate} or \emph{CTR} of the ad.
Knowledge of these click-through rates helps advertisers determine
optimal bidding behavior.
%(e.g., given the current bids of the other advertisers, which
%slot is most profitable and how much should I bid for it).
CTRs can also be an integral part of the ad ranking policy.  For
example, it is common for policies to rank bidders by the product of
their bid and some function of their \emph{relevance}, a
slot-independent measure of CTR.
%(i.e., ad-specific multiplicative contribution to the click-through
%rate at a particular slot).
Throughout the paper, we assume that CTRs do not change over time.
%which is a reasonable approximation to reality if the changes in CTR
%is slow.

Most of the existing literature on sponsored search auctions treats
CTRs as known.  When advertisers first enter the system, however,
their CTRs are not yet known either by the search engine or even by
the advertisers themselves, and can only be estimated over time based
on the observed clicks.  Observations are inherently limited to slots
in which ads appear, and estimates are generally poor for advertisers
with low rank that do not usually appear at all.  Furthermore, without
the assumption of factorable CTRs, little can be said about CTRs of an
ad in slots in which it has not previously appeared (or has appeared
only a small number of times).  Thus there is a need for an
exploration policy that periodically perturbs the current slate of
displayed ads, showing some in alternate slots and occasionally
displaying those ads that are ranked below the last slot.  Ideally,
this exploration policy should not be difficult to incorporate into
the current sponsored search mechanisms.  Additionally, if the
advertisers' bids have reached an equilibrium, the exploration policy
should, when possible, eliminate the incentives for bidders to change
their bids, thereby destabilizing the auction.  Such destabilization
can result in negative user and advertiser experience, as well as
unnecessary loss in revenue to the search engine, and can make
exploration harder to control.

In this paper, we address the problem of learning the click-through
rates for each ad in every slot.  Our primary goal is to maintain an
equilibrium bid configuration if the bidders did indeed play according
to an equilibrium prior to exploration.  When this is not possible, we
provide bounds on the amount that any advertiser could gain by
deviating.  This incentive to deviate can be minimized by reducing
exploration, at the cost of slowing down the process of learning the
CTRs.  Additionally, we bound the revenue loss that the search engine
incurs due to exploration, as compared to maintaining a policy based
on current estimates of CTRs.

A similar problem has been addressed by Pandey and
Olston~\cite{pandey06} and Gonen and Pavlov~\cite{gonen07}.  The
former work addresses the learning problem without considering
advertiser incentives.  The latter addresses both.  Our model differs
from existing ones in three primary ways:
%Three primary
%distinctions exist between our model and existing models for
%exploration:
\begin{enumerate}
\item We avoid imposing a particular ranking policy or introducing a
new pricing scheme so that changes to existing systems are minimal.
\item The data gathered by our approach can be incorporated into
general learning algorithms using sample selection debiasing
techniques.\cite{heckman79}
\item We avoid the standard but unrealistic assumption that
click-through rates can be factored into advertiser- and slot-specific
components.
\end{enumerate}

\section{Notation and Definitions}
\label{sec:notation}

We consider an auction for a particular keyword in which there are $N$
advertisers (alternately called bidders or players) placing
bids.\footnote{Since our analysis can be repeated for each keyword,
the restriction to a single keyword is without loss of generality.
Indeed, the analysis can even be generalized to incorporate arbitrary
context information, as long as the number of contexts is finite and
advertisers may submit separate bids for each.~\cite{even-dar07}} We
assume that the search engine has $K$ slots with non-negligible CTRs.
Throughout the discussion on incentives, we assume that the CTRs
depend only on the ad being displayed and the slot in which it is
shown.  Thus, we use $c_i^s$ to denote the true CTR of player $i$ in
slot $s$.  We assume that for each player $i$, $c_i^s > c_i^t$
whenever $1 \leq s < t \leq K$.  For convenience, we define $c_i^s = 0$ for
$s > K$
%and $c_i^s = c_i^1$ for
and $s < 1$.  In most of our analysis we deal explicitly with
estimated click-through rates; the search engine estimates are denoted
by $\hat{c}_i^s$, whereas the advertiser $i$'s estimates are denoted
by $\tilde{c}_i^s$.  Finally, we let $v_i$ denote the value of a click
to player $i$.

For now we assume that throughout the exploration process, advertisers
are ranked according to their bid $b_i$ multiplied by a weight $w_i$
which is an increasing function of their estimated relevance scores
for the particular keyword.  Setting this weight equal to relevance
recovers the standard rank-by-revenue model.  Without loss of
generality, assume that advertisers are indexed in the order in which
they are ranked when playing equilibrium, i.e. advertiser $i$ is in
slot $i$ in the ranking.
%Finally, we assume that for all $i,j$ with $w_iv_i \geq w_jv_j$, $c_i^{s-1}/c_i^s \geq c_j^{s-1}/c_j^s$ for all $s\geq 2$.
%An advertiser $i>K$ is called a `losing bidder.   -- Moving this later
Each advertiser pays a price per click equal to the lowest bid that
maintains his current position; thus the price paid by bidder $i$ in
rank $s$ is $p_i^s = w_{s+1}b_{s+1}/w_i$.
%LL: Should we mention how $p_i^K$ is defined?  It's based on the
%reserve price, or is simply zero. -- JW: I added something to this
% effect into section 3.

The relevance score of an advertiser, which we denote by $e_i,$ can be
thought of as an average CTR over all slots for the given keyword. We
might choose to define this relevance as $\sum_{s=1}^{K}c_i^s$ or
alternately as $\sum_{s=1}^{K}c_i^s / c_s$ where $c_s$ is the
``average'' CTR that any ad might expect to receive on slot
$s$.\footnote{Observe that when $c_i^s$ is factorable into the product
$e_i c_s$, both of these relevance scores are proportional to $e_i$.}
%The precise choice of how to define relevance could potentially
%effect how quickly we can get an accurate estimate of advertiser
%relevance from data.}
We can fix the weights for each advertiser prior to (each phase of)
exploration and reveal the new estimates of CTRs at the end of the
exploration period only, allowing greater control of exploration.

We assume that prior to exploration the advertisers converge to a
symmetric Nash equilibrium, a variant of Nash equilibrium introduced
simultaneously by Varian~\cite{varian07} and Edelman et
al.\cite{edelman05}.  We slightly alter the standard definition to
take into account CTR estimates as follows.
\begin{definition}
A \emph{symmetric Nash equilibrium (SNE)} is an ordering and a set of bids such
that for every player $i$ and for every slot $s$,
\(
\tilde{c}_i^i\left(v_i - p_i^i\right)
\geq  \tilde{c}_i^s\left(v_i - p_i^s\right),
\)
where $\tilde{c}_i^s$ denotes advertiser $i$'s CTR estimate at slot $s$.
\end{definition}
Existence of at least one symmetric Nash Equilibrium was proved in a
slightly different setting than ours by B\"{o}rgers et
al.~\cite{borgers07}. Their proof applies essentially without change
to our setting.% (see Appendix~\ref{appendix:sne_proof}).
%We also assume that the SNE played by the advertisers orders them by $w_iv_i$.
%This is true of all SNE in the special case of factorable CTRs, and is true of at least one SNE under a relatively strong condition in the general case~\cite{borgers07}.
%\footnote{The only necessarily modification is to specify the price by
%player $i$ as $\frac{w_{i+1}b_{i+1}}{w_i}$.}

%At some points, we will assume the existence of a \emph{reserve price}
%which is the minimum amount that any bidder must pay to receive a
%slot.
%Without loss of generality, we assume that all advertisers have
%bids above the reserve price of slot $K$ or that the reserve price is
%zero. Otherwise, we simply will not consider players for whom this
%assumption does not hold.

\section{An Algorithm for Exploration}
\label{sec:kswappingalg}

We begin by describing a simple algorithm for learning click-through
rates.  Below (in Section~\ref{sec:swapping_incentives}) we show that
we can set parameters of this algorithm in such a way as to minimize
or entirely eliminate incentives for advertisers to deviate from a
pre-exploration SNE.  Our key condition will be that throughout the
entire run of the algorithm the prices which the advertisers pay are
fixed to their pre-exploration equilibrium prices.

The algorithm, which we call \texttt{k-swap}
(Algorithm~\ref{alg:kswap}), starts by ranking ads by the product of bid
and weight as usual, and repeatedly chooses pairs of ads to swap in
order to explore.  In particular, each time the given keyword receives
an \emph{impression} (i.e. each time a query is made on the keyword),
a swapping distance $k \in \{1,\cdots,K\}$ is chosen from some
distribution (e.g.  uniformly at random).  The algorithm calculates or
looks up a swapping probability for each pair of slots $s$ and $s+k$
that are a distance $k$ apart. (The method for choosing these
probabilities will be discussed in
Section~\ref{sec:swapping_incentives}.)  Finally, the algorithm uses
this set of swapping probabilities to decide which (if any) pair of
ads to swap.
%The procedure is then repeated.

We must be careful about how pairs of ads are chosen to be swapped so
we can avoid swapping the same ad more than once on a single query.
Let $S_i$ denote the event that the ads in slots $i$ and $i+k$ are
swapped and let $r_i^k = \Pr(S_i)$ be the probability that this event
occurs. We have
\[
\Pr(S_i) = \Pr(S_i | S_{i-k}) \Pr(S_{i-k}) +
\Pr(S_i | \neg S_{i-k}) \Pr(\neg S_{i-k}) .
\]
To avoid conflicting swaps, we can set $\Pr(S_i | S_{i-k}) = 0$, which
implies that $\Pr(S_i | \neg S_{i-k}) = \Pr(S_i) / \Pr(\neg S_{i-k}) =
r_i^k / (1 - r_{i-k}^k)$, which is no greater than one as long as we
enforce that $r_{i-1}^k + r_i^k \leq 1$.
\begin{algorithm}[t!]
\begin{algorithmic}
\STATE Calculate all swapping probabilities $r_i^k$
\FORALL{queries on the given keyword}
\STATE Randomly select a $k \in \{1,\cdots,K\}$
\FOR{$i = 1$ to $\min\{k, K-k+1\}$}
\STATE Set $S_i \leftarrow 1$ with probability $r_i^k$, $S_i \leftarrow 0$ otherwise
\ENDFOR
\FOR[Note that this statement is null if $2k > K$]{$i = k+1$ to $K-k+1$}
\IF{$S_{i-k} = 1$}
\STATE Set $S_i \leftarrow 0$
\ELSE
\STATE Set $S_i \leftarrow 1$ with probability $r_i^k / (1 - r_{i-k}^k)$,
$S_i \leftarrow 0$ otherwise
\ENDIF
\ENDFOR
\FOR{$i = 1$ to $K-k$}  % : $S_i = 1$}
%\IF{$S_i = 1$}
\STATE Swap the ads in slots $i$ and $i+k$ if $S_i = 1$
%\ENDIF
\ENDFOR
\IF{$S_{K-k+1} = 1$}
\STATE Choose an $i \in \{K+1,\cdots,N\}$ to display in slot $K-k+1$ %according to the distribution $q_i$
%\STATE Move ad $i$ into slot $K-k+1$
\ENDIF
\ENDFOR
\end{algorithmic}
\caption{The \texttt{k-swap} algorithm.}
\label{alg:kswap}
\end{algorithm}

For the sake of this algorithm, all ads with rank $K+1, \cdots, N$ can
be thought of as sharing slot $K+1$.  Thus whenever an ad in slot $s
\leq K$ is chosen to swap with slot $K+1$, any ad with rank $K+1,
\cdots, N$ could be displayed in slot $s$.  Due to lack of space, we
do not discuss how the algorithm might decide which losing ad to
display, but one could imagine giving preference to ads that have not
often been displayed in the past.

%% YV: The comments in the next two sentences are moved into the text.
%The algorithm is described in Algorithm~\ref{alg:kswap}.  A method for
%choosing swapping probabilities $r_i^k$ is discussed in
%Section~\ref{sec:swapping_incentives}.  Prices are set via the
%generalized second price auction mechanism as described in
%Section~\ref{sec:notation} and remain unchanged for all advertisers
%throughout exploration.
%When an ad in slot $s \leq
%K$ is swapped out of its current slot, the advertiser pays the price
%per click he would have paid if the ad had not been swapped; when the
%ad of a losing bidder (i.e. one with rank $s > K$) is swapped into a
%slot, the price per click can be set to a small reserve price or
%simply zero.  Thus, the immediate effect of the exploration scheme on
%advertisers is only the change in effective CTR.  Ranking and pricing
%policies need not be altered.

%In Section~\ref{sec:swapping_incentives}, we show a set of conditions
%on the swapping probabilities that guarantee that if advertisers are
%at equilibrium before exploration is introduced, they will have no
%incentives to alter their bids when exploration is added using this
%algorithm.  In Section~\ref{sec:learningbounds}, we give bounds on the
%error of our estimates of CTR learned using the algorithm to explore.

%As our first order of business, we present a simple algorithm for
%learning click-through rates, which is based on repeatedly swapping
%ads that are $k$ slots apart.  The first step of this algorithm
%involves randomly selecting $k$ between 1 and $K$.  In the next step
%it determines the probabilities that all pairs will be swapped each
%time a keyword is entered.  When a keyword is entered (i.e., for each
%impression), the algorithm probabilistically decides which (if any)
%pairs of ads to swap, subject to the constraint that ads are exactly
%$k$ slots apart.  The procedure may then be repeated from the
%beginning, or after some fixed number of impressions.  Whenever an ad
%is swapped out of its equilibrium slot, the advertiser nevertheless
%pays the price he was paying prior to the swap.  Thus, the immediate
%effect on advertisers is only the change in effective click-through
%rate, and the ranking and pricing policies need not be altered.

%As long as every pair of ads $k$ slots apart will be swapped with non-zero probability for each fixed $k$, our algorithm ensures that all the click-through-rates will eventually be learned, albeit potentially very slowly.
%In certain special cases, however, we can learn all the click-through-rates by only swapping adjacent ads, thereby considerably speeding up convergence.
%One such special case is when $\frac{c_i^s}{c_i^{s+1}}$ is constant for all $i$ and all $s=1,\ldots,K-1$, in which case it is sufficient to learn $c_i^i$ and $c_i^{i+1}$ for each advertiser $i$.

%If we assume that advertisers submitted symmetric Nash equilibrium bids prior to exploration~\cite{varian07}, our goal is to restrict exploration in such a way as to eliminate or at least minimize the incentives for bidders to deviate from equilibrium that exploration would now introduce.
%This is the subject of the following section.
%By achieving this goal, we will later be able to bound the loss in revenue incurred due purely to exploration.

\section{Maintaining Equilibrium During Pairwise Swapping}
\label{sec:swapping_incentives}

In this section, we consider the effect on advertiser incentives of
implementing an exploration policy that occasionally chooses pairs of
ads that are $k$ slots apart to swap or moves an undisplayed ad into
slot $K-k+1$ for some \emph{fixed} value of $k$.  By ensuring that
advertisers do not have incentives to deviate from equilibrium bids
for any fixed $k$, we ensure that the advertisers do not deviate
throughout the entire run of \texttt{k-swap}.
%Algorithm~\ref{alg:kswap}.
%incentives are not altered under such an exploration policy for all
%$k$, we can ensure that advertiser incentives are not altered when the
%exploration algorithm described in Section~\ref{sec:kswappingalg} is
%used.

We assume that the search engine bases the weights $w_i$ on the CTR
estimates $\hat{c}_i^s$,
%Furthermore, we assume that these weights stay fixed
%throughout each exploration period and are updated only when a period
%of exploration is completed.
and fix the prices paid by the advertisers through the entire run of
\texttt{k-swap}. The updated CTR estimates obtained during exploration
are only reported to advertisers after the algorithm completes.  In
practice, the algorithm may need to be run in multiple phases,
interleaving exploration with updates of CTR estimates, and allowing
sufficient time for advertisers to reach a new equilibrium after each
phase.

Our assumptions raise a conceptual question: if the advertisers care
about the \emph{real} CTRs, how can we maintain incentives given only
estimates?  We posit that often advertisers do not know the CTRs any
better than the search engine and formulate their own optimization
problem (at least approximately) in terms of the estimates provided by
the search engine; that is, we assume that $\tilde{c}_i^s =
\hat{c}_i^s \ \forall i, s$.
We consider the case in which
advertisers have additional information about their CTRs
%and provide bounds on their
%incentives to deviate as a result of exploration in
in Section~\ref{sec:realCTRsknown}.

For the analysis that follows, we assume that the search engine knows
(or can obtain good estimates of) each advertiser's value per
click.
%\footnote{Thus, we are not considering the problem of incentives
%to bid in a manner that disguises true valuation. We presume that the
%system has been in place for some time and valuations have already
%been revealed, before an exploration strategy is made public.}
If we assume that a SNE is played prior to exploration, we can derive
bounds on advertiser values~\cite{varian07} and base our estimates on
these bounds.  In practice, this assumption will not be necessary; we
do not actually advocate setting the swapping probabilities separately
for each individual auction, but rather fixing probabilities in such a
way that the guarantees will hold for most typical auctions.

Since all analysis in this section is for a fixed value of $k$, we
drop the superscript and use $r_i$ in place of $r_i^k$ to denote be
the probability that ads $i$ and $i+k$ are swapped.
% for $i \leq K - k$.
These probabilities can be represented as multiples of $r_1$,
i.e. $r_i = \alpha_i r_1$.  Then, if $\alpha_i$ are set exogenously
(for example, $\alpha_i = 1$ for all $1\leq i\leq K$), \texttt{k-swap}
has only one tunable parameter, $r_1$, for a fixed value of $k$.  For convenience of
notation, we define $\alpha_i = 0$ for all $i < 1$ and $i > K - k +
1$.  In order to allow exploration of CTRs of all bidders, we let
$r_{K-k+1}$ designate the total probability that \emph{any} losing
bidder is swapped into slot $K-k+1$.  Let $q_s$ denote the
probability that a losing bidder with rank $K+1 \le s \le N$ is
displayed \emph{conditional} on \emph{some} losing ad being
displayed.\footnote{Thus, the probability that a particular losing
bidder $s$ gets selected is $q_s r_{K-k+1}$.}
%Since $q_s$ is a conditional probability distribution,
We have that $\sum_{s=K+1}^N q_s = 1$.  Finally, define
$q_{max}=\max_{K+1 \leq  s \leq N} q_s$.

%To ease notation, we
%say that $r_i = 0$ for all $i < 1$ and $i < K -k + 1$.  (The
%probability $r_{K-k+1}$ will be defined slightly differently below.)
%Note that in any phase of the algorithm, we will only swap
%advertisements which are $k$ apart for a fixed value of $k$.
%any that occupy slots closer than that will not be swapped.
%For example, when $k=1$, only adjacent ads may be swapped.
%Thus, for example, if $k = K$, only slots 1 and $K+1$ will be swapped
%with each other, while other ads will not be explored.
%We can represent each probability $r_i$ in terms of $r_1$, i.e. $r_{i}
%= r_1 \alpha_i$ for some values $\alpha_i > 0$.

%We define
%a probability distribution $\{q_s\}_{K+1 \le s \le N}$ (so $s$
%corresponds to some losing bidder) such that $\sum_{s=K+1}^N q_s = 1$.
%Thus, the probability that a particular losing bidder $s$ will be
%selected is $r_{K-k+1} q_s$.  Define $q_{max}=\max_s q_s$.
%For now we leave the precise details of choosing the distribution
%$\{q_s\}$ open.  One might imagine selecting this distribution in such
%a way, for example, that an ad is explored more often when the search
%engine's current estimate of its click-through rate is poor.  In other
%words, low-ranking ads that have been observed fewer times will be
%displayed more often than low-ranking ads with click-through rates
%that are known to be small.

Once we add exploration, the \emph{effective} estimate of CTR for
advertiser $i$ in slot $s$ is no longer $\hat{c}_i^s$.  Rather, now
with some probability $r_{s-k}$ the ad in slot $s$ is moved to slot
$s-k$, and with some probability $r_{s}$ the ad is moved to slot
$s+k$.  Then the new effective estimate of CTR of player $i$ for rank
$s$ is \(\hat{c}_i^{'s} = (1 - r_{s-k} - r_{s}) \hat{c}_{i}^{s} +
r_{s-k} \hat{c}_{i}^{s-k} + r_{s} \hat{c}_{i}^{s+k}.\)\footnote{Recall
that $r_s = 0$ and $\hat{c}_i^s = 0$ for $s < 1$ and $s > K-k+1$. We can
replace CTR with effective CTR because the prices paid by all
advertisers remain fixed for the duration of exploration.}
%\begin{eqnarray*}
%c_{i}^{'s} &=& (1 - r_{s-k} - r_{s}) c_{i}^{s} + r_{s-k} c_{i}^{s-k} +
%r_{s} c_{i}^{s+k}
%\\
%&=& (1 - \alpha_{s-k} r_1 - \alpha_{s} r_1) c_{i}^{s}
%+ \alpha_{s-k} r_1 c_{i}^{s-k}
%+ \alpha_{s} r_1 c_{i}^{s+k} .
%\end{eqnarray*}

Let \(D_{i,s} =\alpha_s(\hat{c}_i^s-\hat{c}_i^{s+k}) -
\alpha_{s-k}(\hat{c}_i^{s-k}-\hat{c}_i^{s}).\) Observe that
$r_1D_{i,s}$ is the marginal CTR loss of advertiser $i$ in slot $s$
when exploration is allowed.  We now define the quantities $J_{i,j}$
and $Z_i$ which are used in Theorem~\ref{thm:adjacentads}:
\begin{eqnarray}
J_{i,j} &=& (v_i - p_i^i)D_{i,i} - (v_i - p_i^j)D_{i,j}
%J_{i,j} &=& (v_i-p_i^i)
%[\alpha_i(\hat{c}_i^i-\hat{c}_i^{i+k})
%- \alpha_{i-k}(\hat{c}_i^{i-k}-\hat{c}_i^{i})]
%\nonumber \\
%& & - (v_i-p_i^j)
%[{\alpha}_j(\hat{c}_i^j-\hat{c}_i^{j+k})
%-\alpha_{j-k}(\hat{c}_i^{j-k}-\hat{c}_i^{j})]
\label{eqn:Jdef} \\
Z_i &=& (v_i - p_i^i)D_{i,i} + \alpha_{K-k+1} q_{max} \hat{c}_i^{K-k+1} v_i.
%Z_i &=& \left(v_i - p_i^i\right)
%\left(\alpha_i(\hat{c}_i^i - \hat{c}_i^{i+k}) - \alpha_{i-k}(\hat{c}_i^{i-k} - \hat{c}_i^i)
%\right) + \alpha_{K-k+1} q_{max} \hat{c}_i^{K-k+1} v_i
\label{eqn:Zdef}
\end{eqnarray}
To get some intuition about what these mean, note that $r_1J_{i,j}$ is
the difference between the marginal loss in expected payoff due to
exploration that the advertiser $i$ receives in slot $j$ and the
marginal loss in expected payoff due to exploration in slot $i$.
Similarly, $r_1Z_i$ is the difference between the marginal loss in
payoff due to exploration that the advertiser $i$ receives by
switching to rank above $K+1$ (and thereby not occupying any slot) and
the marginal loss due to exploration in slot $i$.

The following result gives the conditions under which exploration does
not incent advertisers to change their bids and characterizes the
settings in which this is not possible.  The proof of this theorem and
others can be found in the appendix.
% of the extended version of this
%paper.\footnote{The extended version will soon be available on the authors'
%websites.}
%The following theorem summarizes a set of sufficient conditions to
%eliminate incentives for advertisers to deviate from their symmetric Nash equilibrium bids when exploration by pairwise swapping is added.
%The theorem will likely appear cryptic at
%first glance; intuition for each of the conditions is provided below.
\begin{theorem}
Assume that each advertiser $i \in \{1,\cdots,K\}$ strictly prefers
his current slot to all others in equilibrium, i.e. the condition
\((v_i-p_i^i)\hat{c}_i^i > (v_i-p_i^j)\hat{c}_i^j\) holds for all $1
\leq i,j \leq K, i\neq j$ whenever $J_{i,j} > 0$ and $v_i-p_i^i > 0 \
\forall i$ whenever $Z_i > 0$.
%\begin{equation}
%(v_i-p_i^i)\hat{c}_i^i
%> (v_i-p_i^j)\hat{c}_i^j,
%\label{eqn:strongpref}
%\end{equation}
Then for generic valuations and relevances there exists an $r_1 > 0$
such that no advertiser has incentive to deviate from the
pre-exploration SNE bids once exploration is added.  In particular,
any $r_1$ satisfying the following set of conditions is sufficient:
\begin{eqnarray*}
r_1 \leq \min \Bigg\{ & &
\min_{2\leq i \leq K}\frac{1}{\alpha_i + \alpha_{i-k}} ,
\qquad
\min_{1 \le i \le K; Z_i>0}
\frac{1}{Z_i} (v_i - p_i^i) \hat{c}_i^i , \\
& & \min_{1 \le i,j \le K; i\neq j; J_{i,j}>0}
\frac{1}{J_{i,j}}\left((v_i-p_i^i)\hat{c}_i^i
-(v_i- p_i^j)\hat{c}_i^j\right) \ \Bigg\}.
\end{eqnarray*}
%Furthermore, for any $i, j$ such that $J_{i,j} \leq 0$, it need not be
%the case that Equation~\ref{eqn:strongpref} hold.
\label{thm:adjacentads}
\end{theorem}
%The proof, which can be found in Appendix~\ref{appendix:adjacentads},
%is broken into three cases.  First it shows that if the conditions in
%the theorem statement hold, advertisers $1,\cdots,K$ have no incentive
%to alter their bids in order to switch to other ranks within
%$1,\cdots,K$.  Next it shows that these advertisers have no incentives
%alter their bids to move to slots lower than $K$.  Finally it shows
%that advertisers ranked below slot $K$ before exploration have no
%incentive to deviate.

%This theorem leads to natural questions about how high these swapping
%probabilities can be in practice.
To get some intuition about how the theorem can be applied and about
the magnitude of $r_1$, consider the following example.
\begin{example}
Suppose that there are 3 advertisers bidding on 2 slots. Let
$\hat{c}_i^j = \hat{c}_j$ for all players $i \in \{1,2,3\}$ and slots
$j\in\{1,2\}$ where $\hat{c}_1=1$ and $\hat{c}_2=0.5$. Let $v_1=v_2=3$, and
$v_3=1$.  Suppose that prior to exploration each advertiser bids his
value per click and pays the next highest bid.  One can easily verify
that this configuration constitutes a SNE in which player 1 gets slot
1, player 2 gets slot 2, and player 3 gets no slot, and that in this
equilibrium, player 1 is indifferent between slots 1 and 2.

Let us fix $\alpha_2 = 3/2$.
%, which constrains $r_1$ to be at most $2/3$.
Now we can determine the setting of $r_1$ that allows us to swap
neighboring ads ($k=1$) without introducing incentives to deviate
during exploration.  Applying the first constraint, we find the
condition that $r_1 \leq 1/(1 + 3/2) = 2/5$ must hold.  By the second
constraint, since $Z_1 = 11/4$, we must have $r_1 \leq 4/11$, and
since $Z_2 = 7/4$, we must have $r_1 \leq 2/7$.  With our setting of
$\alpha_2$, $J_{1,2} = 0$ and $J_{2,1} = -1/4 < 0$.  Consequently, the
third constraint on $r_1$ has no effect.  Combining the effects of
these constraints, we see that we can set the swapping probabilities
as high as $r_1 = 2/7$ and $r_2 = 3/7$ without giving any of the
advertisers incentive to deviate during exploration.

Suppose we want to increase $r_1$ to $2/7 + \epsilon$ and thereby
learn a little bit faster.  Consider the incentives of the second
bidder to switch to rank 3 (i.e., receive no slot).  The utility from
being ranked third is $3/7 + 3\epsilon/2 > 3/7$, while the utility
from remaining in slot two is $3/7 - \epsilon/4 < 3/7$.  Consequently,
for any $\epsilon>0$ (and, thus, for any $r_1 > 2/7$) the second
bidder wants to deviate from his equilibrium bid.

%Now consider making $\alpha_2 = 3/2 + \epsilon$. When $\epsilon$ is
%small, $J_{1,2} < 0$ and $J_{2,1} < 0$.  $Z_1$ remains unchanged,
%while $Z_2$ becomes $7/4 + 3\epsilon/2$ and thus $r_1 \leq
%\frac{1}{7/2 + 3\epsilon/2} < 2/7$.  Thus, increasing $r_2$ slightly
%requires decreasing $r_1$.

A similar analysis of constraints and incentives shows that we cannot
increase $\alpha_2$ without decreasing $r_1$ or altering advertiser
incentives.  Similarly, any attempt to decrease $\alpha_2$ can
destabilize the equilibrium.

%Finally, consider making $\alpha_2 = 3/2 - \epsilon$.  While for small
%$\epsilon$ $J_{2,1}$ remains negative, not so with $J_{1,2}$, which
%now equals $\epsilon$.  Now, since in equilibrium player 1 was exactly
%indifferent between slots 1 and 2, we cannot explore and maintain the
%same equilibrium in this case.
\end{example}

As the example suggests, the bounds in Theorem~\ref{thm:adjacentads}
are close to tight.  In fact, the bounds can be made tight simply by
replacing $q_{max}$ with the conditional probability with which ad $i$
would be selected if it were not in one of the top $K$ ranks.

Note that we would not expect a search engine to calculate a distinct
set of swapping probabilities using Theorem~\ref{thm:adjacentads} for
each individual auction in practice.  Indeed it may not be possible
for the search engine to estimate advertiser values accurately in all
cases.
%and the search engine may not want to spend the time
%calculating probabilities the fly even if values are known.
We instead advocate using the theorem to find a single fixed set of
swapping probabilities such that advertisers will not wish to deviate
when \texttt{k-swap} is run for \emph{most} or \emph{all typical}
auctions.

%% add motivation for fixing alpha a priori (one parameter exploration, very fast, since closed-form); in extended version we describe how to formulate and solve the problem more generally, but we would have to use numerical tools; we believe that the constraint will rarely be a problem and one can pick something simple for alpha_i (like all 1's)

%Theorem~\ref{thm:adjacentads} suggests a way to explore without
%affecting advertiser incentives, and characterizes the settings under
%which this is not possible.  In practice, we suspect that by setting
%$\alpha_i$ in a straightforward way (e.g., $\alpha_i = 1$ for all $i$)
%we will usually be able to find $r_1 > 0$ that satisfies the
%conditions of Theorem~\ref{thm:adjacentads}.


\iffalse{
\ifnum\EXTENDED=1
\section{Maintaining Equilibrium During Exploration: General Approach}

We are interested in introducing exploration into the ad display
protocol.  In other words, we want to create a protocol that
occasionally swaps the order in which ads appear in order to allow us
to learn more accurate estimates of advertiser CTR. We begin by
considering a general setting in which two ads in any pair of
positions might be swapped for exploration.  For ease of analysis, we
want it to be the case that the SNE bids does not change when this
exploration is introduced.

Let $R \in \mathbb{R}^{N \times N}$ be a symmetric, stochastic
matrix\footnote{A matrix is stochastic if its entries are nonnegative
and each row sums to $1$.}.  Each matrix entry $r_{i,j}$ represents
the probability that the ad that would be assigned to slot $i$
according to the ranking by the product of weight and bid actually
appears in slot $j$ during exploration.  In other words,
$r_{i,j}=r_{j,i}$ is the probability that the ads in slot $i$ and slot
$j$ are swapped, while $r_{i,i}$ is the probability that the ad in
slot $i$ is not swapped with another ad and thus actually appears
in slot $i$.  If $R$ is the identity matrix, then there is no
exploration at all.  If $R$ has a bandwidth of $1$ (that is, for every
row $i$, only $r_{i,i-1}$, $r_{i,i}$, and $r_{i,i+1}$ can be nonzero),
then only adjacent ads may be swapped.

When a click occurs on an ad that has been swapped, the advertiser is
charged the same payment he would have been charged if the ads had not
been swapped.  In other words, the advertiser in the $i$th position
when there is no swapping is always charged $b_{i+1} w_{i+1} / w_{i}$
when he receives a click, regardless of which slot the ad actually
appears in when the click occurs.

Because advertiser prices do not change when ads are explored, we can
view the effects of this ad swapping as a simple alteration of
slot-specific CTR.  After exploration is added the new CTR for ad $i$
ranked in position $j$ is:
\[
c_i^{'j} = \sum_{k=1}^N r_{j,k}c_i^k = \sum_{k=1}^N r_{k,j}c_i^k.
\]

In order to guarantee that there is no incentive for the advertisers
to deviate from the original SNE once exploration is introduced, it
must be the case that for every $i$ and $j$, the advertiser currently
ranked in position $i$ prefers not to switch to rank $j$.  More
precisely, we need it to be the case that for all $i$, for all $j <
i$,
\[
\sum_{k=1}^{N} r_{i,k}c_i^k\left(v_i- \frac{w_{i+1}b_{i+1}}{w_i}\right)
\geq \sum_{k=1}^{N} r_{j,k}c_i^k\left(v_i- \frac{w_j b_j}{w_i}\right),
\]
and for all $j$ such that $i \leq j \leq N$,
\begin{equation}
\sum_{k=1}^{N} r_{i,k}c_i^k\left(v_i- \frac{w_{i+1}b_{i+1}}{w_i}\right)
\geq \sum_{k=1}^{N} r_{j,k}c_i^k\left(v_i- \frac{w_{j+1} b_{j+1}}{w_i}\right).
\label{eqn:general-constraint}
\end{equation}

To simplify analysis, we enforce the stronger requirement that
Equation~\ref{eqn:general-constraint} hold for \emph{all} pairs $i$
and $j$.  This is equivalent to requiring that the bids satisfy a
symmetric Nash equilibrium under exploration.

%\begin{eqnarray*}
%\sum_{k=1}^N r_{ik}c_i^k\left(v_i-p_i^i\right) &\ge& \sum_{k=1}^N
%r_{jk}c_i^k(v_i-p_i^j),
%\end{eqnarray*}
%where
%\begin{eqnarray*}
%p_i^j &=& \Big\{\begin{array}{ll} \frac{w_{j+1}b_{j+1}}{w_i}, &
%\mbox{if $j \le K$} \\ p_\mathrm{reserved} & \mbox{otherwise}
%\end{array},
%\end{eqnarray*}
%and $p_\mathrm{reserved}$ is the reserved price.  For simplicity,
%let $p_\mathrm{reserved}=0$.  Since $c_i^k=0$ when $k>K$, we may
%simplify the inequality a little bit:
%\begin{eqnarray}
%\sum_{k=1}^K r_{ik}c_i^k\left(v_i-p_i^i\right) &\ge& \sum_{k=1}^K
%r_{jk}c_i^k(v_i-p_i^j). \label{eqn:general-constraint}
%\end{eqnarray}

%\footnote{Is this assumption reasonable?  One of the reasons we
%need exploration is to collect data to get better estimates of
%CTRs $c_i^j$ (and maybe utilities $v_i$).  To do exploration,
%however, we assume we know these values.}
If the values $v_i$ and $c_i^j$ are known, then these conditions form
a set of linear inequality constraints on the swapping probabilities
$r_{i,j}$.  Finding values of these probabilities that do not change
the SNE then only involves finding a feasible solution to a set of
linear inequalities, which can be done efficiently in polynomial time.
In the worse case, there are $O(N^2)$ such inequalities, but many of
them can be redundant in many cases. For example, if $r_{s,t} <
r_{s,K+1}$ for any $t > K+1$ and $1 \le s \le K$, then we can only
consider $O(NK)$ inequalities.  Further improvements are possible.
%\footnote{However, it is a practical concern whether a polynomial-time
%solution is good enough since we will have to rank the bids \emph{in
%real time}.}
Furthermore, if there are multiple solutions that do not change the
SNE, we may choose the one that is optimal in some sense.  For
example, we could choose exploration probabilities to minimize the
loss of revenue, learn the most about advertiser CTRs, etc.  In this
optimization case, the problem becomes a linear program.  (See the
open problems in Section~\ref{sec:open}.)
\fi
\fi

\section{Learning Bounds}
\label{sec:learningbounds}

In this section, we bound the error of our estimated click-through
rates for each advertiser in each slot after $Q$ queries have been
made on the given keyword.
%Because we have made no assumptions about
%the form of advertiser CTRs, observations of ad $i$ in
%slot $s$ give us no direct information about the CTR of ad $i$ in
%alternate slots, or about the CTR of alternate ads in slot $s$.  Thus
%we must bound the error of our estimate for each advertiser in each
%slot separately, using only the relevant observations.
Let $n_{i,s}$ denote the number of times we have observed advertiser
$i$ in slot $s$, and let $z_{i,s,j}$ be the indicator random variable
which is $1$ if ad $i$ is clicked the $j$th time it appears in slot
$s$, and $0$ otherwise.
%Let $p_k$ be the probability of choosing a swapping distance of $k$ at
%each time step, so $p_k = 1/K$ if swapping probabilities are chosen
%uniformly at random.
Finally, let $\pi_{i,s}^k$ be the probability that ad $i$ is displayed
at slot $s$ when we are swapping ads that are $k$ slots apart, as
discussed in Section~\ref{sec:swapping_incentives}.
%If we let $r_i$ and $\alpha_i$ denote the values of $r_i$ and $\alpha_i$ when the
%swapping distance is $k$, then we can see that
%\begin{equation*}
%\pi_{i,s}^k =
%\begin{cases}
%1 - r_1 \alpha_i - r_1 \alpha_{i-k}, & \text{if $s=i$}
%\\
%r_1 \alpha_i, & \text{if $s=i+k$}
%\\
%r_1 \alpha_s, & \text{if $s=i-k$ and $i \leq K$}
%\\
%r_1 \alpha_s q_i, & \text{if $s=K-k+1$ and $i > K$}
%\\
%0, & \text{otherwise}
%\end{cases}
%\end{equation*}

To simplify the presentation of results, we assume that the swapping
distance $k$ is drawn uniformly at random from $\{1,\cdots,K\}$ for
each query, but the extension to arbitrary distributions is
straight-forward.
%Note that as long as $r_i^k > 0$
%whenever $i + k \leq K+1$, every ad is swapped into every slot with
%some positive probability, which implies that the probability that any
%ad $i$ appears in slot $s$ is positive, i.e., $(1/K) \sum_{k=1}^K
%\pi_{i,s}^k > 0$.
%The proof of the following theorem follows easily
%from repeated applications of Hoeffding's inequality and the union
%bound.

%Thus we need an algorithm for exploration that places every ad in
%every slot with some positive probability.  We might also want to
%allow an initial learning phase in which the ordering of ads is chosen
%uniformly at random until we have enough information to form initial
%estimates of CTRs, or to assume that we already have some initial
%estimates when we start.

%The proof (Appendix~\ref{appendix:learningbounds_gen}) of the following theorem follows easily from repeated
%applications of Hoeffding's inequality and the union bound.
\begin{theorem}
Suppose the \texttt{k-swap} algorithm has been run for $Q$ queries
with a fixed set of broadcasted CTR estimates.  Let $\hat{c}_i^s$ be
our \emph{new} estimate of CTR, defined as \( \hat{c}_i^s =
(1/n_{i,s}) \sum_{j=1}^{n_{i,s}} z_{i,s,j} \) for all advertisers $i$
and slots $s$ such that $n_{i,s} \geq 1$.  Then for any $\delta \in
(0,1)$, with probability $1-\delta$, the following holds for all $i$
and $s$ for which we have made at least one observation:
\[
|\hat{c}_i^s - c_i^s| \leq
\sqrt{\frac{\ln(2KN/\delta)}
{2 n_{i,s}}} .
\]
Furthermore, with probability $1-\delta$, for all $i$ and $s$, we have
that $n_{i,s} \geq \max\{(Q/K) \sum_{k=1}^K \pi_{i,s}^k - \sqrt{Q
\ln(2KN/\delta) / 2}, 0\}$.
\label{thm:learningbounds_gen}
\end{theorem}

%This theorem implies that
Thus as the number of queries $Q$ grows, our estimates of the CTR
vectors for each advertiser grow arbitrarily close to the true CTR
vectors.

\section{Bounds on the Incentives of ``Omniscient'' Advertisers}
\label{sec:realCTRsknown}

%Suppose that we are following the policy of swapping advertisers in
%slots that are $k$ apart.
If players have much more information about the actual click-through
rates than the search engine, it is unlikely that we can entirely
eliminate incentives of advertisers to change their bids during
exploration.  However, if we can bound the error in our estimates of
the click-through rates, we can also bound how much advertisers can
gain by deviating.  When incentives to deviate are small, we may
reasonably expect advertisers to maintain their equilibrium bids,
since computing the new optimal bids may be costly.  The search engine
may further dull benefits from deviation by
%paying advertisers to keep their bids fixed.
charging a small fee to advertisers when they change their bids.

From this point on, we assume that the error in search engine
estimates of the CTRs is uniformly bounded by $\epsilon$; that is, \(
|c_i^s - \hat{c}_i^s| \leq \epsilon \) for every $i$ and $s$.
% with high probability.

Assume that $r_1^k$ were set such that the bidders have no
incentive to change their bids if they use $\hat{c}_i^s$ as their CTR
estimates.  We now establish how much incentive they have to deviate
if they know their \emph{actual} CTR $c_i^s$, that is, $\tilde{c}_i^s
= c_i^s$; we call such advertisers ``omniscient''.
\begin{theorem}
The most that any omniscient advertiser can gain by deviating in
expectation per impression
% JW: moving this def earlier
%\footnote{Each instance a search keyword is queried
%is called an \emph{impression}.}
is
\(
\max_{1\leq i \leq K}2\epsilon(v_i - p_i^K).
%\frac{w_{K+1}b_{K+1}}{w_i}
\)
\label{thm:dev_bound1}
\end{theorem}
This bound has the intuitive property that as our CTR estimates
improve, the bound on incentives to deviate from equilibrium bids
improves as well.\footnote{Note that given $r_1^k$ the actual payoffs
to deviation are not affected as we learn unless we also publicize
the learned information.}  It is also intuitive, however, that
incentives diminish if the exploration probabilities fall.  This
motivates the following alternate bound which shows that we can make
the incentives to deviate arbitrarily small even for omniscient
advertisers by appropriately setting $r_1^k$.

%, where we again assume the worst case for our purposes: all players know the \emph{actual} click-through rates.
%\footnote{Hence, in the equations below we assume that the symmetric equilibrium is with respect to the actual click-through rates.  If players do not know the actual CTRs, $c_i^j$ have the meaning of CTRs according to the players' estimates and the uniform bound would need to be interpreted as the difference between their estimates and ours.}
\begin{theorem}
The most that any omniscient advertiser can gain by deviating in
expectation per impression is
\[
%\max_{1\leq k \leq K}\max_{1\leq i \leq K}\max_{1\leq j \leq K} r_1^k(\alpha_i(\hat{c}_i^i - \hat{c}_i^{i+k}) + \alpha_{j-k}(\hat{c}_i^{j-k} - \hat{c}_i^{j}) + 2\epsilon(\alpha_{i} + \alpha_{j-k}))(v_i - p_i^K).%\frac{w_{K+1}b_{K+1}}{w_i}
\max_{1 \leq i,j,k \leq K} \left\{ r_1^k \left(\alpha_i(\hat{c}_i^i - \hat{c}_i^{i+k}) + \alpha_{j-k}(\hat{c}_i^{j-k} - \hat{c}_i^{j}) + 2\epsilon(\alpha_{i} + \alpha_{j-k})\right) \left(v_i - p_i^K\right) \right\}.
\]
\label{thm:dev_bound2}
\end{theorem}
%Proofs of both bounds appear in the appendix.

\section{Bounds on Revenue Loss Due to Exploration}

%Suppose as in the previous section that we are following the policy of
%swapping advertisers in slots that are $k$ apart.
We now assume that the advertisers play according to the symmetric
Nash equilibrium that was played prior to exploration and, as in the
previous section, assume that the errors of the search engine's
estimates of CTRs are uniformly bounded by $\epsilon$ with high
probability.  Given these assumptions, the theorem that follows bounds
the loss in revenue due entirely to exploration.
\begin{theorem}
The maximum expected loss to the search engine revenue per impression due to exploration is bounded by
\[
\max_{1\leq k \leq K} \left\{r_1^k\sum_{i=2}^Kp_i^i\left(\alpha_i(\hat{c}_i^i - \hat{c}_i^{i+k}) - \alpha_{i-k}(\hat{c}_i^{i-k} - \hat{c}_i^{i}) + 2\epsilon\right)\right\}. %\frac{w_{i+1}b_{i+1}}{w_i}   \frac{r_1w_2b_2(\hat{c}_1^1 - \hat{c}_1^2 + 2\epsilon)}{w_1}
\]
\label{thm:rev_bound1}
\end{theorem}


\section{Special Cases}

In this section we study the problem of exploration while maintaining
a pre-exploration symmetric Nash equilibrium in two special cases.  In
both cases, it is only necessary to swap adjacent pairs of ads in
order to learn reasonable estimates of advertiser CTRs.

\subsection{Factorable Click-Through Rates}
\label{sec:factor}

\subsubsection{Maintaining Equilibrium}

%We now consider the special case in which the CTRs $c_i^s$ are
%factorable into a component that depends only on advertiser and a
%component that depends only on slot, i.e. $c_i^s = e_i c_s$.

The first special case we consider is the commonly studied setting
where $c_i^s = e_ic_s$; that is, CTRs are factored into a product of
advertiser relevance and slot-specific factors.  Since there are far
more data for estimating $c_s$ than $e_i$, we assume $c_s$ is
known and $e_i$ is to be learned for all advertisers. Under these
assumptions, using \texttt{k-swap} may seem strange; after all, we can
learn $e_i$ for all advertisers $i\leq K$ just as well by leaving them
in their current slots!  The only problem to be addressed then is to
learn CTRs of losing bidders.  Consequently, if we truly believe that
CTRs are factorable, we need only do adjacent-ad swapping ($k=1$) and
can set $r_1 = \cdots = r_{K-1} = 0$ and only allow $r_K > 0$.  In
this case, we need not worry about deviations by advertisers in slots
$1,\ldots,K-1$ to alternative slots $1,\ldots,K-1$, since the effective CTRs for
these deviations are unchanged.  Additionally, no advertiser wants to
deviate to slot $K$, since the CTR in this slot is strictly lower than
it was before exploration, and no advertiser ranked $K+1,\ldots,N$
wants a higher slot, since their effective CTRs increase.  Thus we
need only consider the incentives of the advertiser in slot $K$.  It
is not difficult to verify that the condition under which exploration
does not affect advertiser $K$'s incentives is
\[
r_K \leq \min
\bigg\{ \min_{1\leq j \leq K-1}\frac{c_K\left(v_K - p_K^K\right)
- c_j\left(v_K - p_K^j\right)}{c_K(v_K - p_K^K)},\\
\frac{v_K - p_K^K}{v_K(q_{max} + 1) - p_K^K}\bigg\},
\]
and we can find an $r_K > 0$ when \(c_K(v_K - p_K^K) > c_j(v_K -
p_K^j)\) for $j < K$.

There is, however, another possible scenario in which exploration
might be useful under the factorable CTR assumption.  Suppose that we
initially posit the factorable CTR model, but want to verify whether
this is really the case.  To do so, we can use adjacent-ad swapping to
form multiple estimates of $e_i$ using data from multiple
adjacent slots.  By comparing these estimates, we can vet our current
model while also improving our CTR estimates for losing bidders.
%and we will improve the estimates of $e_i$ for advertisements not
%shown in equilibrium ``for free''.

%Each case of advertiser incentives that we wish to consider concerns
%only the incentives of a single bidder considering alternative slots.
%Thus all of the analysis can be done in terms of $c_s$ alone.
Since CTR is factorable, our analysis need only consider the
effective slot-specific CTRs, which we assume are known,
$c_s' = (1 - r_{s-1} - r_{s}) c_{s} + r_{s-1} c_{s-1} + r_{s} c_{s+1}$.
%Now when we allow exploration through adjacent ad swapping, we have $c'_s
%= (1 - r_{s-1} - r_{s}) c_{s} + r_{s-1} c_{s-1} + r_{s} c_{s+1}$.
%If we allow the probabilities $r_i$ to take on arbitrary values, then
%even in this restricted setting, analyzing the shift in equilibrium
%bids when CTRs change from $c_i$ to $c_i'$ is complicated.  However,
%we can now benefit from setting the probabilities in special ways.
Set \(\alpha_i = \prod_{j=2}^{i}[(c_{j-1} - c_j)/(c_j - c_{j+1})].\)
By setting the swapping probabilities in this manner, the effective
CTRs in slots $2,\cdots,K-1$ are unchanged when exploration is added.
We can now simplify the bounds and characterization of
Theorem~\ref{thm:adjacentads}.  In particular, the precondition of the
theorem and the second bound on $r_1$ need only to hold for $i=1$.
Furthermore, it can be shown that in the factorable setting, the
necessary precondition $(v_1 - p_1^1)c_1 > (v_1 - p_1^j)c_j$
always holds in the minimum revenue SNE~\cite{varian07,lahaie07,cary07} for generic valuations and relevances.  
%Formal statements and proofs of these results are in the appendix.% of the extended version.

Formally, the following result obtains in the factorable setting.
\begin{theorem}
Consider the setting in which CTRs are factorable into the product of
advertiser relevance and a slot-specific CTR factor.  Let $r_i$ be
defined as in Equation~\ref{eqn:rdefgen} for all $i\in\{2,\cdots,K\}$.
Assume that advertiser 1 strictly prefers his current slot to all
others in equilibrium, i.e. the condition \(\left(v_1-p_1^1\right)c_1
> \left(v_1-p_1^j\right)c_j\) holds for all $2 \leq j \leq K$ whenever
$J_{1,j} > 0$.  Then for generic valuations and relevances there
exists an $r_1 > 0$ such that no advertiser has an incentive to
deviate from the pre-exploration SNE bids once exploration is added.
Any $r_1$ for which the following conditions hold is sufficient:
\begin{eqnarray*}
r_1 \leq \min \Bigg\{ & &
\min_{2\leq i \leq K}\frac{1}{\alpha_i + \alpha_{i-1}} ,
\qquad
\min_{1 \le i \le K; Z_i>0}
\frac{1}{Z_i} (v_i - p_i^i) c_i^i \\
& & \min_{2 \le j \le K; J_{1,j}>0}
\frac{1}{J_{1,j}}((v_1-p_1^1)c_1-(v_1-p_1^j)c_j). \ \Bigg\}
\end{eqnarray*}
where
\[
J_{1,j} = \left(v_1-p_1^1 \right)(c_1-c_2)
+ \left(v_1-p_1^j \right)
\left(\alpha_{j-1}(c_{j-1}-c_{j}) - {\alpha}_j(c_j-c_{j+1})\right)
\]
and $Z_i$ is defined according to Equation~\ref{eqn:Zdef}.
\label{thm:adjacentads_factorable}
\end{theorem}

\subsubsection{Learning Bounds}
\label{sec:learningbounds_factorable}

As in the general setting, it is possible to derive learning bounds
that show that as the number of observed queries grow, our estimates
of the advertiser CTR vectors grow arbitrarily close to the true CTRs with high probability.
%Here our estimates of CTR are simply
%\[
%\hat{c}_i^s = \frac{c_s}{c_{s_i} n_{i,s_i}} \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}
%\]
%$\hat{c}_i^s = (c_s / c_{s_i} n_{i,s_i}) \sum_{j=1}^{n_{i,s_i}}
%z_{i,s_i,j}$ for all $i$ and $s$, where $s_i = \arg\max_s c_s
%\sqrt{n_{i,s}}$.  
%We once again defer the theorem statement and proof to the appendix. % of the extended version due to lack of space.

As before, let $n_{i,s}$ denote the number of times we have observed advertiser $i$ in slot $s$ at the current fixed CTR estimates, and let $z_{i,s,j}$ be a random variable indicating whether or not the ad $i$ was clicked on the $j$th time it appeared in slot $s$.

\begin{theorem}
Suppose that CTRs can be factored into advertiser-dependent and
slot-dependent components.  In other words, for all $i$ and $s$,
$c_i^s = e_i c_s$ where $c_s$ is known.  Suppose we have observed
$n_{i,s}$ instances of ad $i$ at slot $s$ with a fixed set of
broadcasted CTR estimates.  Let $\hat{c}_i^s$ be our \emph{new}
estimate of CTR, defined as:
\[
\hat{c}_i^s = \frac{c_s}{c_{s_i} n_{i,s_i}} \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}
\]
for all advertisers $i$ and slots $s$; let $s_i = \arg\max_s c_s
\sqrt{n_{i,s}}$.  Then for any $\delta \in (0,1)$, with probability
$1-\delta$, the following holds for all $i$ and $s$:
\[
|\hat{c}_i^s - c_i^s| \leq \frac{c_s}{c_{s_i}}
\sqrt{\frac{\ln(2N/\delta)}{2n_{i,s_i}}}
%= \min_{s'} \frac{c_s}{c_{s'}}
%\sqrt{\frac{\ln(2N/\delta)}{2n_{i,s'}}}
%\leq \frac{c_s}{c_{s_i}}
%\sqrt{\frac{\ln(2N/\delta)}{2n_{i,s_i}}}
\]
\label{thm:learningbounds_sep}
\end{theorem}

\subsection{Click-through Rates with Constant Slot Ratios}
\label{sec:constratios}

\subsubsection{Maintaining Equilibrium}

In this section, we consider adjacent-ad swapping ($k=1$) for the case
in which for each player $i$, the click-through rates have constant
ratios for adjacent slots. That is, for all $i$ and all $1 \leq s \leq
K-1$, we assume that \( c_i^{s+1}/c_i^{s} = \gamma_i \leq 1 \) where
$\gamma_i$ is advertiser-dependent and unknown.
Let $\hat{\gamma}_i$ denote the search engine estimate of $\gamma_i$ and suppose as before that advertisers use these as their own estimates.
Let $\alpha_j = 1$ for
every $j\in\{2,\ldots,K-1\}$, so $r_1 = r_2 = \cdots = r_{K-1}$.
Additionally, let $\alpha_K = \min\{(\hat{\gamma}_i - 1)^2/q_{max},1\}$.
%By doing this we can simplify the conditions for $r_i > 0$ as well as the
%actual expression for $r_1$.
% we need only swap neighbor
%slots (i.e., $k=1$) to learn all the needed CTRs.

As in the previous section, we can considerably simplify the bounds
and characterization of Theorem~\ref{thm:adjacentads} in this special
case.  In particular, the first and second bounds on $r_1$ must hold,
but the third bound on $r_1$ and the precondition need only to hold
for $i = 1$ and $i = K$.
% in order to guarantee that no advertiser has incentive to deviate
%when adjacent-ad swapping is introduced.

\begin{theorem}
Suppose that CTRs are of the form $c_i^s = e_i (\hat{\gamma}_i)^{s-1}$ for
all $i$ and $s$.  Assume that advertisers $i=1,\cdots,K$ strictly
prefer their current slots to all others in equilibrium, i.e. the
following condition holds for $i=1,K$ and all $j \in \{1,\cdots,K\},
j\neq i$ whenever $J_{i,j} > 0$:
\[
(v_i-p_i^i)\hat{c}_i^i > (v_i-p_i^j)\hat{c}_i^j .
\]
Furthermore, assume that for all $i$ such that $Z_i > 0$, $v_i - p_i^i > 0$.
Then for generic valuations and relevances there exists $r_1 > 0$ such
that no advertiser has an incentive to deviate from the
pre-exploration symmetric Nash equilibrium bids once exploration is
added.  Any $r_1$ satisfying the following set of conditions is
sufficient:
\begin{eqnarray*}
r_1 \leq \min \Bigg\{
& & \frac{1}{2} , \qquad
\min_{i = 1,K; Z_i>0}
\frac{\hat{c}_i^1}{Z_i} (v_i - p_i^i)
(\hat{\gamma}_i)^{i-1} , \\
& &\min_{i=1,K; 1 \le j \le K; J_{i,j}>0}
\frac{\hat{c}_i^1}{J_{i,j}}\left((v_i-p_i^i)
(\hat{\gamma}_i)^{i-1}
- (v_i-p_i^j )(\hat{\gamma}_i)^{j-1}\right) \ \Bigg\}
\end{eqnarray*}
\label{thm:adjacentads_const_ratios}
\end{theorem}

\subsubsection{Learning Bounds for Ad-Dependent Constant Slot Ratios}
\label{sec:learningbounds_const_ratios}

We can also prove analogous learning bounds in this setting that show
that it is only necessary to explore via adjacent-ad swapping in order
to obtain CTR estimates for all advertisers at all slots.  
%This can
%be accomplished by estimating $\gamma_i$ for each $i$ as
%\[
%\hat{\gamma}_i =
%\frac{(1/n_{i,s_i+1}) \sum_{j=1}^{n_{i,s_i+1}} z_{i,s_i+1,j}}
%{(1/n_{i,s_i}) \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}}
%\]
%for a chosen slot $s_i$ at which there is a sufficient amount of data
%available.  The CTR at each slot is then estimated using
%$\hat{\gamma}_i$ and the estimate of the CTR at the designated slot
%$s_i$.

%Formal theorems describing the conditions on $r_1$ necessary to
%maintain equilibrium in this setting and the corresponding learning
%bounds can be found in the appendix along with their proofs.

Again, let $n_{i,s}$ denote the number of times we have observed advertiser
$i$ in slot $s$ at the current fixed CTR estimates, and let
$z_{i,s,j}$ be a random variable indicating whether or not the ad $i$
was clicked on the $j$th time it appeared in slot $s$.
\begin{theorem}
Suppose that CTRs are of the form $c_i^s = e_i (\gamma_i)^{s-1}$ for
all $i$ and $s$, where $\gamma_i$ is unknown and $e_i = c_i^1$.  Suppose also that the
adjacent-ad swapping algorithm has been running for $Q$ queries with a
fixed set of broadcasted CTR estimates.  Suppose we have observed
$n_{i,s}$ instances of ad $i$ at slot $s$ with a fixed set of
broadcasted CTR estimates. Let $\hat{c}_i^s$ be our \emph{new}
estimate of CTR, defined as:
\[
\hat{c}_i^s = \frac{(\hat{\gamma}_i)^{s-s_i}}{n_{i,s_i}} \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}
\]
where
\[
\hat{\gamma}_i =
\frac{(1/n_{i,s_i+1}) \sum_{j=1}^{n_{i,s_i+1}} z_{i,s_i+1,j}}
{(1/n_{i,s_i}) \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}}
\]
Then for any $\delta \in (0,1)$, with probability $1-\delta$, the
following bound holds for all advertisers $i$ and slots $s$:
\[
|\hat{c}_i^s - c_i^s| \leq \left(s(s+1) + s_i^2 + 1 \right) \sqrt{\frac{\ln(4N/\delta)}
{n_{i}}} + \frac{(s(s+1) + s_i^2) \ln(4N/\delta)}{\hat{c}_i^{s_i} n_{i}}.
\]
where $n_i = \min\{n_{i,s_i}, n_{i,s_i+1}\}$.
\label{thm:learningbounds_constratio}
\end{theorem}

\ifnum\CONTEXT=1
\section{Dealing with Continuous Context Information}
\label{S:context}

As we mentioned, a keyword entered by a user is just one (although, for our purposes, perhaps the most important one) of many characteristics of the context in which advertisements are displayed.
While our approach is directly applicable when context has a finite domain and a user is allowed to submit separate bids for each context, it is not clear whether we can extend all of our results in general when context contains features with continuous (or very large) domains and upon which bids cannot be conditioned.\footnote{For example, since a context is realized only instantaneously (i.e., for a particular impression), there would be no possibility of changing bids to adapt to the particular context.}
Since the presence of such features is quite common, we will now partially generalize some of our results.
However, we will be unable to say much as yet in a setting as general as the one above.

For the remainder of the discussion, we will focus on the subspace of continuous features upon which the advertisers cannot condition their bids.
We denote this context by $x$ and let $X$ be the set of all possible contexts that can arise.
We assume that the only effect that a particular context $x$ has is on the click-through-rates and, consequently, make these functions of context for all slots and players.
Thus, $c_a^s(x)$ denotes the click-through-rate of player $a$ in slot $s$ when context is realized to $x$.
Suppose that advertisers are ranked on the search engine based on their bids $b_a(x)$ multiplied by some weight $w_a$, which is a function of their \emph{relevance} to the keyword entered, $e_a(x)$.
Thus, we say that $w_a(x) = w_a(e_a(x))$.
We let $e_a(x) = \sum_{s=1}^K c_a^s(x)/c_s(x)$, where $c_s(x)$ is some normalization for the particular slot $s$.
Given the particular ranking of advertisers, an advertiser $a$ will pay some price, $p_a^s(x)$ for appearing in (or switching to) slot $s$.

Since we assume that advertisers cannot condition their bids on the context, we take their bids to be scalar and denoted the bid of player $a$ by $b_a$.
We let $b$ indicate the entire profile of advertiser bids and $b_{-a}$ the profile of bids of all players other than $a$.
The expected utility of the advertiser $a$ is
\begin{equation}
\label{E:exp_u}
\begin{split}
U_a(b) = E_{x\sim D}u_a(x,b) &= E_{x \sim D}[c_a(x,b)(v_a - p_a(x,b))] =\\
&= v_aE_{x \sim D}[c_a(x,b) - E_{x \sim D}[c_a(x,b)p_a(x,b)],
\end{split}
\end{equation}
where $c_a(x,b)$ is the CTR of player $a$ under context $x$ given the ranking induced by $w_a(x)$ and the configuration of all bids $b$, and, similarly, $p_a(x,b)$ is the price per click paid by $a$ under $x$ given bids $b$ and the induced ranking.

Now, suppose that we have a (dominant strategy) Nash equilibrium bid configuration $b^*$ for every possible realization of context $c_a^s$.
Clearly, when the CTRs are conditional on context, equilibrium status of $b^*$ is not affected in this case.
For example, VCG~\cite{Mascolell95} possesses this property, as does the ladder pricing scheme~\cite{aggarwal06}; both induce truthful bidding (i.e., $b^* = v$) for any realization of click-through-rates.

It is easy to see that context changes nothing in terms of maintaining equilibria during exploration: our scheme above can be applied directly.
What it complicates is the analysis of bounds on the incentives to deviate of omniscient advertisers as well as the analysis of revenue loss due to exploration.
We now address these questions to a limited degree.

\subsection{Bound on Incentives of ``Omniscient'' Advertisers}

First, we present a bound on the incentives that advertisers may have to deviate if they know their CTRs exactly.
Fix $b_{-a}$ (e.g., to equilibrium $b_{-a}^*$) and suppose that the bidders were in equilibrium before exploration.
Let $\hat{C}_a^s = E_{x \sim D}[\hat{c}_a^s(x)]$ and $C_a^s = E_{x \sim D}[c_a^s(x)]$.]
\begin{theorem}
\label{T:dev_bnd}
Suppose $|\hat{C}_a^s - C_a^s| \leq \epsilon$ for all $a,s$.
Furthermore, suppose that $E[p_a(x,b_a)] \leq \bar{p}$ uniformly on $b_a \in \R$ and the players are omniscient.
Then any player will gain at most $\bar{r}\bar{\alpha}(v_a\hat{C}_a^1 + \bar{p})$ by deviating from a pre-exploration equilibrium.
\end{theorem}
The proof of this theorem can be found in the appendix.

As we can see, the conditions in Theorem~\ref{T:dev_bnd} are very strong.
A natural question then arises: are there reasonable settings in which the bound would be of value?
The example below demonstrate the power of the bounds in the case of generalized second-price auctions.
\begin{example}
The generalized second-price auction price has a finite upper bound for a fixed set of other players' bids as long as $E_x[\frac{\max_{t \neq a}w_{t}}{w_a(x)}] < \infty$ for all $a$:
\[
p_a^s(b_a,b_{-a}) \leq E_x[\frac{\max_{t \neq a}b_{t}w_{t}(x)}{w_a(x)}] \leq \max_{t\neq a}b_tE_x[\max_{t \neq a}\frac{w_{t}(x)}{w_a(x)}].
\]
Since $b_{-a}$ is fixed, this is finite if the expected weight ratio is finite uniformly on $b_a$.
\end{example}

\subsection{Bound on Expected Revenue Loss Due to Exploration}

A final question we address in the continuous context setting is the bound on how much revenue will be lost by the search engine while the exploration is taking place.
For this bound, we assume as above that the bidders maintain their equilibrium bids $b^*$ during exploration.
If not, revenue loss can be quite unpredictable, since it is unclear in what ways the bidders will change their bids once out of equilibrium (and a new equilibrium adjustment process, even if convergent, may be quite long).
\begin{theorem}
Suppose that the players maintain their equilibrium bids $b^*$ during exploration.
Then revenue loss due to exploration is bounded by
\[
2\bar{r}\bar{\alpha}\sum_{a=1}^{N}E_{x\sim D}[p_a(x,b^*)].
\]
\end{theorem}

\fi

\ifnum\EXTENDED=1
\section{Next Steps and Open Problems}

\fi

\section{Conclusion}

We have introduced an exploration scheme which allows search engines
to learn click-through rates for advertisements.  We showed how, when
possible, to set the exploration parameters in order to eliminate the
incentives for advertisers to deviate from a pre-exploration symmetric
Nash equilibrium.  In situations in which we cannot entirely eliminate
incentives to change bids, we can make returns to changing bids
arbitrarily small.  Particularly, we can make these small enough to
ensure that bid manipulation is hardly worth advertisers' time.
Finally, we derived a bound on worst-case expected per-impression
revenue loss due to exploration.  Since this loss is zero in the limit
of no exploration, we can set exploration parameters in order to make
it arbitrarily small, while still ensuring that we eventually learn
click-through rates.

\section*{Acknowledgements}

The authors thank Alexander Strehl and Yiling Chen for insightful
comments on early drafts of this paper.

\iffalse
\ifnum\EXTENDED=1
\section{Next Steps and Open Problems}
\label{sec:open}

The following questions and problems are currently open:
\begin{itemize}

\item How can we optimize the swapping probabilities in order to
maximize revenue, information learned, etc?

\item What policy should we use for choosing which ad in ranks
$K+1,\cdots,N$ to show in slot $K$ each time we explore?

\item Need to think about what assumptions are reasonable.  In
particular, can we assume that we start with semi-reasonable estimates
of CTR or a decent initial ranking order and only wish to use
exploration to further improve these estimates?  Do we need to start
out with a pure exploration phase in order to get these initial
estimates?

\item How can we estimate how much revenue we are losing during the
exploration phases due to poor estimates of CTR?

\item Can we ensure that advertisers do not benefit by creating
multiple copies of themselves with low bids?  (Perhaps assume a base
fee or start-up charge for creating a new ad?)

\item Can we use a similar proof structure for the case in which we
might want to swap non-adjacent pairs?  (We could, for example, have
some positive probability for swapping any pair of ads.)

\item What do we want to say about the simple factorable CTR setting?
We should fill in a simple theorem analogous to
Theorem~\ref{thm:adjacentads} and then possibly move this section so
that it comes before the more complicated general CTR setting to give
intuition before we dive into the complicated general proofs.

\end{itemize}
\fi
\fi

\bibliographystyle{plain}
%\bibliographystyle{splncs}
\bibliography{explore}

\ifnum\EXTENDED=1
\appendix
\section*{Appendix}
\section{Proofs}
\subsection{Proof of Existence of SNE}
\label{appendix:sne_proof}

In the existence proof of SNE by B\"{o}rgers et al.~\cite{borgers07},
define the mapping $v_i' = w_iv_i$ and $b_i' = w_ib_i$ for every
player $i$.  Then, if $v_i'$ are used as valuations and $b_i'$ as
corresponding bids, Walrasian equilibrium prices $p'_s$ of each slot
exist in our setting by the same argument.  Since for each advertiser
$i$, $v_i$ is independent of slot $s$ and $\tilde{c}_i^s > \tilde{c}_i^{s+1}$, $p_1'
\geq p_2' \geq \cdots \geq p_K'$, also by the same argument as in
\cite{borgers07}.  Now, index each bidder by the slot they won and
define the bids of players $2 \leq i \leq K$ to be the price paid for
slot $i-1$: $b_i' = p_{i-1}'$.  Define the bids $b_i'$ of advertisers
who do not receive a slot to be $p_K'$.  The first bidder can bid
anything above $p_1'$.  By the argument presented in~\cite{borgers07},
this configuration constitutes a symmetric Nash equilibrium.

The inequalities $\tilde{c}_i^i(v_i' - p_i') \geq \tilde{c}_i^s(v_i' - p_s')$
characterize SNE in the above construction.  Dividing both sides by
$w_i$ does not change the direction of inequality.  Consequently, if
we define $p_i^s = p_s/w_i$, we recover the inequalities $\tilde{c}_i^i(v_i -
p_i^i) \geq \tilde{c}_i^s(v_i - p_i^s)$ that characterize SNE in our setting.

\subsection{Proof of Theorem~\ref{thm:adjacentads}}
\label{appendix:adjacentads}

%For reference, we restate the theorem:

In order to prove Theorem~\ref{thm:adjacentads}, we must make sure
that when the conditions stated in the theorem hold, no advertiser is
happier changing his bid and moving to a different position in the
ranking.  We break this proof into multiple parts, summarized by the
following series of lemmas.  Combining the pieces yields a set of
conditions that show that no advertiser has incentive to deviate when
exploration is added.

The first condition,
\[
r_1 \le \min_{2\leq i \leq K}\frac{1}{\alpha_i + \alpha_{i-k}},
\]
ensures that $r_i + r_{i-k}\leq 1$ for all $i$.  The other two
conditions are the subject of Lemmas~\ref{lemma:devs1Kgen}
and~\ref{lemma:no1Ktobottom} below.

\subsubsection{Incentives of $1,\cdots,K$ to Switch to
Alternate Ranks in $1,\cdots,K$}

We first verify that players $i \in \{1,\cdots,K\}$ do not want to
switch to alternate ranks $j \in \{1,\cdots,K\}$.  The following lemma
gives conditions to guarantee this.  Recall that we define $c_1^0 = 0$
and $\alpha_0 = 0$.

\begin{lemma}
Assume that the condition
\[
(v_i-p_i^i)\hat{c}_i^i
> (v_i-p_i^j)\hat{c}_i^j,
\]
holds for every $i, j \in \{1,\cdots,K\}$ in equilibrium.  Suppose
that prior to exploration advertisers' bids are in a symmetric Nash
equilibrium.  Then there is \(r_1 > 0\) such that players in slots
$1,\cdots,K$ do not wish to switch to other slots in $1,\cdots,K$ as
long as
\[
r_1 \le \min_{1 \le i,j \le K; J_{i,j}>0}
\frac{1}{J_{i,j}}\left((v_i-p_i^i)\hat{c}_i^i-(v_i-p_i^j)\hat{c}_i^j\right)
\]
where $J_{i,j}$ is as defined in Equation~\ref{eqn:Jdef}.
\label{lemma:devs1Kgen}
\end{lemma}
\begin{proof}
To ensure that players in slots $1,\cdots,K$ do not have incentive to
switch to other slots within this range, we need the condition
\begin{eqnarray*}
\lefteqn{ \left((1-r_{i-k}-r_i)\hat{c}_i^i + r_{i-k}\hat{c}_i^{i-k} +
r_i\hat{c}_i^{i+k}\right)(v_i-p_i^i)} \\
&\ge& \left((1-r_{j-k}-r_j)\hat{c}_i^j + r_{j-k}\hat{c}_i^{j-k} +
r_j\hat{c}_i^{j+k}\right)(v_i-p_i^j)
\end{eqnarray*}
to be satisfied for any $i,j \in \{1,\cdots,K\}$.  Using the
definition $r_i = \alpha_i r_1$ and rearranging terms, we obtain the
equivalent condition
\begin{eqnarray}
r_1 J_{i,j} &\leq&
(v_i-p_i^i)\hat{c}_i^i
-(v_i-p_i^j)\hat{c}_i^j.
\label{eqn:Jcondition}
\end{eqnarray}
Under our assumption, the right hand side of
Equation~\ref{eqn:Jcondition} is always strictly positive.  When
$J_{i,j}\le0$, any $r_1 \in [0,1]$ satisfies the condition we need.
When $J_{i,j}>0$, we need to guarantee
\begin{eqnarray*}
r_1 &\le& \frac{(v_i-p_i^i)\hat{c}_i^i
-(v_i-p_i^j)\hat{c}_i^j}{J_{i,j}}.
\end{eqnarray*}
Therefore, we must have for all $i, j \in \{1,\cdots,K\}$ such that
$J_{i,j} > 0$
\[
r_1 \le
\frac{1}{J_{i,j}} \left((v_i-p_i^i)\hat{c}_i^i-(v_i-p_i^j)\hat{c}_i^j\right).
\]
\end{proof}

\subsubsection{Incentive of Players $1,\ldots,K$ to Move to Ranks $K+1, \ldots, N$}

The previous lemma showed that the $K$ highest ranked advertisers do
not have incentive to deviate to another rank between $1$ and $K$ when
exploration is added under certain conditions.  We now consider the
conditions that guarantee that these advertisers do not want to move
to a rank greater than $K$.
%First, we demonstrate a simple and
%intuitive result that $w_i v_i > w_{i+1} b_{i+1}$ for $1 \leq i \leq
%K$ for generic valuations and relevances.
%\begin{lemma}
%In a symmetric Nash equilibrium with $w_iv_i \geq w_{i+1}v_{i+1}$, $w_iv_i > w_{i+1}b_{i+1}$ for $1 \leq
%i \leq K$ generic valuations and relevances.
%\label{lemma:snVB}
%\end{lemma}
%\begin{proof}
%Suppose $w_i v_i \leq w_{i+1} b_{i+1}$ for some $i \in
%\{1,2,\cdots,K\}$.

%For $j > 1$, the following upper bound on $w_j b_j$ holds in a
%symmetric Nash equilibrium (a simple extension of Varian~\cite{varian07,lahaie07}):
%\begin{equation}
%w_j b_j \leq w_{j-1}v_{j-1}(1-\beta_j) + w_{j+1}b_{j+1}\beta_j
%\label{eqn:wbbound}
%\end{equation}
%where $\beta_j = \hat{c}_j^j/\hat{c}_j^{j-1} < 1$.  From the above bound with
%$j={i+1}$ and the assumption that $w_i v_i \leq w_{i+1} b_{i+1}$, it
%follows that $w_iv_i \leq w_iv_i(1-\beta_{i+1}) +
%w_{i+2}b_{i+2}\beta_{i+1}$ and, therefore $w_iv_i \leq
%w_{i+2}b_{i+2}$.

%Applying the bound in Equation~\ref{eqn:wbbound} again with $j=i+2$,
%we see that $w_{i+2}b_{i+2} \leq w_{i+1}v_{i+1}(1-\beta_{i+2}) +
%w_{i+3}b_{i+3}\beta_{i+2}$.  Since for generic values and relevances,
%$w_{i+1}v_{i+1} < w_iv_i$, we have
%$w_{i} v_{i} \beta_{i+2} < w_{i+3} b_{i+3} \beta_{i+2}$
%$w_{i+1}v_{i+1}(1-\beta_{i+2}) +
%w_{i+3}b_{i+3}\beta_{i+2} < w_iv_i(1-\beta_{i+2}) +
%w_{i+3}b_{i+3}\beta_{i+2}$
%and, consequently, $w_iv_i < w_{i+3}b_{i+3} \leq w_{i+1}b_{i+1}$.
%Thus, $w_iv_i < w_{i+1}b_{i+1}$ and $v_i - \frac{w_{i+1}b_{i+1}}{w_i}
%< 0$.  But this is a contradiction, since player $i$ would then want
%to switch to slot $K+1$, whereas we assumed that all bidders were in a
%Nash equilibrium.
%\end{proof}

\begin{lemma}
If the players are in a symmetric Nash equilibrium with $v_i > p_i^i$ whenever $Z_i > 0$ before exploration and
if
\[
r_1 \leq
\min_{1 \le i \le K; Z_i>0}
\frac{1}{Z_i} \left(\hat{c}_i^i (v_i - p_i^i)\right)
\]
%\[
%r_1 \leq \frac{\hat{c}_1^1\left(v_1 - \frac{w_2
%b_2}{w_1}\right)}{\alpha_Kq_m\hat{c}_1^Kv_1 + (\hat{c}_1^1 - \hat{c}_1^2)\left(v_1 -
%\frac{w_2 b_2}{w_1}\right)}
%\]
where $Z_i$ is defined as in Equation~\ref{eqn:Zdef}, then the $K$
highest ranking advertisers have no incentive to switch to any slot
below $K$ for generic valuations and relevances.  Furthermore, it is
always possible to set $r_1$ in such a way such that the above holds
and $r_1 > 0$.
\label{lemma:no1Ktobottom}
\end{lemma}
\begin{proof}  We show that any player $i \in \{1,\cdots,K\}$ has
no incentive to deviate to any slot $j \in \{K+1,\cdots,N\}$.
For any $j \in \{K+1,\cdots,N\}$, in order to
guarantee that player $i$ does not want to switch to slot $j$, the
following condition must hold:
\begin{eqnarray*}
\left((1 - r_{i-k} - r_{i}) \hat{c}_i^i + r_{i-k} \hat{c}_i^{i-k} + r_{i} \hat{c}_i^{i+k}
\right)
(v_i - p_i^i)
&\geq& r_K q_j \hat{c}_i^{K-k+1} v_i.
\end{eqnarray*}
%where $p$ is the reserve price.  As we let $p$ get arbitrarily close
%to $0$ and
As we require that this condition hold simultaneously for all $j$, it becomes equivalent to
%\begin{eqnarray*}
%\hat{c}_1^1\left(v_1 - \frac{w_2 b_2}{w_1}\right) - r_1\left(\hat{c}_1^1 -
%\hat{c}_1^2\right)\left(v_1 - \frac{w_2 b_2}{w_1}\right) &\geq& r_1\alpha_Kq_m\hat{c}_1^Kv_1. %
%\end{eqnarray*}
\begin{equation}
r_1 Z_i \leq \hat{c}_i^i (v_i - p_i^i)
\label{eqn:rZbound}
\end{equation}
%By Lemma~\ref{lemma:snVB}, the right hand side of
%Equation~\ref{eqn:rZbound} is strictly positive for generic
%values and relevances.
Since $v_i - p_i^i > 0$, the right hand side of Equation~\ref{eqn:rZbound} is strictly positive.
When $Z_i \leq 0$, the constraint is
satisfied trivially.  Thus we need only that when $Z_i > 0$,
\[
r_1 \leq \frac{1}{Z_i} \left(\hat{c}_i^i (v_i - p_i^i)\right)
\]
%\[
%r_1 \le \frac{\hat{c}_1^1\left(v_1 - \frac{w_2
%b_2}{w_1}\right)}{\alpha_Kq_m\hat{c}_1^Kv_1 + (\hat{c}_1^1 - \hat{c}_1^2)\left(v_1 -
%\frac{w_2 b_2}{w_1}\right)}.
%\]
%By Lemma~\ref{lemma:snVB}, the numerator is strictly positive in a
%symmetric Nash equilibrium for generic valuations and relevances, and
%thus since the denominator is also strictly positive, we can always
%choose $r_1 > 0$ to be small enough so that this condition is
%satisfied.
\end{proof}

\subsubsection{Incentives of Players $K+1,\ldots,N$ to Move to Slots $1,\ldots,K$}

\begin{lemma}
No advertiser in slots $K+1,\cdots,N$ prefers to deviate and move to
any slot in $1,\cdots,K$ when exploration is added.
\end{lemma}
\begin{proof}
Since the set of advertisers $K+1,\cdots,N$ received no clicks in the
pre-exploration symmetric Nash equilibrium, we know that it must be
the case that for all $i$ and $j$ such that $K+1 \leq i \leq N$ and $1
\leq j \leq K$,
\[
v_i - p_i^j \leq 0 .
\]
In other words, these advertisers have a value per click that is lower
than the equilibrium price per click of any slot between $1$ and $K$.
When exploration is added, the CTRs of these slots might change, but
the price is still higher than these advertisers' values.  Thus the
advertisers still are not interested in these slots when exploration
is added.
\end{proof}

Note that we have not addressed the incentives for players
$K+1,\cdots,N$ to deviate to other ranks $K+1$ or higher.  This case
will depend on the way in which the distribution $q_i$ is chosen.
There are many possible choices for which players $K+1,\cdots,N$ will
not have incentive to swap ranks among themselves.


\subsection{Proof of Theorem~\ref{thm:learningbounds_gen}}
\label{appendix:learningbounds_gen}

The proof of this theorem relies on several applications of a version
of Hoeffding's inequality which is stated here for completeness.
\begin{lemma} (Hoeffding's Inequality)
Let $x_1, \cdots, x_n$ be independent random variables bounded in the
range $[0,1]$.  Let $\hat{x} = (1/n) \sum_{i=1}^n x_i$ denote the mean of
these variables.  Then for any $\delta \in (0,1)$, with probability
$1-\delta$,
\[
|\hat{x} - E[\hat{x}]| \leq \sqrt{\frac{\ln(2/\delta)}{2n}} .
\]
\label{lemma:hoeffding}
\end{lemma}

We apply Hoeffding's inequality first to bound the error of our
estimation of the click-through rate of ad $i$ in slot $s$ given that
we have observed the ad in this slot $n_{i,s}$ times.  The following
holds with probability $1-\delta$.
\[
|\hat{c}_i^s - c_i^s| \leq
\sqrt{\frac{\ln(2/\delta)}{2n_{i,s}}}
\]


To prove the final piece of the theorem, we can apply Hoeffding's
inequality once again to bound the deviation of $n_{i,s}$ from its
expectation with probably $1-\delta$ as follows.
\[
|n_{i,s} - E[n_{i,s}]| \leq
\sqrt{Q \ln(2/\delta) / 2}
\]

Dividing $\delta$ by $NK$ and applying the union bound completes the
proof.

%Applying the union bound, we find that for any $\delta \in (0,1)$,
%with probability $1-\delta$, the following holds for all $i$ and $s$.
%\[
%|\hat{c}_i^s - c_i^s| \leq
%\sqrt{\frac{\ln(4KN/\delta)}
%{2 (E[n_{i,s}] - \sqrt{Q \ln(4KN/\delta) / 2}) }}
%\]
%
%Plugging in the appropriate expression for $E[n_{i,s}]$ completes the
%proof.


\subsection{Proof of Theorem~\ref{thm:dev_bound1}}

First, we need a useful lemma that bounds the effective CTRs.
\begin{lemma}
\(|c_i^{'s} - \hat{c}_i^{'s}| \leq \epsilon\).
\label{L:eff_ctr_bnd}
\end{lemma}
\begin{proof}
\begin{eqnarray*}
\abs{c_i^{'s}-\hat{c}_i^{'s}} &=& \abs{(1-r_{s-k}-r_s)(c_i^s-\hat{c}_i^s) + r_{s-k}(c_i^{s-k}-\hat{c}_i^{s-k}) + r_s (c_i^{s+k}-\hat{c}_i^{s+k})} \\
  &\le& (1-r_{s-k}-r_s) \epsilon + r_{s-k} \epsilon + r_s \epsilon \,\,=\,\, \epsilon. %
\end{eqnarray*}
\end{proof}

%We only show the case of incentives of players $1 \leq i \leq K$ deviating to $1 \leq i \leq K$, as the other cases are analogous.
Now consider a player $i$ deviating to slot (or rank) $j$:
\[
\begin{split}
& c_i^{'i}(v_i - p_i^i)
\geq \hat{c}_i^{'i}(v_i - p_i^i) - \epsilon(v_i - p_i^i) \\
& \geq \hat{c}_i^{'j}(v_i - p_i^j) - \epsilon(v_i - p_i^i)
\geq c_i^{'j}(v_i - p_i^j) - \epsilon(v_i - p_i^i) - \epsilon(v_i - p_i^j) \\
& \geq c_i^{'j}(v_i - p_i^j) - 2\epsilon(v_i - p_i^K).
\end{split}
\]
Recall that if $j \geq K+1$, $c_i^j = 0$.

\subsection{Proof of Theorem~\ref{thm:dev_bound2}}

%Let \(p_i^i = \frac{w_{i+1}b_{i+1}}{w_i}\) and \(p_i^j = \frac{w_{j+1}b_{j+1}}{w_i}\) (assuming player $i$ in the latter case) for simplicity of notation.
Consider incentives for some player $i$ for deviating to slot $j$ and let
\[
\mu = r_1(\alpha_i(\hat{c}_i^i - \hat{c}_i^{i+k}) + \alpha_{j-k}(\hat{c}_i^{j-k} - \hat{c}_i^{j}) + 2\epsilon(\alpha_{i} + \alpha_{j-k}))(v_i - p_i^K).
\]
Then,
\[
\begin{split}
&[(1-r_{i-k} - r_i)c_i^i +r_{i-k}c_i^{i-k} + r_ic_i^{i+k}](v_i - p_i^i) + \mu \\
& \geq [(1-r_{i-k} - r_i)c_i^i +r_{i-k}c_i^{i-k} + r_ic_i^{i+k}](v_i - p_i^i) +\\
&\quad\quad r_i(c_i^i - c_i^{i+k})(v_i - p_i^K) + r_{j-k}(c_i^{j-k} - c_i^{j})(v_i - p_i^K) \\
&\geq [(1-r_{i-k} - r_i)c_i^i(v_i - p_i^i) + r_{i-k}c_i^{i-k}(v_i - p_i^i) +\\
&\quad\quad r_ic_i^i(v_i - p_i^i) + r_{j-k}(c_i^{j-k} - c_i^{j})(v_i - p_i^j) \\
&= c_i^i(v_i - p_i^i) + r_{i-k}(c_i^{i-k} - c_i^i)(v_i - p_i^i) + r_{j-k}(c_i^{j-k} - c_i^{j})(v_i - p_i^j) \\
&\geq c_i^j(v_i - p_i^j) + r_{j-k}(c_i^{j-k} - c_i^{j})(v_i - p_i^j) \\
&\geq c_i^j(v_i - p_i^j) + r_{j-k}(c_i^{j-k} - c_i^{j})(v_i - p_i^j) - r_j(c_i^j - c_i^{j+k})(v_i - p_i^j) \\
&= [(1-r_{j-k} - r_j)c_i^j +r_{j-k}c_i^{j-k} + r_jc_i^{j+k}](v_i - p_i^j),
\end{split}
\]
where the inequalities follow from the assumption that $c_i^i(v_i - p_i^i) \geq c_i^j(v_i - p_i^j)$ and the fact that $p_i^s \geq p_i^K$ for any slot $s$.

\subsection{Proof of Theorem~\ref{thm:rev_bound1}}

\[
\begin{split}
\Delta_{Revenue} &= \sum_{i=1}^Kc_i^ip_i^i - \sum_{i=1}^Kc_i^{'i}p_i^i
= \sum_{i=1}^Kp_i^i(c_i^i - c_i^{'i}) \\
&= \sum_{i=1}^Kp_i^i(r_i(\hat{c}_i^i - \hat{c}_i^{i+k}) - r_{i-k}(\hat{c}_i^{i-k} - \hat{c}_i^i) + 2\epsilon) \\
&= r_1\sum_{i=1}^Kp_i^i\left(\alpha_i(\hat{c}_i^i - \hat{c}_i^{i+k}) - \alpha_{i-k}(\hat{c}_i^{i-k} - \hat{c}_i^i) + 2\epsilon\right).
\end{split}
\]
%For players $2\leq i \leq K$, \(c_i^i - c_i^{'i} \leq (\hat{c}_i^i +\epsilon) - (\hat{c}_i^{'i} - \epsilon) = 2\epsilon\).
%For player $1$, \(c_1^1 - (1 - r_1)c_1^1 - r_1c_1^2 = r_1(c_1^1 - c_1^2) \leq r_1(\hat{c}_1^1 - \hat{c}_1^{1+k} + 2\epsilon)\).

%\subsection{Proof of Theorem~\ref{thm:rev_bound2}}

%For every $i$
%\[
%\begin{split}
%c_i^i - c_i^{'i} &= c_i^i - (1 - r_{i-1} - r_{i}) c_{i}^{i} + r_{i-1} c_{i}^{i-1} + r_{i} c_{i}^{i+1} - \hat{c}_i^{'i} =\\
%&= r_{i-1}(c_i^i - c_i^{i-i}) + r_{i}(c_i^i - c_i^{i+1}) \leq\\
%&\leq r_{i}(c_i^i - c_i^{i+1}) \leq r_i(\hat{c}_i^i - \hat{c}_i^{i+1} + 2\epsilon).
%\end{split}
%\]
%Plugging in $r_i = \alpha_ir_1$ gives the result.

\subsection{Theorem Statement and Proof for the Factorable Case}
\label{appendix:adjacentads_factorable}

%Theorem~\ref{thm:adjacentads_factorable} below is mentioned briefly in
%Section~\ref{sec:factor}.  
For completeness, we restate Theorem~\ref{thm:adjacentads_factorable} formally before providing its proof.  Before diving into the proof of the main
theorem, note that by defining $\alpha_i$ to be
\[
\alpha_i = \prod_{j=2}^{i}\left(\frac{c_{j-1} - c_j}{c_j - c_{j+1}}\right),
\]
we obtain the following recursive expression for $r_i$:
\begin{equation}
r_{i} = r_{i-1} \left(\frac{c_{i-1} - c_i}{c_i - c_{k+1}}\right).
\label{eqn:rdefgen}
\end{equation}
for all $i \in \{2,\cdots,K\}$. This setting of probabilities is
convenient because the CTRs of an ad in slots $2,\cdots,K$ do not
change when exploration is added if bids do not change, as shown in
the following useful lemma .
\begin{lemma}
When $r_i$ are computed recursively by (\ref{eqn:rdefgen}), then
$c'_{i}=c_i$ for all $i \in \{2,\cdots,K\}$.
\label{lemma:samectr}
\end{lemma}
\begin{proof}
For any $i \in \{2,\cdots,K\}$,
\begin{eqnarray*}
c'_{i} &=& (1 - r_{i-1} - r_{i}) c_i + r_{i-1} c_{i-1} + r_{i} c_{i+1} \\
&=& c_i + r_{i-1} (c_{i-1} - c_i) - r_{i} (c_i - c_{i+1}) \\
&=& c_i + r_{i-1} (c_{i-1} - c_i)
- r_{i-1} \left(\frac{c_{i-1} - c_i}{c_i - c_{i+1}}\right) (c_i - c_{i+1})
= c_i.
\end{eqnarray*}
\end{proof}

Now we are ready to state and prove the main theorem.

\begin{theorem}
Consider the setting in which CTRs are factorable into the product of
advertiser relevance and a slot-specific CTR factor.  Let $r_i$ be
defined as in Equation~\ref{eqn:rdefgen} for all $i\in\{2,\cdots,K\}$.
Assume that advertiser 1 strictly prefers his current slot to all
others in equilibrium, i.e. the condition \(\left(v_1-p_1^1\right)c_1
> \left(v_1-p_1^j\right)c_j\) holds for all $2 \leq j \leq K$ whenever
$J_{1,j} > 0$.  Then for generic valuations and relevances there
exists an $r_1 > 0$ such that no advertiser has an incentive to
deviate from the pre-exploration SNE bids once exploration is added.
Any $r_1$ for which the following conditions hold is sufficient:
\begin{eqnarray*}
r_1 \leq \min \Bigg\{ & &
\min_{2\leq i \leq K}\frac{1}{\alpha_i + \alpha_{i-1}} ,
\qquad
\min_{1 \le i \le K; Z_i>0}
\frac{1}{Z_i} (v_i - p_i^i) c_i^i \\
& & \min_{2 \le j \le K; J_{1,j}>0}
\frac{1}{J_{1,j}}((v_1-p_1^1)c_1-(v_1-p_1^j)c_j). \ \Bigg\}
\end{eqnarray*}
where
\[
J_{1,j} = \left(v_1-p_1^1 \right)(c_1-c_2)
+ \left(v_1-p_1^j \right)
\left(\alpha_{j-1}(c_{j-1}-c_{j}) - {\alpha}_j(c_j-c_{j+1})\right)
\]
and $Z_i$ is defined according to Equation~\ref{eqn:Zdef}.
%\label{thm:adjacentads_factorable}
\end{theorem}

First, we demonstrate a simple and
intuitive result that $w_i v_i > w_{i+1} b_{i+1}$ for $1 \leq i \leq
K$ for generic valuations and relevances.
\begin{lemma}
In a symmetric Nash equilibrium with $w_iv_i \geq w_{i+1}v_{i+1}$,
$w_iv_i > w_{i+1}b_{i+1}$ for $1 \leq i \leq K$ for generic valuations
and relevances.
\label{lemma:snVB}
\end{lemma}
\begin{proof}
Suppose $w_i v_i \leq w_{i+1} b_{i+1}$ for some $i \in
\{1,2,\cdots,K\}$.

For $j > 1$, the following upper bound on $w_j b_j$ holds in a
symmetric Nash equilibrium (a simple extension of Varian~\cite{varian07,lahaie07}):
\begin{equation}
w_j b_j \leq w_{j-1}v_{j-1}(1-\beta_j) + w_{j+1}b_{j+1}\beta_j
\label{eqn:wbbound}
\end{equation}
where $\beta_j = c_j/c_{j-1} < 1$.  From the above bound with
$j={i+1}$ and the assumption that $w_i v_i \leq w_{i+1} b_{i+1}$, it
follows that $w_iv_i \leq w_iv_i(1-\beta_{i+1}) +
w_{i+2}b_{i+2}\beta_{i+1}$ and, therefore $w_iv_i \leq
w_{i+2}b_{i+2}$.

Applying the bound in Equation~\ref{eqn:wbbound} again with $j=i+2$,
we see that $w_{i+2}b_{i+2} \leq w_{i+1}v_{i+1}(1-\beta_{i+2}) +
w_{i+3}b_{i+3}\beta_{i+2}$.
When CTRs are factorable, $w_iv_i \geq w_{i+1}v_{i+1}$~\cite{borgers07,edelman05,varian07}.
Since for generic values and relevances, $w_{i+1}v_{i+1} < w_iv_i$, we have
$w_{i} v_{i} \beta_{i+2} < w_{i+3} b_{i+3} \beta_{i+2}$
%$w_{i+1}v_{i+1}(1-\beta_{i+2}) +
%w_{i+3}b_{i+3}\beta_{i+2} < w_iv_i(1-\beta_{i+2}) +
%w_{i+3}b_{i+3}\beta_{i+2}$
and, consequently, $w_iv_i < w_{i+3}b_{i+3} \leq w_{i+1}b_{i+1}$.
Thus, $w_iv_i < w_{i+1}b_{i+1}$ and $v_i - \frac{w_{i+1}b_{i+1}}{w_i}
< 0$.  But this is a contradiction, since player $i$ would then want
to switch to slot $K+1$, whereas we assumed that all bidders were in a
Nash equilibrium.
\end{proof}
Thus, $v_i > p_i^i$ for all players $i$ when CTRs are factorable.

Given Lemma~\ref{lemma:samectr}, note that if none of the bidders in
slots $2,\cdots,N$ wanted to move up to slot 1 in equilibrium before
exploration, they have even less incentive to do so once exploration
is added since the effective CTR for slot 1 is now lower and the
effective CTR of their own slots is the same by our definition of
$\alpha_i$.  Furthermore, none of the bidders in slots $2,\cdots,N$
want to to switch to alternate slots in $2,\cdots,K$ since the
effective CTRs are now the same for all of these slots and do not
depend on the bidder's identity due to the factorization assumption.
Consequently, we need only examine whether or not the top bidder wants
to move down, or whether any bidder might like to move into a slot
below $K$.  The analysis of these cases is directly analogous to the
analysis in the proof of Theorem~\ref{thm:adjacentads}, and the
sufficient conditions on $r_1$ are derived in the same manner.

\subsection{Proof of Player 1's Strict Preference at SNE}
\label{appendix:min_symm}

Below is a formal statement and proof of the theorem mentioned in
Section~\ref{sec:factor}.

\begin{theorem}
Suppose that the players are playing a minimum symmetric Nash
equilibrium.  Then for generic valuations and relevances \((v_1 -
p_1^1)c_1 > (v_1 - p_1^j)c_j.\)
\label{thm:min_symm}
\end{theorem}

%Note that $e_i$ cancels from both sides of equations, since
%comparisons are made for the same player.
\[
\begin{split}
c_1w_2b_2 - c_jw_{j+1}b_{j+1} &= \sum_{t=1}^{K}(c_t - c_{t+1})w_{t+1}v_{t+1} - \sum_{t=j}^{K}(c_t - c_{t+1})w_{t+1}v_{t+1}
\\
&= \sum_{t=1}^{j-1}(c_t - c_{t+1})w_{t+1}v_{t+1}
\\
&\leq w_2v_2 \sum_{t=1}^{j-1}(c_t - c_{t+1}) = w_2v_2(c_1 - c_j).
\end{split}
\]
For generic valuations and relevances,
\(w_2v_2(c_1 - c_s) < w_1v_1(c_1 - c_s)\) and, consequently,
\(c_1w_2b_2 - c_jw_{j+1}b_{j+1} < w_1v_1c_1 - w_1v_1c_j\) for every $2\leq j \leq K$.
Rewriting, we get \(c_1(w_1v_1 - w_2b_2) > c_j(w_1v_1 - w_{j+1}b_{j+1})\) and we recover the desired strict inequality.

\subsection{Learning Bounds in the Factorable Case}
\label{app:learningbounds_sep}

The proof of the following theorem, which is presented in
Section~\ref{sec:factor}, is given below.  As before, let $n_{i,s}$
denote the number of times we have observed advertiser $i$ in slot $s$
at the current fixed CTR estimates, and let $z_{i,s,j}$ be a random
variable indicating whether or not the ad $i$ was clicked on the $j$th
time it appeared in slot $s$.

\begin{theorem}
Suppose that CTRs can be factored into advertiser-dependent and
slot-dependent components.  In other words, for all $i$ and $s$,
$c_i^s = e_i c_s$ where $c_s$ is known.  Suppose we have observed
$n_{i,s}$ instances of ad $i$ at slot $s$ with a fixed set of
broadcasted CTR estimates.  Let $\hat{c}_i^s$ be our \emph{new}
estimate of CTR, defined as:
\[
\hat{c}_i^s = \frac{c_s}{c_{s_i} n_{i,s_i}} \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}
\]
for all advertisers $i$ and slots $s$; let $s_i = \arg\max_s c_s
\sqrt{n_{i,s}}$.  Then for any $\delta \in (0,1)$, with probability
$1-\delta$, the following holds for all $i$ and $s$:
\[
|\hat{c}_i^s - c_i^s| \leq \frac{c_s}{c_{s_i}}
\sqrt{\frac{\ln(2N/\delta)}{2n_{i,s_i}}}
%= \min_{s'} \frac{c_s}{c_{s'}}
%\sqrt{\frac{\ln(2N/\delta)}{2n_{i,s'}}}
%\leq \frac{c_s}{c_{s_i}}
%\sqrt{\frac{\ln(2N/\delta)}{2n_{i,s_i}}}
\]
%\label{thm:learningbounds_sep}
\end{theorem}

Now, for each advertiser $i$, we base our estimate of click-through rate on
data from the slot $s_i$ maximizing $c_s \sqrt{n_s}$.  Let
\[
\hat{c}_i^{s_i} = \frac{1}{n_{i,s_i}} \sum_{j=1}^{n_{i,s_i}} z_{i,{s_i},j}
\]
be the estimate of click-through rate in this slot.  By Hoeffding's
inequality, for any $\delta' \in (0,1)$, with probability $1-\delta'$,
\[
|\hat{c}_i^{s_i} -  c_i^{s_i}| \leq \sqrt{\frac{\ln(2/\delta')}{2n_{i,s_i}}} .
\]
Since for any $s$, $c_i^s = c_i^{s-i} (c_{s}/c_{s_i})$ and
$\hat{c}_i^s = \hat{c}_i^{s-i} (c_{s}/c_{s_i})$, we thus have for all
$s$
\[
|\hat{c}_i^{s} -  c_i^{s}| \leq \frac{c_{s}}{c_{s_i}} \sqrt{\frac{\ln(2/\delta')}{2n_{i,s_i}}} .
\]

We want this claim to hold for all $N$ advertisers.  Setting $\delta'
= \delta / N$ and applying the union bound completes the proof.


\subsection{Theorem Statement and Proof for Constant Slot Ratios}
\label{appendix:adjacentads_const_ratios}

The following Theorem is mentioned in Section~\ref{sec:constratios}.
For completeness, the theorem and proof are formally stated here.

\begin{theorem}
Suppose that CTRs are of the form $c_i^s = e_i (\hat{\gamma}_i)^{s-1}$ for
all $i$ and $s$.  Assume that advertisers $i=1,\cdots,K$ strictly
prefer their current slots to all others in equilibrium, i.e. the
following condition holds for $i=1,K$ and all $j \in \{1,\cdots,K\},
j\neq i$ whenever $J_{i,j} > 0$:
\[
(v_i-p_i^i)\hat{c}_i^i > (v_i-p_i^j)\hat{c}_i^j .
\]
Furthermore, assume that for all $i$ such that $Z_i > 0$, $v_i - p_i^i > 0$.
Then for generic valuations and relevances there exists $r_1 > 0$ such
that no advertiser has an incentive to deviate from the
pre-exploration symmetric Nash equilibrium bids once exploration is
added.  Any $r_1$ satisfying the following set of conditions is
sufficient:
\begin{eqnarray*}
r_1 \leq \min \Bigg\{
& & \frac{1}{2} , \qquad
\min_{i = 1,K; Z_i>0}
\frac{\hat{c}_i^1}{Z_i} (v_i - p_i^i)
(\hat{\gamma}_i)^{i-1} , \\
& &\min_{i=1,K; 1 \le j \le K; J_{i,j}>0}
\frac{\hat{c}_i^1}{J_{i,j}}\left((v_i-p_i^i)
(\hat{\gamma}_i)^{i-1}
- (v_i-p_i^j )(\hat{\gamma}_i)^{j-1}\right) \ \Bigg\}
\end{eqnarray*}
%\label{thm:adjacentads_const_ratios}
\end{theorem}

The incentives for player $1$ and players $K, K+1, \cdots, N$ can be
analyzed exactly as in the proof of Theorem~\ref{thm:adjacentads}, and
the conditions on $r_1$ follow from this analysis as before.  Thus
here we focus only on the incentives of players $2,\cdots,K-1$.

\subsubsection{Incentives of Players $2,\ldots,K-1$ to Move to Slots $1,\ldots,K$}

\begin{lemma}
In the constant ratio setting, when $r_i = r_1$ for $i \in
{2,\cdots,K}$, players $2,\ldots,K-1$ do not have incentive to deviate
to other slots $1,\ldots,K$ during adjacent-ad swapping exploration
for any $r_1$.
\end{lemma}
\begin{proof}
To ensure that players in slots $2,\cdots,K-1$ do not have incentive to
switch to other slots within this range, we need the condition
\begin{eqnarray*}
\lefteqn{ \left((1-r_{i-1}-r_i)\hat{c}_i^i + r_{i-1}\hat{c}_i^{i-1} +
r_i\hat{c}_i^{i+1}\right)(v_i-p_i^i)} \\
&\ge& \left((1-r_{j-1}-r_j)\hat{c}_i^j + r_{j-1}\hat{c}_i^{j-1} +
r_j\hat{c}_i^{j+1}\right)(v_i-p_i^j)
\end{eqnarray*}
to be satisfied for any $i,j \in \{1,\cdots,K\}$.  Setting \(r_i =
r_1\) for all $i$ and plugging in \(\hat{c}_i^{s-1} = \hat{c}_i^s/\hat{\gamma}_i\) and
\(\hat{c}_i^{s+1} = \hat{c}_i^s\hat{\gamma}_i\), we get
\begin{eqnarray*}
(1-r_{s-1}-r_s)\hat{c}_i^s + r_{s-1}\hat{c}_i^{s-1} + r_s\hat{c}_i^{s+1}
&=& \hat{c}_i^s + \left(\hat{\gamma}_i - 2 + \frac{1}{\hat{\gamma}_i}\right) r_1 \hat{c}_i^s \\
&=& \left(1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right)\hat{c}_i^s \\
\end{eqnarray*}
for every player $i$ and for all $s = 2,\ldots,K-1$.
Thus, the condition that needs to be satisfied is
\[
\hat{c}_i^i\left(1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right)(v_i-p_i^i) \geq \hat{c}_i^j\left(1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right)(v_i-p_i^j)
\]
which is equivalent to the symmetric equilibrium condition before
exploration and thus holds by assumption.  For deviation to slot 1,
note that \((1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}) \geq 1\) and
thus $\hat{c}_i^{'i} \geq \hat{c}_i^i$ for every $i=2,\ldots,K-1$, whereas
$\hat{c}_1^{'1} \leq \hat{c}_1^1$.  Consequently, if deviations to 1 were
unprofitable prior to exploration, they are certainly still
unprofitable with exploration.  Finally, for deviations to slot $K$, note that
the effective CTR for slot $K$ is \(\hat{c}_i^K(1 + r_1(\hat{\gamma}_i - 2)) \leq
\hat{c}_i^K(1 + r_1(\hat{\gamma}_i + 1/\hat{\gamma}_i - 2))\).  Thus,
\begin{eqnarray*}
\hat{c}_i^i\left(1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right)(v_i-p_i^i) &\geq& \hat{c}_i^K\left(1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right)(v_i-p_i^j)\\
&\geq& \hat{c}_i^K\left(1 + r_1(\hat{\gamma}_i - 2)\right)(v_i-p_i^j)
\end{eqnarray*}
\end{proof}

\subsubsection{Incentives of Players $2,\ldots,K-1$ to Move to Ranks $K+1,\ldots,N$}

\begin{lemma}
In the constant ratio setting, when $r_i = r_1$ for $i \in
{2,\cdots,K}$, players in slots $2,\ldots,K-1$ have no incentive to
move to ranks $K+1,\ldots,N$ during adjacent-ad swapping exploration
for any $r_1$.
\end{lemma}
\begin{proof}
Since \(\alpha_K = \min\{\frac{(\hat{\gamma}_i - 1)^2}{q_{max}},1\}\),
we have that \(\alpha_Kq_{max} \leq (\hat{\gamma}_i - 1)^2\) or \(\frac{(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i} \geq \alpha_Kq_{max}(\frac{1}{\hat{\gamma}_i})^{K-i}\).

In order to eliminate incentives to deviate to slots $K+1,\ldots,N$, we need to satisfy
\[
\left(1 + \frac{r_1(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right)(v_i - p_i^i) \geq r_1\alpha_Kq_{max}(\frac{1}{\hat{\gamma}_i})^{K-i}v_i,
\]
or, alternatively,
\[
(v_i - p_i^i) \geq r_1\left(v_i\left(\alpha_Kq_{max}\left(\frac{1}{\hat{\gamma}_i}\right)^{K-i} - \frac{(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right) - \frac{p_i^i(\hat{\gamma}_i - 1)^2}{\hat{\gamma}_i}\right).
\]
But since \((\hat{\gamma}_i - 1)^2/\hat{\gamma}_i \geq
\alpha_Kq_{max}(1/\hat{\gamma}_i)^{K-i}\), we know that
\(\alpha_Kq_{max}(1/\hat{\gamma}_i)^{K-i} - (\hat{\gamma}_i - 1)^2/\hat{\gamma}_i \leq
0,\) and the right-hand side is at most 0.  Since the left-hand side
is at least 0 (otherwise our assumption of equilibrium prior to
exploration does not hold), any $r_1$ satisfies the condition.
\end{proof}


\subsection{Learning Bounds for Constant Slot Ratios}
\label{app:learningbounds_constratio}

The following theorem giving learning bounds for the constant slot
ratio setting is mentioned in Section~\ref{sec:constratios}.  Again,
let $n_{i,s}$ denote the number of times we have observed advertiser
$i$ in slot $s$ at the current fixed CTR estimates, and let
$z_{i,s,j}$ be a random variable indicating whether or not the ad $i$
was clicked on the $j$th time it appeared in slot $s$.

\begin{theorem}
Suppose that CTRs are of the form $c_i^s = e_i (\gamma_i)^{s-1}$ for
all $i$ and $s$, where $\gamma_i$ is unknown and $e_i = c_i^1$.  Suppose also that the
adjacent-ad swapping algorithm has been running for $Q$ queries with a
fixed set of broadcasted CTR estimates.  Suppose we have observed
$n_{i,s}$ instances of ad $i$ at slot $s$ with a fixed set of
broadcasted CTR estimates. Let $\hat{c}_i^s$ be our \emph{new}
estimate of CTR, defined as:
\[
\hat{c}_i^s = \frac{(\hat{\gamma}_i)^{s-s_i}}{n_{i,s_i}} \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}
\]
where
\[
\hat{\gamma}_i =
\frac{(1/n_{i,s_i+1}) \sum_{j=1}^{n_{i,s_i+1}} z_{i,s_i+1,j}}
{(1/n_{i,s_i}) \sum_{j=1}^{n_{i,s_i}} z_{i,s_i,j}}
\]
Then for any $\delta \in (0,1)$, with probability $1-\delta$, the
following bound holds for all advertisers $i$ and slots $s$:
\[
|\hat{c}_i^s - c_i^s| \leq \left(s(s+1) + s_i^2 + 1 \right) \sqrt{\frac{\ln(4N/\delta)}
{n_{i}}} + \frac{(s(s+1) + s_i^2) \ln(4N/\delta)}{\hat{c}_i^{s_i} n_{i}}.
\]
where $n_i = \min\{n_{i,s_i}, n_{i,s_i+1}\}$.
%\label{thm:learningbounds_constratio}
\end{theorem}

The proof is divided into a sequence of lemmas.  The first one, stated
below, follows from a direct application of Hoeffding's inequality
and the union bound.  Recall that $s_i$ is a chosen slot to explore
for ad $i$.

\begin{lemma}
For each $i$, with probability at least $1-\delta$, we have
\begin{eqnarray}
\abs{\hat{c}_i^{s_i}-c_i^{s_i}} \le \Delta_i, &~&
\abs{\hat{c}_i^{s_i+1}-c_i^{s_i+1}} \le \Delta_i,
\label{eqn:learningbounds_assumption}
\end{eqnarray}
where
\begin{eqnarray*}
\Delta_i &=& \max\left\{ \sqrt{\frac{\ln
\frac{4}{\delta}}{2n_{i,s_i}}}, \sqrt{\frac{\ln
\frac{4}{\delta}}{2n_{i,s_i+1}}} \right\}.
\end{eqnarray*}
\end{lemma}

\begin{lemma}
Assuming Equation~\ref{eqn:learningbounds_assumption} holds.  Then
for each $i$ we have
\begin{eqnarray*}
\abs{\hat{\gamma}_i^s-\gamma_i^s} &\le& \frac{s(s+1)
\Delta_i}{\hat{c}_i^{s_i}}.
\end{eqnarray*}
\end{lemma}

\begin{proof} First we can see that for any $i$,
\begin{eqnarray*}
\abs{\hat{\gamma}_i-\gamma_i} &=& \abs{\frac{\hat{c}_i^{s_i+1}}{\hat{c}_i^{s_i}} - \frac{c_i^{s_i+1}}{c_i^{s_i}}}
  = \frac{\abs{\hat{c}_i^{s_i+1}c_i^{s_i}-\hat{c}_i^{s_i}c_i^{s_i+1}}}{\hat{c}_i^{s_i}c_i^{s_i}} \\
  &=& \frac{\abs{(\hat{c}_i^{s_i+1}-c_i^{s_i+1})c_i^{s_i}-(\hat{c}_i^{s_i}-c_i^{s_i})c_i^{s_i+1}}}{\hat{c}_i^{s_i}c_i^{s_i}} \\
  &\le& \frac{\abs{\hat{c}_i^{s_i+1}-c_i^{s_i+1}}c_i^{s_i} + \abs{\hat{c}_i^{s_i}-c_i^{s_i}}c_i^{s_i+1}}{\hat{c}_i^{s_i}c_i^{s_i}} \\
  &\le& \frac{\Delta_i (c_i^{s_i} + c_i^{s_i+1})}{\hat{c}_i^{s_i}c_i^{s_i}}
  \le \frac{2 \Delta_i }{\hat{c}_i^{s_i}}. %
\end{eqnarray*}

Now, by Taylor's theorem, we have
\begin{eqnarray*}
(\hat{\gamma}_i)^s &=& (\gamma_i)^s + s (\hat{\gamma}_i-\gamma_i) \left((\hat{\gamma}_i)^{s-1}-(\gamma_i)^{s-1}\right) + \frac{1}{2}s(s-1)(\hat{\gamma}_i-\gamma_i)^2(\tilde{\gamma})^{s-2}, %
\end{eqnarray*}
for some $\tilde{\gamma}$ between $\gamma_i$ and $\hat{\gamma}_i$.
Since $\abs{(\hat{\gamma}_i)^{s-1}-(\gamma_i)^{s-1}} \le 1$ and $0
\le \gamma_i, \hat{\gamma}_i, \tilde{\gamma} \le 1$,\footnote{If
$\hat{\gamma}_i$ happens to be greater than $1$ (which is
possible), then we can safely set it to $1$.  This change can only
make the estimate more accurate, since we know $\gamma_i \in
(0,1]$.} we have
\begin{eqnarray*}
    \abs{(\hat{\gamma}_i)^s-(\gamma_i)^s} %
&=& \abs{s (\hat{\gamma}_i-\gamma_i) \left((\hat{\gamma}_i)^{s-1}-(\gamma_i)^{s-1}\right) + \frac{1}{2}s(s-1)(\hat{\gamma}_i-\gamma_i)^2(\tilde{\gamma})^{s-2}} \\
&\le& \abs{\hat{\gamma}_i-\gamma_i} \left(s + \frac{s(s-1)}{2}\right)
\le \frac{s(s+1) \abs{\hat{\gamma}_i-\gamma_i}}{2}
\le \frac{s(s+1) \Delta_i}{\hat{c}_i^{s_i}}.
\end{eqnarray*}
%s \abs{\hat{\gamma}_i-\gamma_i} + o(\hat{\gamma}_i-\gamma_i)$
%since $\abs{(\hat{\gamma}_i)^{s-1}-(\gamma_i)^{s-1}} \le 1$.  The
%lemma then follows immediately from the previous lemma.
\end{proof}

%We next bound the error in $\hat{e}_i$:

%\begin{lemma}
%Assuming Equation~(\ref{eqn:learningbounds_assumption}) holds,
%then for each $i$ we have
%\begin{eqnarray*}
%\abs{\hat{e}_i-e_i} = O\left(\frac{\Delta_i
%s_i}{(\gamma_i)^{2s_i}}\right).
%\end{eqnarray*}
%\end{lemma}
%
%\begin{proof}
%\begin{eqnarray*}
%\abs{\hat{e}_i-e_i} &=& \abs{\frac{\hat{c}_i^{s_i}}{(\hat{\gamma}_i)^{s_i-1}} - \frac{c_i^{s_i}}{(\gamma_i)^{s_i-1}}} \\
%  &=& \frac{\abs{\hat{c}_i^{s_i} (\gamma_i)^{s_i-1} - c_i^{s_i}(\hat{\gamma}_i)^{s_i-1}}}{(\hat{\gamma}_i)^{s_i-1}(\gamma_i)^{s_i-1}} \\
%  &\le& \frac{c_i^{s_i}\abs{(\hat{\gamma}_i)^{s_i-1}-(\gamma_i)^{s_i-1}} + (\gamma_i)^{s_i-1}\abs{\hat{c}_i^{s_i}-c_i^{s_i}}}{(\hat{\gamma}_i)^{s_i-1}(\gamma_i)^{s_i-1}} \\
%  &\le& \frac{c_i^{s_i}O\left(\frac{(s_i-1)\Delta_i}{c_i^{s_i}}\right) + (\gamma_i)^{s_i-1}\Delta_i}{(\hat{\gamma}_i)^{s_i-1}(\gamma_i)^{s_i-1}} \\
%  &=& O\left(\frac{\Delta_i s_i}{(\gamma_i)^{2s_i}}\right).
%\end{eqnarray*}
%\end{proof}

With these lemmas, we can prove
Theorem~\ref{thm:learningbounds_constratio}.  For each $i$ and $s$,
\begin{eqnarray*}
    \abs{\hat{c}_i^s-c_i^s} %
&=& \abs{(\hat{\gamma}_i)^{s-s_i}\hat{c}_i^{s_i} - (\gamma_i)^{s-s_i}c_i^{s_i}} \\
&=& \abs{\left((\hat{\gamma}_i)^{s-s_i} - (\gamma_i)^{s-s_i}\right)\hat{c}_i^{s_i} + (\gamma_i)^{s-s_i}\left(\hat{c}_i^{s_i} - c_i^{s_i}\right)} \\
&\le& \abs{(\hat{\gamma}_i)^{s-s_i} - (\gamma_i)^{s-s_i}}\hat{c}_i^{s_i} + (\gamma_i)^{s-s_i}\abs{\hat{c}_i^{s_i} - c_i^{s_i}} \\
&\le& \left((s-s_i)^2+(s-s_i)\right) \Delta_i + (\gamma_i)^{s-s_i} \Delta_i \\
&\le& \Delta_i \left(s^2 + s + s_i^2 + (\gamma_i)^{s-s_i}\right).
%  &=& O\left(e_i \abs{(\hat{\gamma}_i)^{s-1}-(\gamma_i)^{s-1}}\right) + O\left((\gamma_i)^{s-1}\abs{\hat{e}_i-e_i}\right) \\
%  &=& O\left(\frac{e_i s \Delta_i}{c_i^{s_i}}\right) + O\left(\frac{\Delta_i s_i}{(\gamma_i)^{2s_i}}\right) \\
%  &=& O\left(\left(\frac{s}{(\gamma_i)^{s_i}} + \frac{s_i}{(\gamma_i)^{2s_i}}\right) \Delta_i\right) \\
%  &=& O\left(\frac{K \Delta_i}{(\gamma_i)^{2s_i}} \right) \\
%  &=& O\left(\frac{K}{(\gamma_i)^{2s_i}} \sqrt{\frac{\ln \frac{1}{\delta}}{n_{i,s_i}}} \right). %
\end{eqnarray*}
By the previous lemma,
$$
(\gamma_i)^{s-s_i} \le (\hat{\gamma}_i)^{s-s_i} +
\frac{((s-s_i)^2+(s-s_i))\Delta_i}{\hat{c}_i^{s_i}} \le
(\hat{\gamma}_i)^{s-s_i} + \frac{s^2 + s + s_i^2 \Delta_i}{\hat{c}_i^{s_i}},
$$
and we obtain
$$
\abs{\hat{c}_i^s-c_i^s} \le \Delta_i \left(s^2 + s + s_i^2 +
(\hat{\gamma}_i)^{s-s_i} + \frac{(s^2 + s + s_i^2)
\Delta_i}{\hat{c}_i^{s_i}}\right).
$$

A simple application of the union bound results in
Theorem~\ref{thm:learningbounds_constratio}.

%%\subsection{Proof of Lemma~\ref{L:eff_ctr_bnd}}
%\[
%\begin{split}
%c_i^{'s} - \hat{c}_i^{'s} &= (1 - r_{s-1} - r_{s}) c_{i}^{s} + r_{s-1} c_{i}^{s-1} + r_{s} c_{i}^{s+1} - \hat{c}_i^{'s} \geq\\
%&\geq (1 - r_{s-1} - r_{s}) (\hat{c}_{i}^{s} - \epsilon) + r_{s-1} (\hat{c}_{i}^{s-1}-\epsilon) + r_{s} (\hat{c}_{i}^{s+1}-\epsilon) - \hat{c}_i^{'s} = -\epsilon.
%\end{split}
%\]
%Thus, \(c_i^{'s} \geq \hat{c}_i^{'s} - \epsilon\).
%\[
%\begin{split}
%c_i^{'s} - \hat{c}_i^{'s} &= (1 - r_{s-1} - r_{s}) c_{i}^{s} + r_{s-1} c_{i}^{s-1} + r_{s} c_{i}^{s+1} - \hat{c}_i^{'s} \leq\\
%&\leq (1 - r_{s-1} - r_{s}) (\hat{c}_{i}^{s} + \epsilon) + r_{s-1} (\hat{c}_{i}^{s-1}+\epsilon) + r_{s} (\hat{c}_{i}^{s+1}+\epsilon) - \hat{c}_i^{'s} =\epsilon.
%\end{split}
%\]
%Thus, \(c_i^{'s} \leq \hat{c}_i^{'s} + \epsilon\).
%Combining the two bounds gives the result.
\ifnum\CONTEXT=1
\subsection{Dealing with Continuous Context Information}
\label{A:context}

\ifnum\EXTENDED=0
As we mentioned, a keyword entered by a user is just one (although, for our purposes, perhaps the most important one) of many characteristics of the context in which advertisements are displayed.
While our approach is directly applicable when context has a finite domain and a user is allowed to submit separate bids for each context, it is not clear whether we can extend all of our results in general when context contains features with continuous (or very large) domains and upon which bids cannot be conditioned.\footnote{For example, since a context is realized only instantaneously (i.e., for a particular impression), there would be no possibility of changing bids to adapt to the particular context.}
Since the presence of such features is quite common, we will now partially generalize some of our results.
However, we will be unable to say much as yet in a setting as general as the one above.

For the remainder of the discussion, we will focus on the subspace of continuous features upon which the advertisers cannot condition their bids.
We denote this context by $x$ and let $X$ be the set of all possible contexts that can arise.
We assume that the only effect that a particular context $x$ has is on the click-through-rates and, consequently, make these functions of context for all slots and players.
Thus, $c_a^s(x)$ denotes the click-through-rate of player $a$ in slot $s$ when context is realized to $x$.
Suppose that advertisers are ranked on the search engine based on their bids $b_a(x)$ multiplied by some weight $w_a$, which is a function of their \emph{relevance} to the keyword entered, $e_a(x)$.
Thus, we say that $w_a(x) = w_a(e_a(x))$.
We let $e_a(x) = \sum_{s=1}^K c_a^s(x)/c_s(x)$, where $c_s(x)$ is some normalization for the particular slot $s$.
Given the particular ranking of advertisers, an advertiser $a$ will pay some price, $p_a^s(x)$ for appearing in (or switching to) slot $s$.

Since we assume that advertisers cannot condition their bids on the context, we take their bids to be scalar and denoted the bid of player $a$ by $b_a$.
We let $b$ indicate the entire profile of advertiser bids and $b_{-a}$ the profile of bids of all players other than $a$.
The expected utility of the advertiser $a$ is
\begin{equation}
\label{E:exp_u}
\begin{split}
U_a(b) = E_{x\sim D}u_a(x,b) &= E_{x \sim D}[c_a(x,b)(v_a - p_a(x,b))] =\\
&= v_aE_{x \sim D}[c_a(x,b) - E_{x \sim D}[c_a(x,b)p_a(x,b)],
\end{split}
\end{equation}
where $c_a(x,b)$ is the CTR of player $a$ under context $x$ given the ranking induced by $w_a(x)$ and the configuration of all bids $b$, and, similarly, $p_a(x,b)$ is the price per click paid by $a$ under $x$ given bids $b$ and the induced ranking.

Now, suppose that we have a (dominant strategy) Nash equilibrium bid configuration $b^*$ for every possible realization of context $c_a^s$.
Clearly, when the CTRs are conditional on context, equilibrium status of $b^*$ is not affected in this case.
For example, VCG~\cite{Mascolell95} possesses this property, as does the ladder pricing scheme~\cite{aggarwal06}; both induce truthful bidding (i.e., $b^* = v$) for any realization of click-through-rates.

It is easy to see that context changes nothing in terms of maintaining equilibria during exploration: our scheme above can be applied directly.
What it complicates is the analysis of bounds on the incentives to deviate of omniscient advertisers as well as the analysis of revenue loss due to exploration.
We now address these questions to a limited degree.
\fi

\subsubsection{Bound on Incentives of ``Omniscient'' Advertisers}

\begin{lemma}
\label{L:max_bnd}
Let $Y$ be some subset of a Euclidean space and let $f:Y\rightarrow \R$ and $g:Y\rightarrow \R$ be two functions such that $\|f - g\|_{\infty} \leq \gamma$.
Suppose $y^* = \arg\max_{y \in Y}f(x)$.
Then $|\max_{y \in Y} g(y) - g(y^*)| \leq 2\gamma$.
\end{lemma}
The proof of this is straightforward and we thus omit it.

Fix $b_{-a}$ (e.g., to equilibrium $b_{-a}^*$).
To simplify notation, we will remove $b_{-a}$ from expressions below and leave only the response of bidder $a$, $b_a$.

Now, recall that $x$ denotes context and $X$ the space of all possible context realizations.
Suppose we set $r_1(x,b_a)$ and $\alpha_i$ for all slots to be exploration parameters as described above.
During exploration, the prices $p_a(x)$ will remain as before; thus, only the effective click-through-rates will change.
We let $c_a'(x,b_a)$ be the effective CTR of player $a$ during exploration and let $\hat{C}_a^s = E_{x \sim D}[\hat{c}_a^s(x)]$ and $C_a^s = E_{x \sim D}[c_a^s(x)]$.
Let $\bar{r} = \max_{x \in X, b\in \R}r_1(x,b_a)$ and $\bar{\alpha} = \max_{s}\alpha_s$.
Finally, let $\bar{c} = \sup_{x,a,s,b_a}c_a^s(x,b_a) \leq 1$, since CTR is just the probability of a click and therefore cannot exceed 1.
We define the expected utility of a player $a$ during exploration as
\begin{equation}
U_a'(b) = E_{x \sim D}[c_a'(x,b_a)(v_a - p_a(x,b_a))]
\end{equation}
\begin{lemma}
\label{L:unif_bnd}
Suppose for player $a$, $|\hat{C}_a^s - C_a^s| \leq \epsilon$ for all $s$ and suppose that $E[p_a(x,b_a)] \leq \bar{p}$ uniformly on $b_a \in \R$. Then $\|U_a - U_a'\|_{\infty} \leq 2\bar{r}\bar{\alpha}(v_a\hat{C}_a^1 + \bar{p} + \epsilon)$ uniformly on $b_a \in \R$.
\end{lemma}
\begin{proof}
We will show the uniform bound by bounding the greatest utility loss and gain at any point $b \in \R$.
Take advertiser $a$, some $b \in \R$ and let $X = X^1 \cup \cdots \cup X^K$ be a partition of $X$ into subsets such that for all $x \in X^s$ player $a$ gets slot $s$.
Then
\[
E_x[c_a(x,b_a)p_a(x,b_a)] = \sum_{s=1}^K\int_{X^s}c_a^s(x,b_a)p_a(x,b_a)dF(x)
\]
and
\[
\begin{split}
E_x&[c_a'(x,b_a)p_a(x,b_a)] = \sum_{s=1}^K\int_{X^s}c_a^{'s}(x,b_a)p_a(x,b_a)dF(x) =\\
&= \sum_{s=1}^K\int_{X^s}([1 - r_{s-k}(x,b_a) - r_s(x,b_a)]c_a^s(x,b_a) +\\
& \quad\quad\quad\quad+ r_{s-k}c_a^{s-k}(x,b_a) + r_{s}c_a^{s+k}(x,b_a))p_a(x,b_a)dF(x)=\\
&= E_x[c_a(x)p_a(x)] + \sum_{s=1}^K\int_{X^s}r_{s-k}(x,b_a)(c_a^{s-k}(x,b_a) - c_a^s(x,b_a))p_a(x,b_a)dF(x) -\\
&\quad\quad\quad\quad- \sum_{s=1}^K\int_{X^s}r_{s}(x,b_a)(c_a^{s}(x,b_a) - c_a^{s+k}(x,b_a))p_a(x,b_a)dF(x) \leq\\
&\leq E_x[c_a(x,b_a)p_a(x,b_a)] + \bar{r}\bar{\alpha}\sum_{s=1}^K\int_{X^s}c_a^{s-k}(x,b_a)p_a(x,b_a)dF(x) \leq\\
&\leq E_x[c_a(x,b_a)p_a(x,b_a)] + \bar{r}\bar{\alpha}E[p_a(x,b_a)] \leq E_x[c_a(x,b_a)p_a(x,b_a)] + \bar{r}\bar{\alpha}\bar{p}\leq\\
&\leq E_x[c_a(x,b_a)p_a(x,b_a)] + 2\bar{r}\bar{\alpha}\bar{p}.
\end{split}
\]
Alternatively,
\[
\begin{split}
E_x&[c_a'(x,b_a)p_a(x,b_a)] = \sum_{s=1}^K\int_{X^s}c_a^{'s}(x,b_a)p_a(x,b_a)dF(x) =\\
&= \sum_{s=1}^K\int_{X^s}([1 - r_{s-k}(x,b_a) - r_s(x,b_a)]c_a^s(x,b_a) +\\
& \quad\quad\quad\quad+ r_{s-k}c_a^{s-k}(x,b_a) + r_{s}c_a^{s+k}(x,b_a))p_a(x,b_a)dF(x)=\\
&= E_x[c_a(x)p_a(x)] + \sum_{s=1}^K\int_{X^s}r_{s-k}(x,b_a)(c_a^{s-k}(x,b_a) - c_a^s(x,b_a))p_a(x,b_a)dF(x) -\\
&\quad\quad\quad\quad- \sum_{s=1}^K\int_{X^s}r_{s}(x,b_a)(c_a^{s}(x,b_a) - c_a^{s+k}(x,b_a))p_a(x,b_a)dF(x) \geq\\
&\geq E_x[c_a(x,b_a)p_a(x,b_a)] - 2\bar{r}\bar{\alpha}\sum_{s=1}^K\int_{X^s}c_a^{s}(x,b_a)p_a(x,b_a)dF(x) \geq\\
&\geq E_x[c_a(x,b_a)p_a(x,b_a)] - 2\bar{r}\bar{\alpha}\bar{p}.
\end{split}
\]
Similarly,
\[
v_aE_x[c_a(x,b_a)] - 2\bar{r}\bar{\alpha}E[c_a^1(x)] \leq v_aE_x[c_a'(x,b_a)] \leq v_aE_x[c_a(x,b_a)] + 2\bar{r}\bar{\alpha}E[c_a^1(x)].
\]
Consequently,
\[
\begin{split}
U_a(b) - U_a'(b)  &\geq v_aE_x[c_a(x,b_a)] - E_x[c_a(x)p_a(x)] -  v_aE_x[c_a(x,b_a)] - 2\bar{r}\bar{\alpha}\bar{c} +\\
&\quad\quad\quad+ E_x[c_a(x,b_a)p_a(x,b_a)] - 2\bar{r}\bar{\alpha}\bar{c}\bar{p}\geq\\
&\geq -2\bar{r}\bar{\alpha}(v_aE[c_a^1(x)] + \bar{p})
\end{split}
\]
and
\[
\begin{split}
U_a(b) - U_a'(b)  &\leq v_aE_x[c_a(x,b_a)] - E_x[c_a(x)p_a(x)] -  v_aE_x[c_a(x,b_a)] + 2\bar{r}\bar{\alpha}\bar{c} +\\
&\quad\quad\quad+ E_x[c_a(x,b_a)p_a(x,b_a)] + 2\bar{r}\bar{\alpha}\bar{c}\bar{p}\leq\\
&\geq 2\bar{r}\bar{\alpha}\bar{c}(v_aE[c_a^1(x)] + \bar{p}).
\end{split}
\]
Thus,
\[
|U_a(b) - U_a'(b)| \leq 2\bar{r}\bar{\alpha}(v_aE[c_a^1(x)] + \bar{p}) \leq 2\bar{r}\bar{\alpha}(v_aE[\hat{c}_a^1(x)] + \bar{p} + \epsilon)
\]
Since this bound is independent of $b_a$, it is uniform on $b_a \in \R$.
\end{proof}

\begin{theorem}
\label{TA:dev_bnd}
Suppose $|\hat{C}_a^s - C_a^s| \leq \epsilon$ for all $a,s$.
Furthermore, suppose that $E[p_a(x,b_a)] \leq \bar{p}$ uniformly on $b_a \in \R$ and the players are omniscient.
Then any player will gain at most $\bar{r}\bar{\alpha}(v_a\hat{C}_a^1 + \bar{p})$ by deviating from a pre-exploration equilibrium.
\end{theorem}
\begin{proof}
Apply Lemma~\ref{L:unif_bnd} and then Lemma~\ref{L:max_bnd}.
\end{proof}

\begin{example}
The generalized second-price auction price has a finite upper bound for a fixed set of other players' bids as long as $E_x[\frac{\max_{t \neq a}w_{t}}{w_a(x)}] < \infty$ for all $a$:
\[
p_a^s(b_a,b_{-a}) \leq E_x[\frac{\max_{t \neq a}b_{t}w_{t}(x)}{w_a(x)}] \leq \max_{t\neq a}b_tE_x[\max_{t \neq a}\frac{w_{t}(x)}{w_a(x)}].
\]
Since $b_{-a}$ is fixed, this is finite if the expected weight ratio is finite uniformly on $b_a$.
\end{example}

\subsubsection{Bound on Expected Revenue Loss Due to Exploration}

\begin{theorem}
Suppose that the players maintain their equilibrium bids $b^*$ during exploration.
Then revenue loss due to exploration is bounded by
\[
2\bar{r}\bar{\alpha}\sum_{a=1}^{N}E_{x\sim D}[p_a(x,b^*)].
\]
\end{theorem}
\begin{proof}
Let $\phi(s)(x,b^*)$ denote the player that receives slot $s$ when context is $x$ and let us partition the context space as $X = X_1^s \cup \cdot \cup X_N^s$, where $X_a^s$ is the set of realizations of $x$ such that advertiser $a$ gets slot $s$.
Then
\[
\begin{split}
\Delta_{Rev} &= \sum_{s=1}^KE_x[p_{\phi(s)(x,b^*)}^s(x,b^*)(c_{\phi(s)(x,b^*)}^s(x,b^*) - c_{\phi(s)(x,b^*)}^{'s}(x,b^*))] = \\
&=\sum_{s=1}^KE_x[p_{\phi(s)(x,b^*)}^s(x,b^*)r_{s}(c_{\phi(s)(x,b^*)}^s(x,b^*) - c_{\phi(s)(x,b^*)}^{s+k}(x,b^*)) -\\
&\quad\quad\quad\quad - r_{s-k}(c_{\phi(s)(x,b^*)}^{s-k}(x,b^*) - c_{\phi(s)(x,b^*)}^{s}(x,b^*))] \leq\\
&\leq \sum_{s=1}^KE_x[p_{\phi(s)(x,b^*)}^s(x,b^*)(r_{s}c_{\phi(s)(x,b^*)}^s(x,b^*) + r_{s-k}c_{\phi(s)(x,b^*)}^{s}(x,b^*))] \leq\\
&\leq 2\bar{r}\bar{\alpha}\sum_{s=1}^KE_x[p_{\phi(s)(x,b^*)}^s(x,b^*)c_{\phi(s)(x,b^*)}^s(x,b^*)] \leq\\
&\leq 2\bar{r}\bar{\alpha}\sum_{s=1}^KE_x[p_{\phi(s)(x,b^*)}^s(x,b^*)] =\\
&= 2\bar{r}\bar{\alpha}\sum_{s=1}^K\sum_{a=1}^N\int_{X_a^s}p_a^s(x,b^*)dF(x) = 2\bar{r}\bar{\alpha}\sum_{a=1}^N\sum_{s=1}^K\int_{X_a^s}p_a^s(x,b^*)dF(x) =\\
&= 2\bar{r}\bar{\alpha}\sum_{a=1}^NE_x[p_a(x,b^*)].
\end{split}
\]
\end{proof}
\fi
\fi

\end{document}
