\documentclass[11pt]{article}
\setlength{\parindent}{0pt} % don't indent paragraphs
\setlength{\parskip}{\baselineskip}
% borrowed from http://www.cs.cornell.edu/courses/Cs6840/2012sp/

%%% PACKAGES %%%%%
\usepackage[T1]{fontenc}
\usepackage{epic}
\usepackage{eepic}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{marvosym}
\usepackage{amsmath, amsthm, amssymb, upgreek}
\usepackage{fancyhdr, lastpage}
\usepackage{fullpage} \usepackage{epsfig}
\usepackage{pgf,tikz}
\usepackage{setspace}
\usetikzlibrary{arrows}

\usepackage{amsfonts, multicol, tabularx,mathtools, hyperref, float, url,
  lmodern, microtype}

%%% MACROS %%%
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\newsavebox{\spacebox}
%/aspace = visible space (for TM), %\mytilde = ~
\begin{lrbox}{\spacebox}
\verb*! !
\end{lrbox}
\newcommand{\aspace}{\usebox{\spacebox}\hspace{0.1cm}}%
\newcommand{\mytilde}{\raise.17ex\hbox{$\scriptstyle\mathtt{\sim}$}}

% \p = \frac{}{}, \br = {}, \an = <>, \bp = \left{\right}, \bs =
% square bracket. \ds = \displaystyle. \bra, \ket, \bracket - self explanatory
% \norm: |blah| \set: \{ blah \}.
% \mat, pmat, bmat, sm, psm: matrices
% \ubar, \obar, \ub{blah}{under_blah}

\newcommand\p[2]{\frac{#1}{#2}}
\newcommand\br[1]{\lbrace #1 \rbrace}
\newcommand\an[1]{\langle #1 \rangle}
\newcommand\bp[1]{\left (#1 \right)}
\newcommand\bs[1]{\left [#1 \right]}
\newcommand\ds\displaystyle
\newcommand\ket[1]{\left|#1\right\rangle}
\newcommand\bra[1]{\left\langle#1\right|}
\newcommand\braket[1]{\left\langle#1\right\rangle}
\newcommand{\norm}[1]{\left\|#1\right\|}
\newcommand{\set}[1]{\left\{#1\right\}}

\newcommand\mat[1]{\begin{matrix}#1\end{matrix}}
\newcommand\pmat[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand\bmat[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand\sm[1]{\begin{smallmatrix}#1\end{smallmatrix}}
\newcommand\psm[1]{\bp{\begin{smallmatrix}#1\end{smallmatrix}}}
\newcommand\bsm[1]{\bs{\begin{smallmatrix}#1\end{smallmatrix}}}

\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\ubar}[1]{\underline{#1}}
\newcommand{\ub}[2]{\underbrace{#1}_{#2}}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
\newcommand{\fig}[3]{
			\vspace{#2}
			\begin{center}
			Figure #1:~#3
			\end{center}
	}

%%%%%% USEFUL COMMANDS TO REMEMBER %%%%%%%%
% \boxed{}, \binom{}{},

%single-line equation, underbrace
%\[ \underbrace{\text{reminder of underbrace}}_{b} \biggr|_0^1 \]

% multi-line equations
%\begin{align*} x^2 + y^2 &= 1	\\ y &= \sqrt{1 - x^2}. \end{align*}

%multi-line proof
%\begin{align*} x^2 + y^2 &= 1	& \text{because i said so} \\ y &= \sqrt{1 - x^2} & \text{because no particular reason} \end{align*}

%simultaneous equations
%\[ f(x,y,z) = \begin{cases} 3x + 5y + z & \quad \text{case 1}\\ 7x + 2y + 4z & \quad \text{case 2} \end{cases} \]

%top above bottom: \stackrel{top}{bottom}
%stack below \sums: \substack{x > y\\ x > z}

% DEFINES
\theoremstyle{definition}
\newtheorem{lemma}{Lemma}
\newtheorem*{lem}{Lemma}
\newtheorem*{problem}{Problem}
\newcommand{\solution}{\noindent {\bf Solution.}}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}
\newtheorem*{remark}{Remark}
\newtheorem{observation}{Observation}
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{axiom}[lemma]{Axiom}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{proposition}[lemma]{Proposition}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Arg}{\operatorname{Arg}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\I}{\mathbb{I}}

% Header/first page box
%args: Classname, Year/semester, Title, Instructor, Name
\newcommand{\heading}[5]{
   \noindent
   \begin{center}
   \framebox[\textwidth]{
     \begin{minipage}{0.9\textwidth} \onehalfspacing
       {#1 (\pageref{LastPage} pages)} \hfill #2

       {\centering \Large #3

       }\medskip

       {\it Instructor:#4 \hfill }
       {#5}
     \end{minipage}
   }
   \end{center}
\thispagestyle{empty}
\pagestyle{fancy} \lhead{
} \chead{#1 - #3 (page \thepage\ of \pageref{LastPage})}
\rhead{}
\cfoot{ }
\setlength{\headheight}{20pt}
\setlength{\headsep}{20pt}
}

%%%%% DOCUMENT SPECIFIC %%%%
\DeclareMathOperator{\OPT}{OPT}
\DeclareMathOperator{\SW}{SW}
\DeclareMathOperator{\argmax}{argmax}
\DeclareMathOperator{\E}{\mathbb E}
\allowdisplaybreaks
\usepackage{enumitem}

\begin{document}
%args: Classname, Year/semester, Title, Instructor, Name
\heading{CS6840 - Algorithmic Game Theory}{Spring 2014}{March 14 - Smoothness in
Auction Games}{Eva Tardos}{Chris Liu(cl587)}

\textbf{Reminder: }

Last few lectures: Single item auctions, full information \& Bayesian.
General mechanism - VCG. (Truthful bidding is dominant)

Next few lectures: Make statements about outcomes in auctions without strenuous calculus using
smoothness framework.

\textbf{Smooth auctions: }

Set up:
\begin{itemize}[noitemsep,topsep=-5pt]
  \item Outcome $a \in \Omega$
  \item Payment $p_i$ for player $i$
  \item Value $v_i(a)$ for each outcome
  \item Utility (quasi-linear) $u_i(a,p_i) = v_i(a) - p_i$
  \item Strategy space $S_i$ for player $i$
  \item  $s = (s_1,\ldots,s_n)$ a vector of
    strategies.
  \item Outcome function $o$: $S_1 \times \ldots \times S_n \mapsto \Omega$
  \item Payment functions $p_i$: $S_1 \times \ldots \times S_n  \mapsto \R$
\end{itemize}
Remarks: The strategy $s_i$ should be thought of as a set of bids for player $i$ on outcomes, often their willingness to pay.
Previous notation for bids that are such ''willingness to pay'' was $b_i$.

Notation: Let $o(s)$ be the outcome function.
Payment, value, utility functions may be written as
$p_i(s), v_i(o(s)), u_i(o(s),p_i(s))$, respectively. The rest of the notes will
write $v_i(s)$ to mean  $v_i(o(s))$ and $u_i(s)$
to mean  $u_i(o(s),p_i(s))$ when a mechanism (a tuple of outcome and payment functions) is given.

Example:

1. VCG - outcome: $\argmax_a \sum_i b_i(a)$.

2. First price auction - outcome: $\argmax_i b_i$. payment: $p_i = b_i$ if $i
= \argmax_i b_i$, 0 otherwise.

Approach: Let's see where we get using utility smoothness. Then we will define a
new notion of smoothness for auction games.

\textbf{Smoothness, utility maximization games:}
%Approach: Define a new notion of smoothness, and compare it to the old notion.

Recall that a utility game is $(\lambda, \mu)$ smooth if $\exists s^*$ s.t $\forall s$ $\sum_i u_i(s_i^*,s_{-i}) \geq \lambda
\OPT - \mu \SW(s)$.
%\sum_i u_i(s^*) + \mu u_i(s)$

Remarks:
\begin{itemize}[topsep=0pt]
  \item We will regard this as utility smoothness for the rest of these notes.

\item $\OPT= \max_s \sum_i v_i(s)$.
   Note that $\SW(s^*)$ is not required to be equal to $\OPT$.

\item $\SW(s) = \sum_i u_i(s)$, where $u_i(s) = v_i(s) - p_i(s)$
\end{itemize}


It is useful to see how this translates to an auction game. In an auction, the
auctioneer is a player with a fixed strategy: to collect the money. His/her
utility may be written as $u_{\text{auctioneer}}(s) = \sum_i p_i(s)$. We add the
auctioneer as a player to the utility game.

Translating utility smoothness inequality directly, this is
\[
  \sum_i u_i(s^*_i, s_{-i}) + \ub{\bp{\sum_i p_i(s)}}{\text{auctioneer ``deviating''}}
  \geq \lambda \OPT - \mu\ub{\bp{\sum_i u_i(s) + \sum_i p_i(s)}}{\text{SW}(s)}
\]
Remarks: The sum on $i$ is over all players excluding the auctioneer.

\textbf{Smoothness, auction games:}

Now, in comparison, we define this new notion of smoothness for auction games.
(motivation in future lectures)

\definition An auction game is $(\lambda,\mu)$ smooth if $\exists s^*$ s.t $\forall
s$,
\[
  \sum_i u_i(s^*_i,s_{-i}) \geq \lambda \OPT - \mu \sum_i p_i(s)
\]
Remarks:
Sum on $i$ is over all players, excluding the auctioneer. This is not that dissimilar to utility smoothness:
Assuming $u_i \geq 0$, we can think of a
$(\lambda,\mu)$ smooth auction as $(\lambda,\mu+1)$ smooth utility game, with
the auctioneer added as a player.   In future
lectures we will see why this new definition of smoothness for auction games is natural.

\theorem An auction is $(\lambda,\mu)$ smooth implies a Nash equilibrium
strategy profile $s$ satisfies
$\SW(s) \geq \p{\lambda}{\max\{1,\mu\}}\OPT$

\proof

Let $s$ be Nash strategy profile, and $s^*$ a strategy profile that satisfies smoothness requirements.

Because $s$ is Nash, $u_i(s) \geq u_i(s_i^*,s_{-i})$. Summing over all players:
\begin{align*}
  \text{SW}(s) &\geq \sum_i u_i(s_i^*,s_{-i}) + \sum_i p_i(s)\\
  \sum_i \bp{u_i(s) + p_i(s)} &\geq \sum_i u_i(s_i^*,s_{-i}) + \sum_i p_i(s)\\
  \sum_i \bp{u_i(s) + p_i(s)} &\geq \lambda \OPT - \mu \sum_i p_i(s) + \sum_i p_i(s) \quad & \text{by
    auction smoothness}\\
  \sum_i u_i(s) + \mu \sum_i p_i(s) &\geq \lambda \OPT\\
  \max\{\mu,1\}\bp{\sum_i u_i(s) + \sum_i p_i(s)} &\geq \lambda \OPT\\
  \SW(s) &\geq \p{\lambda}{\max\{1,\mu\}}\OPT \qed
\end{align*}
Remark: Sum on $i$ is over all players excluding the auctioneer.

\textbf{Generalization to Bayesian Nash:}
In general, $s^*_i$ for player $i$ is computed with knowledge of other players' values. In a
Bayesian setting, we do not have this information. Restricting $s_i^*$ such that it only
depends on player $i$'s value
allows us to prove the following theorem:
\theorem If an auction is $(\lambda,\mu)$ smooth with an $s^*$ such that $s_i^*$ depends only on the value of player $i$, this implies that a Bayesian Nash equilibrium
satisfies $\E[\SW] \geq \p{\lambda}{\max\{1,\mu\}}\E[\OPT]$
\proof
Idea is to put expectation operator around the proof of Theorem 1.

By definition, a strategy $s(v) = (s_1(v_1),\ldots,s_n(v_n))$ is now a function (or a distribution over functions, if randomized), as each player's strategy depends on his/her own value. If such a function is a Bayesian Nash Equilibrium if $\E_{v}[u_i(s_i',s_{-i} )| v_i] \leq
\E_{v}[u_i(s) | v_i]$, for all strategies $s_i'\in S_i$, where values $v = (v_1,\ldots,v_n)$ is drawn from some distribution. Using
this for $s_i^*$, and taking also expectations over $v_i$ we get:
\begin{align*}
  \E_{v}\bs{u_i(s)} &\geq \E_{v}\bs{u_i(s_i^*,s_{-i})} \\
  \sum_i \E_v\bs{u_i(s)} &\geq \sum_i \E_v\bs{u_i(s_i^*,s_{-i})}\quad
    &\text{summing over players}\\
    \E_v \bs{\sum_i u_i(s)} &\geq \E_v \bs{\sum_i u_i(s_i^*,s_{-i})}\quad
    &\text{linearity of expectation}\\\\
  \E_v \bs{\sum_i u_i(s)} &\geq \E_v \bs{\lambda \OPT - \mu \sum_i p_i(s)} \quad
    &\text{by smoothness}\\
    \E_v\bs{\sum_i u_i(s)} +\E_v\bs{\mu \sum_i p_i(s)}&\geq \E_v\bs{\lambda \OPT}\\
    \E_v[\SW(s)] &\geq \p{\lambda}{\max\{1,\mu\}} \E_v[\OPT] \qed
\end{align*}

\textbf{Next time:}
Examples of auctions that satisfy $(\lambda,\mu)$ smoothness in this framework.

\end{document}
