Some notation conventions:


1. Probability:
  
   use \Ex{ } for the expectation
       \Pr{ } for the probability
   these two macros will be defined afterwards for the whole book





2. Numbers:


%
% REAL
%
\newcommand{\REAL}{\ensuremath{\mathbb{R}}}

%
% NATURAL NUMBERS
%
\newcommand{\NAT}{\ensuremath{\mathbb{N}}}
\newcommand{\NATURAL}{\NAT}

%
% RATIONAL NUMBERS
%
\newcommand{\RATIONAL}{\ensuremath{\mathbb{Q}}}
\newcommand{\RR}{\ensuremath{\mathbb{R}}}


% asymptotic Notation
 
 \newcommand{\whpO}[1]{\tilde{\mathrm{O}}\left( #1\right)}
 \newcommand{\Oschlange}{$\tilde{\mathrm{O}}$}
 \newcommand{\Ohh}[1]{\mathcal{O}\!\left( #1\right)}
 \newcommand{\Oh}[1]{\mathcal{O}\!\left( #1\right)} 
 \renewcommand{\Oh}[1]{O\left( #1\right)}
 \newcommand{\oh}[1]{\mathrm{o}\!\left( #1\right)}
 \newcommand{\Th}[1]{\Theta\!\left( #1\right)}
 \newcommand{\Om}[1]{\Omega\!\left( #1\right)}
 \newcommand{\om}[1]{\omega\!\left( #1\right)}
 \newcommand{\Oleq}{\preceq}






3. Complexity classes:

\def \pc   {{\sf P}}                              %%% P complexity class
\def \npc  {{\sf NP}}                             %%% NP complexity class
\def \ncc  {{\sf NC}}                             %%% NC complexity class
\def \qpc  {{\sf DTIME}(n^{O({\sf polylog}(n))})} %%% QusiPoly complexity class
\def \snp  {{\sf Max SNP}}                        %%% Max SNP complexity class
\def \apxc {{\sf APX}}                            %%% Max SNP complexity class
\def \ptas {{\sf PTAS}~}
\def \fptas {{\sf FPTAS}~}
\def \pras {{\sf PRAS}}                           %%% Polynomial time radnomized approx scheme 
\def \fpras {{\sf FPRAS}}                         %%% Fully polynomial 
                                                  %%% time radnomized approx scheme




4. Some graph theory:
    
   $G=(V,E)$ - (un)directed graph
   $|V|, |E|$ - cerdinality of $V$, $E$
   $u, v, u_1, v_2 \in V$ - vertices
   $e, f, e_2 \in E$ - edges, arcs
   $(u,v) \in E$ - edge or arc between vertices $u$ and $v$
   $P$ - a path in $G$





5. Notation for mechanism design (probably also relavant in other parts of 
   the book):

   ${\cal M} = (g,p)$ - a mechanism, with $g$ - assignment, $p$ - payment
   Auctioneer, and NOT seller  
   $K$ - commodities or goods to sell, $|K| = k$, $m_j$ = multiplicity of 
         good $j \in K$
   $N = \{1,2, \ldots, n\}$ - the set of agents
   $d$ - vector of declarations from agents
   $g_i(d)$ - assignment (of goods) to agent $i$, under $d$
   $p_i(d)$ - payment to agent $i$ under $d$
   $v_i(a,t)$ - valuation of agent $i$ under assignment $a = g_i(d)$,
                and (true) type $t$ (of agent $i$)
   $u_i = p_i(d) + v_i(a, t)$ - utility
   $\sum_{i} v_i$ = social welfare, where $v_i = v_i(a,t)$
   $\sum_{i} p_i(d)$ = revenue





6. Labels of theorems, lemmas, ... etc.:

   Each group uses its symbol in lower-case letters at the beginning of 
   the label.
   
   Example: The group "B2" on Combinatorial auctions uses
            \label{b2theorem1}.





7. Citing the literature:

   Each group prepares its own bibtex file.
   Please use the following macros: 


Example of use:

booktitle = PROC # { 28th } # ICALP,
journal   = JACM,

---Macros-----

@String{PROC = {Proc.}}

@String{LNCS = {Lecture Notes in Comput. Sci.}}

@String{APPROX = {Int.\ Workshop on Approximation Algorithms
                  for Combinatorial Optimization (APPROX)}}
@String{CPM =  {Ann. Symp. on Combinatorical Pattern Matching}}
@String{ESA =  {Ann. European Symp. on Algorithms (ESA)}}
@String{FOCS = {Ann. IEEE Symp. on Foundations of Comput. Sci. (FOCS)}}
@String{ICALP = {Int. EATCS Coll.  on Automata, Languages and 
                 Programming (ICALP)}}
@String{IPCO = {Int. Integer Programming and Combinatorial
                Optimization Conf. (IPCO)}}
@String{ISAAC = {Ann. Int. Symp. on Algorithms and Computation (ISAAC)}}
@String{SODA = {Ann. ACM--SIAM Symp. on Discrete Algorithms (SODA)}}
@String{STACS = {Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS)}}
@String{STOC = {Ann. ACM. Symp. on Theory of Comput. (STOC)}}
@String{SWAT = {Scandinavian Workshop on Algorithm Theory (SWAT)}}
@String{WADS = {Int. Workshop on Algorithms and Data Structures (WADS)}}
@String{WG = {Int.\ Workshop on Graph Theoretic Concepts
              in Computer Science (WG)}}

@String{IC   = {Information and Computation}}
@String{IPL  = {Inform. Proc. Letters}}
@String{JACM = {J. ACM}}
@String{JALG = {J. Algorithms}}
@String{JCSS = {J. Comput. Syst. Sci}}
@String{MOR  = {Math. Operations Research}}
@String{NETW = {Networks}}
@String{OR   = {Operations Research}}
@String{SICOMP = {SIAM J. Comput}}
@String{SIDMA = {SIAM J. Disc. Math.}}
@String{TCS  = {Theoret. Comput. Sci}}


@String{TSCI = {Transportation Science}}
@String{TAER   = {The American Economic Review}}
@String{ECON   = {Econometrica}}
@String{BELLJ   = {The Bell J. of Economics}}
@String{TAD   =  {Theory and Decision}}
@String{MNGS   = {Management Science}}
@String{IJGT   = {Int. Journal of Game Theory}}
@String{GEB   =  {Games and Economic Behavior}}
@String{RES   = {The Review of Economic Studies}}
@String{RANDJ   = {The RAND Journal of Economics}}
@String{QJE   = {The Quarterly Journal of Economics}}
@String{IGTR   = {Int. Game Theory Review}}

---End of Macros-----