% Partition variables
\newcommand{\clpartition}[1]{N^{#1}}
\newcommand{\assign}[1]{v_{#1}}
\newcommand{\assignc}[1]{V_{#1}}
\newcommand{\assigne}[1]{v^{#1}}
\newcommand{\clpassign}[2]{N^{#1}(\assign{#2})}
% Rough Partition
\newcommand{\parcount}[2]{n_{\rulparam{#1}{#2}}}
\newcommand{\attrpar}[2]{\mathcal{A}_{\rulparam{#1}{#2}}}
\newcommand{\attrparmp}[2]{\mathcal{A}^{m}_{\rulparam{#1}{#2}}}
\newcommand{\parvalcount}[3]{n_{\rulparam{#1}{#2}(#3)}}
\newcommand{\rulsat}[2]{\hat{n}^{#1}_{#2}}
\newcommand{\clrpartition}[2]{\hat{N}^{#1}_{#2}}
\newcommand{\clrpartitionall}[1]{\hat{N}^{#1}}
\newcommand{\clrpassign}[3]{\hat{N}^{#1}_{#2}(#3)}
\newcommand{\clrpassignp}[3]{\hat{N}_{\rulparam{#2}{#1}'}(#3)}
% Sets and functions on the partition variables
\newcommand{\classesinrule}[1]{\{\clpartition{i}\}_{\class{i}\in #1}}
\newcommand{\classesrinrule}[1]{\{\clrpartition{i}{#1}\}_{\class{i}\in #1}}
\newcommand{\countfn}[2]{\mathcal{N}_{#1}(#2)}
\newcommand{\countna}[1]{\mathcal{N}_{#1}}
% Classes, parameters, rules
\newcommand{\class}[1]{C^{#1}}
\newcommand{\classofa}[1]{CL(#1)}
\newcommand{\classof}[2]{CL_{#1}(#2)}
\newcommand{\rparams}[1]{PA(#1)}
\newcommand{\rul}{r}
\newcommand{\rulset}{\ensuremath{R}}
\newcommand{\rulparam}[2]{#1.#2}
\newcommand{\paramset}{\mathcal{\param{}}}
%\newcommand{\attr}[1]{A_{#1}}
\newcommand{\param}[1]{x_{#1}}
\newcommand{\dom}[1]{\mathcal{D}(#1)}
\newcommand{\ruleclass}[2]{\mathcal{A}^{#1}(#2)}
\newcommand{\ruleinterclass}[2]{\hat{\mathcal{A}}^{#1}(#2)}
\newcommand{\relpred}[2]{\ensuremath{#1\; REL\;#2}}
\newcommand{\eqpred}[2]{\ensuremath{#1\; =\;#2}}
% Other objects
\newcommand{\rulval}[1]{w_{#1}}
\newcommand{\numcl}{c}
\newcommand{\util}{U^{*}}
\newcommand{\bucket}[1]{B_{#1}}
% Operations and sets
\newcommand{\sat}[1]{SAT(#1)}
\newcommand{\uni}[2]{\mathcal{U}(#1,#2)}
\newcommand{\diff}[1]{\ensuremath{Diff(#1)}}
\newcommand{\illegal}[1]{\ensuremath{ILL(#1)}}
\newcommand{\rogpart}[3]{\nu^{#1}(\uni{#2}{\assign{#3}})}
\newcommand{\proj}[2]{\assign{#1}|_{#2}}
\newcommand{\ex}[2]{ex_{#1}(#2)}
\newcommand{\noteq}[1]{DF(#1)}
\newcommand{\predset}[2]{\mathcal{P}^{#2}_{#1}}
\newcommand{\predsetic}[2]{\hat{\mathcal{P}}^{#2}_{#1}}
\newcommand{\attric}[2]{\attr{}(\predsetic{#1}{#2})}


% DIRECTED UTILITY

\def\cind{\ensuremath{\mbox{CDI}_{r}}}
\newcommand{\condInd}[3]{\mbox{CDI}_{r}(#1,#2|#3)}
\newcommand{\pa}[1]{Pa(#1)}
\newcommand{\dn}[1]{Dn(#1)}
\newcommand{\co}[1]{Co(#1)}

\newcommand{\attrs}{\Gamma}
\newcommand{\attr}[1]{a_{#1}}
\newcommand{\ssattr}[1]{\gamma_{#1}}
\newcommand{\utilf}[1]{u(#1)}
\newcommand{\refassign}[1]{#1^{0}}
\newcommand{\condutilf}[2]{\refutilf{#1|#2}}
\newcommand{\refutilf}[1]{u_{r}{(#1)}}
\newcommand{\arcs}{E}

\newcommand{\prefOrder}{\ensuremath{\preceq}}
\newcommand{\prefne}{\ensuremath{\prec}}
\newcommand{\domain}{\ensuremath{\Theta}}
\newcommand{\vect}[1]{\ensuremath{\vec{\mathbf{#1}}}}

\def\net{utility difference network}
\def\netc{Utility Difference Network}
\def\procStruct{ProcGetStructure}

\def\defemb#1#2{\expandafter\def\csname #1\endcsname
  {\relax\ifmmode #2\else\hbox{$#2$}\fi}}

\defemb{cA}{{\cal A}}
\defemb{cB}{{\cal B}}
\defemb{cC}{{\cal C}}
\defemb{cD}{{\cal D}}
\defemb{cE}{{\cal E}}
\defemb{cF}{{\cal F}}
\defemb{cG}{{\cal G}}
\defemb{cI}{{\cal I}}
\defemb{cK}{{\cal K}}
\defemb{cN}{{\cal N}}
\defemb{cM}{{\cal M}}
\defemb{cP}{{\cal P}}
\defemb{cR}{{\cal R}}
\defemb{cS}{{\cal S}}
\defemb{cT}{{\cal T}}
\defemb{cV}{{\cal V}}
\defemb{cO}{{\cal O}}
\defemb{cL}{{\cal L}}
\defemb{cX}{{\cal X}}
\defemb{cU}{{\cal U}}

\defemb{bm}{{\bf m}}
\defemb{bF}{{\bf F}}
\defemb{bC}{{\bf C}}
\defemb{bc}{{\bf c}}
\defemb{bp}{{\bf p}}
\defemb{bU}{{\bf U}}
\defemb{bu}{{\bf u}}
\defemb{bV}{{\bf V}}
\defemb{bW}{{\bf W}}
\defemb{bw}{{\bf w}}
\defemb{bX}{{\bf X}}
\defemb{bx}{{\bf x}}
\defemb{bY}{{\bf Y}}
\defemb{by}{{\bf y}}
\defemb{bZ}{{\bf Z}}
\defemb{bz}{{\bf z}}


\newcommand{\ba}{\bar{a}}

\newcommand{\toadd}[1]{
  {\footnotesize
  \begin{center}
  \fbox{
    \begin{minipage}{4in}
      carmel: #1
    \end{minipage}
    }
  \end{center}
  }
}

\newcommand{\compare}{\ogreaterthan}
\newcommand{\imp}{\rhd}
\newcommand{\eqimp}{\bowtie}
\newcommand{\TCPn}{TCP-net}
\newcommand{\TCPns}{TCP-nets}
\newcommand{\UCPn}{UCP-net}
\newcommand{\UCPns}{UCP-nets}
\newcommand{\cparc}[2]{\langle \overrightarrow{#1, #2} \rangle}
\newcommand{\iarc}[2]{(\overrightarrow{#1, #2})}
\newcommand{\ciarc}[2]{(#1, #2)} \newcommand{\bpi}{{\mathbf \pi}}
\newcommand{\shared}{{\mathsf shared}}
\newcommand{\commentnow}[1]{}
\newcommand{\commentout}[1]{}
\newcommand{\reallycommentout}[1]{}
\newcommand{\prefeq}{\succeq}
\newcommand{\pref}{\succ}

\newcommand{\set}[1]{\left\{
    \begin{array}{l}#1
    \end{array}
  \right\}}

\newcommand{\sset}[2]{\left\{~#1 \left|
      \begin{array}{l}#2\end{array}
    \right.     \right\}}

\def\integer{{\mathbb Z}}
\def\nat{{\mathbb N}}

%\renewcommand{\baselinestretch}{0.96}
%\setlength{baselinestretch 0.95}

\newcommand{\ang}[1]{\langle{#1}\rangle}

\providecommand{\newoperator}[3]{\newcommand*{#1}{\mathop{#2}#3}}

\newoperator{\argmax}{\mathrm{argmax}}{\nolimits}

\newcommand\authorAffSize{\small}
\newcommand\department{Dept of Comp. Sci.}


%\theoremstyle{definition}
%\newtheorem{definition}{Definition}
%\newtheorem{example}{Example}
%\newtheorem{observation}{Observation}
%\newtheorem{proposition}{Proposition}
%\newtheorem{claim}{Claim}

%===================================================================
%===================================================================
%===================================================================
%===================================================================
%===================================================================
%===================================================================
%
%               Max's definitions START


%Shortcuts for \textbf \textit and \textrm
\newcommand{\tbf}[1]{\textbf{#1}}
\newcommand{\tit}[1]{\textit{#1}}
\newcommand{\trm}[1]{\textrm{#1}}

%\newcommand{\tpalatino}[1]{
%                   {\fontfamily{palatino}
%                   \selectfont
%                   #1
%                   }
%}

\newcommand{\SelSet}{$\mathscr{I}$}
\newcommand{\Attr}{$\mathscr{A}$}
\newcommand{\Constraints}{$\mathscr{C}$}
\newcommand{\InducedAttrSet}{$\tilde{\mathscr{A}}$}
\newcommand{\ConstSet}{$\mathscr{C}$}


\newcommand{\nog}{NoGood}
\newcommand{\nogs}{NoGoods}


%signs for the algorithms.
%BB-D = B&B-Dynamic
%BB-S = B&B-Static
\newcommand{\bbd}{\tbf{BB-D}}
\newcommand{\bbs}{\tbf{BB-S}}


%Special abbreviations and symbols definition
%The old ones from VC reduction
\newcommand{\Oh}[1]{$\mathcal{O}(#1)$}%Big Oh notation

\newcommand{\BigOh}{$\mathcal{O}$}
\newcommand{\Xmc}{$\mathcal{X}$}
\newcommand{\Xmcbar}{$\mathcal{\overline{X}}$}
\newcommand{\pos}{$\mathcal{POS}$}%preferences over sets
\newcommand{\posUCP}{$\mathcal{POS^*}$}%preferences over sets
\newcommand{\vc}{$\mathcal{VC}$}%vertex cover
\newcommand{\is}{$\mathcal{IS}$}%independent set
\newcommand{\IFF}{\tbf{iff}}
\newcommand{\threeSAT}{$3$-SAT}
\newcommand{\twoSAT}{$2$-SAT}
\newcommand{\kSAT}{$k$-SAT}
\newcommand{\maxtwoSAT}{MAX-$2$SAT}
\newcommand{\GAI}{GAI}
\newcommand{\NPhard}{NP-hard}

\newcommand{\ddpref}{DD-PREF}
\newcommand{\varSet}{$\mathcal{V}$}
\newcommand{\cnf}{CNF}
\newcommand{\sumattr}{\textit{SUM}}
\newcommand{\clauseSet}{$\Phi$}
\newcommand{\Dom}{\textit{Dom}}

\newcommand{\myremark}[1]{\par\texttt{#1}\newline}
\newcommand{\maxremark}[1]{\texttt{#1}}

\newcommand{\propertydefsimple}[1]{$\left< \left| #1 \right| \right>$}
\newcommand{\propertydefcomplex}[2]{$\left< \left| #1 \right| #2 \right>$}


\newcommand{\breakline}{\vspace{2pt}\hrule depth 0.2pt\vspace{2pt}}
\newcommand{\proofDirectionBox}[1]{\Ovalbox{#1}}
\newcommand{\thesisOnly}[1]{}



\newcommand{\fctr}{{\mathfrak{f}}}
\newcommand{\val}{{\mathsf{val}}}
\newcommand{\var}{{\mathsf{Var}}}
\newcommand{\newU}{{\mathfrak{U}}}
\newcommand{\newC}{{\mathfrak{C}}}
\newcommand{\domunion}{{\mathscr{D}}}
\newcommand{\model}{{\bm}}
\newcommand{\negn}{\overline}
\newcommand{\sbsts}[1]{2^{#1}}

\newcommand{\argmin}{\operatornamewithlimits{argmin}}


