\documentclass{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{fullpage}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]

\newcommand{\R}{\ensuremath{\mathbb R}} % R in blackboard font for the reals.

\title{Notes on Equilibria and Exploration with Context}

\begin{document}
\maketitle

\section{Notation and Setup}

Let $x$ denote context and $X$ be the set of all possible contexts that can arise.
Denote an advertisers by $a$ and suppose that there are $N$ advertisers.
Suppose that the search engine has $K$ slots, where a slot is denoted by $s$.
Each advertiser $a$ has a click-through-rate (CTR) associated with each slot $s$, as a function of context, $c_a^s(x)$.
We assume that for every $x$, $c_a^1(x) > c_a^2(x) > \cdots > c_a^K(x)$.
Let the estimate of CTR be denoted $\hat{c}_a^s(x)$ and let the value of advertiser $a$ per click be denoted by $v_a$.

Suppose that advertisers are ranked on the search engine based on their bids $b_a(x)$ multipled 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$.

\section{Equilibria}

\subsection{Context-Conditional Equilibria}

We first consider the less practical setting in which the bidder can submit a bit which is a function of context $x$.
In this case, we can derive the equilibrium bids, rankings, and prices in each context separately (in principle) and assign these to players, if we assume (as is typical in the static analysis without context) that the valuations of advertisers are common knowledge.

%\begin{theorem}
%Suppose that $c_a^s(x)$ is continuous in $x$ for all $a$ and $s$.
%Then there exists an equilibrium $b^*(x)$ which is continuous in $x$.
%\end{theorem}

%Example: factorable CTRs and minimum symmetric equilibrium.
%\begin{example}

%\end{example}

\subsection{Equilibria in Scalar Bids}

It may be impractical to require advertisers to submit bids which are functions of context.
Rather, advertisers may submit a single scalar bid valid for \emph{all} contexts.\footnote{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.}
Thus, the advertisers will be maximizing their \emph{expected} utility with respect to the context distribution $D$:
\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.

\begin{theorem}
Suppose that $b^*$ is a (dominant strategy/Nash) equilibrium bid configuration under any realization of $c_a^s$ for all $a,s$ given the price functions $p_a^s(c_a^1,\ldots,c_a^K)$ for every $a,s$.
Let $c_a^s(x)$ by the click-through-rates induced by realizations of context $x$.
Then $b^*$ is an (dominant strategy/ex-post) equilibrium with respect to $x$.
Particularly, $b_a^*$ maximizes expected utility in~\ref{E:exp_u} for every player $a$ given $b_{-a}^*$.
\end{theorem}
\begin{proof}
This result follows directly from the definition of dominant strategy/ex-post equilibrium.
\end{proof}
\begin{corollary}
VCG, weighted VCG, and ladder pricing schemes all induce $b^* = v$ as dominant strategy equilibrium bids.
\end{corollary}

\section{Maintaing Equilibrium During Exploration}

This is just our other paper.
Nothing changes if you compute $r_1$ based on the specific context.
Thus, you would have $r_1(x)$.

\section{Bound on Incentives to Deviate with 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 in the previous paper.
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} + 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} + 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{T:dev_bnd}
Suppose $|\hat{C}_a^s - C_a^s| \leq \epsilon$ for all $a,s$ 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}

\emph{TODO: study when pricing schemes actually have the property that the expected price of every player (for a fixed vector of other bids) is uniformly upper bounded by some finite value.}
\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 expectated weight ratio is finite uniformly on $b_a$.
\end{example}

\section{Bound on Expected Revenue with Omniscient Advertisers}

\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 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}

\end{document}
