\documentclass[twoside,11pt]{article}

% Any additional packages needed should be included after jmlr2e.
% Note that jmlr2e.sty includes epsfig, amssymb, natbib and graphicx,
% and defines many common macros, such as 'proof' and 'example'.
%
% It also sets the bibliographystyle to plainnat; for more information on
% natbib citation styles, see the natbib documentation, a copy of which
% is archived at http://www.jmlr.org/format/natbib.pdf

\usepackage{jmlr2e}

% Definitions of handy macros can go here

\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

\def\IF{{\mbox{ if }}}
\def\ST{{\mbox{ such that }}}
\def\POWER{{\mathbf{P}}}
\def\argmax{{\mathrm{argmax}}}
\newcommand{\poly}{poly}
\newcommand{\half}{\frac{1}{2}}


\newcommand{\defword}[1]{\textbf{#1}}
\newcommand{\mazcomment}[1]{}
\newcommand{\comment}[1]{}
%\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{obs}{Observation}
%\newtheorem{definition}{Definition}
%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}{Corollary}
\newtheorem{open}{Open Problem}
\newtheorem{algorithm}{Algorithm}
%\newcommand{\qed}{\hfill\rule{2mm}{2mm}}
\newcommand{\qed}{}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

\jmlrheading{5}{2004}{649-667}{1/04}{6/04}{Avrim Blum, Jeffrey Jackson, Tuomas Sandholm, and Martin Zinkevich}

% Short headings should be running head and authors last names

\ShortHeadings{Preference Elicitation and Query Learning}{Blum et al.}
\firstpageno{649}

\begin{document}

\title{Preference Elicitation and Query Learning}

\author{\name Avrim Blum \email avrim@cs.cmu.edu \\
       \addr Department of Computer Science\\
       Carnegie Mellon University\\
       Pittsburgh, PA 15213-3891, USA
       \AND
       \name Jeffrey Jackson \email jackson@mathcs.duq.edu \\
       \addr Department of Mathematics and Computer Science\\
       Duquesne University\\
       Pittsburgh, PA 15282-0001, USA
       \AND
       \name Tuomas Sandholm \email sandholm@cs.cmu.edu \\
       \name Martin Zinkevich \email maz@cs.cmu.edu \\
       \addr Department of Computer Science\\
       Carnegie Mellon University\\
       Pittsburgh, PA 15213-3891, USA
 }

\editor{Kristin Bennett and Nicol\`o Cesa-Bianchi}

\maketitle

\begin{abstract}%   <- trailing '%' for backward compatibility of .sty file
In this paper we explore the relationship between
``preference elicitation'', a learning-style problem that arises in
combinatorial auctions, and the problem of learning via queries
studied in computational learning theory.  Preference elicitation is
the process of asking questions about the preferences of bidders so as
to best divide some set of goods.  As a learning problem, it can be
thought of as a setting in which there are multiple target concepts
that can each be queried separately, but where the goal is not so much
to learn each concept as it is to produce an ``optimal example''.  In
this work, we prove a number of similarities and differences between
two-bidder preference elicitation and query learning, giving both separation
results and proving some connections between these problems.
\end{abstract}

\begin{keywords}
  exact learning, query learning, combinatorial auctions, preference
  elicitation.
\end{keywords}

\section{Introduction}
In a combinatorial auction, an entity (the ``auctioneer'') has a set
$S$ of $n$ items that he would like to partition among a set of $k$
bidders.  What makes an auction {\em combinatorial} is that the
valuations of the bidders --- how much they would be willing to pay for
different subsets of items --- may not necessarily be linear functions
over the items.  For instance, if item $a$ is a left shoe and item $b$
is a right shoe, then a bidder might be willing to pay a reasonable
amount for the bundle $\{a,b\}$ but very little for just $\{a\}$ or
just $\{b\}$.  In the other direction, if $a$ and $b$ are each {\em
pairs} of shoes, then a bidder might value $\{a,b\}$ less than the sum
of his valuations on $\{a\}$ and $\{b\}$ (especially if he just needs
one pair of shoes right now).  A standard goal for the auctioneer in
such a setting is to determine the allocation of goods that maximizes
{\em social welfare}: this is the sum, over all bidders, of the value
that each bidder places on the set of items that he receives.  This
goal is perhaps most natural if one thinks of the auctioneer as not
having a financial interest of its own but simply as an agent acting
to help divide up a given set of items in a way that maximizes overall
happiness or value.  For example, the auctioneer might be a government
agency, or a manager dividing up resources among different projects.
The case of $k=2$ can also be thought of as a situation in which one
of the bidders represents a buyer (with various preferences over
bundles of items) and the other bidder represents a marketplace (with
various discounts and package-deals), and the auctioneer is helping
the buyer decide what subset of items to purchase from the
marketplace.\footnote{To think of this as a combinatorial auction, it
is easiest to imagine that the auctioneer has pre-purchased {\em all}
the items, and then is deciding which the buyer should keep and which
should be returned for a refund.}


There are a number of issues that arise in the combinatorial auction
setting.  For example, there is much work on designing protocols
(mechanisms) so that bidders will be truthful in reporting their
valuations and not want to ``game'' the system
\citep{Sandholm02:eMediator,Nisan00:Computationally,Lehmann02:Truth}.
But another issue is that even if we can get bidders to be truthful,
their valuation functions can be quite complicated.  Because of this,
bidding in a traditional manner may require an exponential amount of
communication.  This has led researchers to study the notion of
preference elicitation, in which the auctioneer asks questions of the
bidders in order to learn (elicit) enough information about their
preferences to determine the best, or approximately best, allocation
of the items~\citep{Conen01:Preference}.  Because the issues of
truthfulness can be handled in this setting via known mechanisms
(discussed later in Section~\ref{sec:vcg}), the problem then becomes one of
determining which questions to ask in order to extract the information
needed for allocation, and to understand when this can be done
quickly.


\subsection{Preference Elicitation and Query Learning}
\label{sec:peql}

We can think of preference elicitation in the context of query
learning by thinking of each item as a boolean feature, thinking of a
subset of the $n$ items (a ``bundle'') as an example $x \in \{0,1\}^n$
indicating which items are in the subset, and thinking of the bidder's
valuation function as a target function.  The standard assumption
of ``free disposal'' --- bidders can throw away items for free --- means we can
assume that these valuation functions are {\em monotone}, though they
typically will not be boolean-valued (we might have $f(x) = \$100$,
for instance).  Furthermore, one of the natural types
of queries studied in preference elicitation, the {\em value query}
(where the auctioneer asks the bidder how much he values some bundle),
corresponds exactly with the learning-theoretic
notion of a membership query.

On the other hand, a key difference between preference elicitation and
query learning is in the goals.  In learning, the objective is
typically to recover the target function, either exactly or
approximately.  In preference elicitation, however, the goal is more
one of finding the ``best example''.  For instance, if there are just
two bidders with preference functions $f$ and $g$, then the goal is to
find a partition $(S',S'')$ of the $n$ items to maximize
$f(S')+g(S'')$.  Thinking in terms of functions over $\{0,1\}^n$, the
goal is to find $x \in \{0,1\}^n$ to maximize $f(x)+g(\bar{x})$.

Notice that one of the immediate differences between preference
elicitation and query learning is that preference elicitation makes
sense even if the target functions do not have short descriptions, or
even short approximations.  We will see some interesting examples later,
but as a simple case, if we learn that
bidder $A$ will pay \$100 for the entire set of $n$ items but no more
than \$50 for any subset of size $n-1$ (she is a collector and wants
the whole set), and $B$ will pay a maximum of \$50 even for the whole
lot, then we know we might as well give all items to $A$, and we do
not need to know exactly how much each bidder would have paid for
different subsets.  On the other hand, it is quite possible for
allocation of items to be {\em computationally} hard, even if the
preferences of all the bidders are known.  For example, even if each
bidder's preferences can be expressed as a simple conjunction (these
are called ``single-minded'' bidders), then if there are many bidders,
allocation is equivalent to the NP-hard set-packing problem.  Even for two
bidders, allocation can be NP-hard for
somewhat more complicated preference functions, such as read-once
formulas~\citep{Zinkevich03:Polynomial}.

Another difference concerns the types of queries that are most
natural in each setting.  While value/membership queries are common to
both, equivalence queries are quite {\em un}natural in the context of
preference elicitation.  On the other hand, the {\em demand query}, a
powerful type of query for preference elicitation introduced by
\citet{Nisan03:Lindahl}, does not seem to have been studied in query
learning.\footnote{In a demand query, the auctioneer proposes a price for
each item and then asks the bidder to specify a single subset of the
items that is optimal for the bidder given
those prices. Demand queries will be discussed further in
Section~\ref{sec:notation}.} 

In this paper, we discuss similarities and differences between the
three objectives of exact learning, approximate learning, and
preference elicitation. We then give a number of upper and lower
bounds for preference elicitation of natural preference (concept)
classes.  We focus primarily on the case of $k=2$ bidders, because
even this case is quite interesting, both practically (since it models
a buyer and a marketplace as mentioned above) and technically. We
first consider monotone DNF formulas, which have long been known to be
hard to learn exactly from membership queries alone but easy to learn
approximately (in a strong, distribution-free PAC sense) given
membership queries and polynomially many random examples of the target
formula~\citep{An88}.  We show that monotone DNF formulas are {\em
hard} for preference elicitation, even with demand queries.  However,
the hardness we show is $2^{\Omega(\sqrt{n})}$-hard rather than the
$2^{\Omega(n)}$-hardness one gets for exact learning of monotone DNF.
On the other hand, we show $\log(n)$-DNF formulas are {\em easy} for
preference-elicitation, even if the functions have more than
polynomially many terms.  We also give a number of general statements
about when the ability to succeed for one of these goals implies being
able to succeed in the others.  After comparing elicitation with
boolean-valued and real-valued preference functions, we briefly
consider the issue of truthfulness in elicitation.  We then summarize
subsequent related work that has been done since the conference
(COLT-03) version of this paper appeared. Finally, we end with two
open problems.

% Since we now have only two open problems, we can't call it ``several''.

\subsection{Related Work on Combinatorial Auctions}

There is a substantial literature of work on combinatorial auctions.
The standard view of these auctions (without the interactive notion of
preference elicitation) is that bidders submit bids on bundles in some
appropriate bidding language, and then the auctioneer determines who
wins what based on these bids.  The issue of 
determining the winners in such auctions, given the bids, is a complex
optimization problem that has received considerable attention 
\citep{Rothkopf98:Computationally,Sandholm02:Algorithm,Fujishima99:Taming,Nisan00:Bidding,Andersson00:Integer,Sandholm01:CABOB}.
%
%Tennenholtz00:Some,DeVries03:Combinatorial,Hoos01:Bidding, (JOURNAL????)
Communication complexity issues have received substantial attention as
well. 
There are $2^n -1$ bundles, and each agent may need to bid on all of
them to fully express its preferences.
%%This can be undesirable for any of several reasons:
% %(1a)
% determining one's valuation for any given bundle can be computationally
% intractable~\citep{Sand93,Sandholm00:Issues,Parkes99:Optimal,Larson01:Costly};
% %Larson02:Bidders,Sand93,FINAL VERSION???
% %Larson00:Deliberation,Larson01:Computationally (JOURNAL)
% %
% %(1b)
% there is a huge number of bundles to evaluate;
% %(2)
% communicating the bids can incur prohibitive overhead (e.g., network
% traffic); and
% %(3)
% agents may prefer not to reveal all of their valuation information due to
% reasons of privacy or long-term competitiveness~\citep{Rothkopf90:Why}.
% %
Appropriate bidding
languages~\citep{Sandholm02:Algorithm,Sandholm02:eMediator,Fujishima99:Taming,Nisan00:Bidding,Hoos01:Bidding,Sandholm01:Side}
can address the communication overhead in some cases where the bidder's
utility function is compressible.
%
%DO WE WANT TO GO INTO THE ABOVE ARGUMENT HERE ???
%
However, they still require the agents to completely determine and
transmit their valuation functions and as such do not solve all the
issues.
%
So in practice, when the number of items for sale is even moderate, the
bidders cannot bid on all bundles.
%They may bid on bundles on which they
%will not be competitive  (thus wasting evaluation effort and
%communication, as well as compromising privacy unnecessarily).  They
%may also not bid on some of the bundles on which they would have been
%competitive (thus leading to the above problems as well as reduced
%economic efficiency and revenue).
Instead, they may bid on bundles which they will not win, and they may
fail to bid on bundles they would have won.  The former problem leads
to wasted effort, and the latter problem leads to reduced economic
efficiency of the resulting allocation of items to bidders.

{\em Preference elicitation}, the subject of this paper, was recently
proposed to address these problems~\citep{Conen01:Preference}, and
several papers have studied different types of
elicitors~\citep{Conen02:Partial,Conen02:Differential,Hudson04:Effectiveness,Nisan03:Lindahl,Smith02:Constructing}.
%% That work usually makes the natural assumption that there is {\em free
%% disposal}, that is, a bidder can throw away extra items for free.
%% This implied that a bidder's valuation for a bundle is at least as
%% high as his valuation for a subbundle of that bundle.  
On the negative side, if valuations are arbitrary monotone functions,
then the worst-case communication complexity to find an (even
approximately) optimal allocation is exponential
in the number of items, no matter what query types are
used~\citep{Nisan03:Lindahl}.  Nonetheless, empirically,
preference elicitation can provide a substantial savings compared to
explicitly bidding on all $2^n-1$ bundles \citep{Hudson04:Effectiveness}.
%%only a small decreasing fraction of the bidders' preferences can be
%%elicited before the provably optimal allocation is found~


An issue that arises in the study of auctions is that bidders may lie
about their preferences (e.g., bidder $f$ when queried with $x$ may
not truthfully report $f(x)$) if they believe it may help in the final
allocation.  However, {\em Vickrey-Clarke-Groves (VCG)}
schemes~\citep{Vickrey61,Clarke71:Multipart,Groves73:Incentives}
provide a method for charging bidders so that each is motivated to
tell the truth about its valuations.  Briefly, in this scheme the
elicitor first finds the optimal allocation $OPT$ under the assumption
that bidders are behaving truthfully.  Then, for each bidder $i$, the
elicitor finds the optimal allocation $OPT_i$ without bidder $i$,
again assuming truthful behavior.  Finally, bidder $i$ is charged a
fee based on the difference between the utility of the other agents in
$OPT$ and $OPT_i$.  It seems perhaps circular at first glance, but one
can show that in such a scheme, each bidder will in fact be motivated
to be truthful throughout the whole
process~\citep{Conen01:Preference}.  Formally, bidding truthfully is
an {\em ex-post equilibrium}.  We discuss these issues in more detail
in Section \ref{sec:vcg}, but the conclusion is that if one can elicit
the optimal allocation exactly assuming that agents tell the truth,
one can determine VCG payments that make truth-telling the best
strategy for the bidders.  Because of this, for the remainder of the
paper (except Section
\ref{sec:vcg}) we will assume that the bidders are truthful.

Driven by the same concerns as preference elicitation in combinatorial
auctions, there has also been significant recent work on ascending
combinatorial auctions
\citep{Parkes99:Optimal,Parkes99:iBundle,Ausubel02:Ascending,Wurman00:AkBA,BDSV01,Bik-Ostroy:01}.
These are multistage mechanisms.  At each stage the auctioneer
announces prices (on items or in some cases on bundles of items), and
each bidder states which bundle of items he would prefer (that is,
which bundle would maximize his valuation minus the price he would
have to pay for the bundle) at those prices.  The auctioneer increases
the prices between stages, and the auction usually ends when the
optimal allocation is found.  Ascending auctions can be viewed as a
special case of preference elicitation where the queries are demand
queries (``If these were the prices, what bundle would you buy from
the auction?'') and the query policy is constrained to increasing the
prices in the queries over time.  Recently it was shown that if {\em
per-item} prices suffice to support an optimal allocation (i.e., a
{\em Walrasian equilibrium} exists), then the optimal allocation can
be found with a polynomial number of queries, where each query and
answer is of polynomial size~\citep{Nisan03:Lindahl}.

Recently, some of us~\citep{Zinkevich03:Polynomial}, noticing the
connection to query learning, showed how the algorithm of
\citet{AnHeKa93} for learning read-once formulas over standard boolean
gates could be adapted to elicit preferences expressible as
read-once-formulas over gates that are especially natural in the
context of combinatorial auctions.  This work goes on to discuss
computational considerations, showing on the negative side that
allocation can be NP-hard even for two bidders with read-once-formula
preferences, but on the other hand, allocation can be done in
polynomial time if one of the two bidders has a linear value function.
%%\footnote{The reviewer may well be wondering why the current work
%%was not put into that paper, and what really the difference is between the
%%two.  The answer is that the focus of the previous paper was on handling
%%read-once-formula preferences over broader and broader classes of
%%gates and algorithmic issues in allocation, whereas the intent of the
%%current paper is to compare and contrast the models.}

\section{Notation and Definitions}\label{sec:notation}
Because subset notation is most natural from the point of view of
preference elicitation, we will use both subset notation and
bit-vector notation in this paper.  That is, we will think of the
instance space $X$ both as elements of $\{0,1\}^n$ and as the power
set of some set $S$ of $n$ {\em items}.  We will also interchangeably
call a subset of $S$ a 
``bundle'' or an ``example''.  When discussing preference elicitation,
we assume there are $k$ bidders with monotone real-valued preference
functions over the instance space.  The objective of preference
elicitation is to determine a $k$-way partition $(S_1, \ldots, S_k)$
of $S$ to maximize $f_1(S_1) + f_2(S_2) + \ldots + f_k(S_k)$, where
$f_1, \ldots, f_k$ are the $k$ real-valued preference functions.  Unless
otherwise noted, we 
will assume $k=2$; Section~\ref{sec:peql} provides some justification
for this focus.

Let $C$ be a class of monotone functions.  We
will be interested in the learnability of various $C$ --- that is,
in various subsets of the class of monotone functions --- in the
exact learning, approximate learning, and preference elicitation
models given the ability to make various types of queries. 
%% By ``approximate learning'' we mean learning with respect to the
%% uniform distribution on inputs --- i.e.., finding a hypothesis
%% function that agrees with the target over almost all of the instance space.  
%%%
%Because preference elicitation makes sense even
%when preferences are quite complicated, we will explicitly say in each
%result whether we are looking at complexity solely as 
%a function of $n$, the number of items, or also as a function of the
%description length of the target/preference functions in the given
%representation. 
While learning algorithms are typically considered efficient if they run
in time polynomial in the number of items $n$ and in the length of
the representation of the target (and possibly other parameters), we will at 
times explicitly 
require run time bounds independent of description length in order to
demonstrate a fundamental advantage of preference elicitation for
problems involving complex targets.  The hardness observations for
learning problems when this restriction is in place are 
therefore not hardness results in the standard learning-theoretic sense.

\paragraph{Query types:}
A {\em membership query} or {\em value query} is a request $x \in
\{0,1\}^n$ to an oracle for a target $f$.  The oracle responds with
the value $f(x)$ corresponding to $x$.
%%While this oracle is typically viewed as applying to boolean $f$, we
%%will also use the terms membership query and {\em value query} to
%%refer to requests to similar oracles for any real-valued $f$.  
We can think of these queries as asking the following question of a
bidder: ``How much are you willing to pay for this bundle of items?''

A {\em demand query} is a request $w \in (${\bf R}$^+)^n$
({\bf R}$^+$ here represents non-negative real values)
to an oracle for a target $f$.  The oracle responds with
an example $x \in \{0,1\}^n$ that maximizes $f(x)-w\cdot x$. 
%% such that the dot product $w \cdot x$ is minimized over all $x$ 
%% for which $f(x) > 0$.  
We can think of a demand query $w$ as asking the following question of a
bidder: ``If you were in a store in which item $i$ had cost $w_i$,
what subset of items would you choose to buy?''
%% is the least expensive bundle of items that will satisfy your
%% preference function?'' 

We can illustrate the power of demand queries with the following
observation due to Nisan.  If one of the bidders has a linear
valuation function, and the other is arbitrary, then preference
elicitation can be done with $n+1$ queries: $n$ value queries and one
demand query.  Specifically, we simply ask the linear bidder $n$ value
queries to determine his value on each item, and then send the other
bidder these values as prices and ask him what he would like to buy.
Thus it is interesting that our main lower bounds, for elicitation of
monotone DNF formulas, hold for demand queries as
well.\footnote{\citet{Lahaie04:Applying} recently studied a more
powerful notion of demand query in which one can propose an arbitrary
polynomial-size function $h(x)$, and receive the $x$ that maximizes
$f(x) - h(x)$.  With this type of query, one {\em can} elicit monotone
DNF formulas, since one can now directly apply Angluin's algorithm
\citep{An88}, making a demand query of this kind whenever Angluin's
algorithm would make an equivalence query.  Lahaie and Parkes go on to
explore further the power of this query class. \label{footnote:dq}}

\paragraph{Natural function/representation classes:}
One of the most natural representation classes of monotone functions
in machine learning is that of monotone DNF formulas.  In
combinatorial auctions, the analog of this representation is called
the ``XOR bidding language''
\citep{Sandholm02:Algorithm}.\footnote{This terminology is to indicate
that the bidder wants only one of his listed bundles and will not pay
more for a set of items that contains multiple bundles inside it.
This usage is very different from the standard definition of XOR as a
sum modulo 2.  Therefore, to avoid confusion, we will not use the XOR
terminology here.} A preference in this representation is a set of
bundles (terms) $T = \{T_1, T_2, \ldots, T_m\}$ along with a set of
values $v = \{v_1, v_2, \ldots, v_m\}$, one value $v_i$ for each
bundle $T_i$.  The value of this preference for all $S'\subseteq S$
is $$f_{T,v}(S')=\max_{T_i \subseteq S'} v_i.$$ In other words, the
value of a set of items $S'$ is the maximum value of any of the
``desired bundles'' in $T$ that are contained in $S'$.  We will call
this the {\em DNF representation} of preferences, or ``DNF
preferences'' for short.  Our hardness results for this class will all
go through for the boolean case (all $v_i$ are equal to 1), while two
of our positive results will hold for general $v_i$.

\comment{
In fact, this is not
surprising because of the following theorem.

\begin{theorem}\label{thm:bool}
Let $C$ be a subclass of DNF preferences that is closed under removal
of terms (if $f\vee T \in C$ then $f \in C$).  Then, if preference
elicitation using value queries can be done for $C$ for boolean
valuations, preference elicitation can also be 
done for general $v_i$ with a number of queries that is at most
polynomially larger in the size of the preference functions.
\end{theorem}

\begin{proof}
The idea of the proof is that if we knew the $v_i$'s, then we could
run our boolean algorithm $m^2$ times, once for each pair $(v,v')$,
viewing valuations for $f$ that are $\geq v_i$ as positive and those
$< v_i$ as negative (and same for $g$ and $v_j$).  We don't know the
$v_i$'s to start, but we can find them out as we go.  Specifically, we
begin by asking for $f(S)$ and $g(S)$ to get the maximum possible
valuations for each.  Now, suppose we have values $v_1, \ldots, v_t$
for $f$ and $v_1', \ldots, v_{t'}'$ for $g$. 
\end{proof}
}

%% 
%% {\sf [I think we can give a general argument that for DNF, if you can
%% solve the boolean case then you can solve the general case.  The idea
%% would be that there are only $m^2$ pairs of interesting values
%% $(v_f,v_g)$ so we could separately run our algorithm $m^2$ times and
%% then pick the best result.  (I.e., we think of values $\geq v_f$ as
%% positive for $f$ and smaller values as negative, and this is still a
%% DNF formula).  Does this sound right?  We need to know
%% what the $v_i$ are for this but I think we can figure this out as we go...]}
%% 
%% {\sf [[ jcj: I think that works if we can learn the $v_i$. ]]}

\section{DNF Preferences}\label{sec:DNF}
\citet{An88} shows that monotone DNF formulas are hard to
exactly learn from value (membership) queries alone, but are easy to learn
approximately given membership queries plus random examples 
(in the PAC distribution-free, strong learning model).  
Angluin's example showing hardness of exact learning
can be thought of as follows: 
imagine the $n$ items are really $n/2$ pairs of shoes.  The buyer
would be happy with any bundle containing at least one pair of shoes
(any such bundle is worth \$1).  But then we add one final term to the
DNF: a bundle of size $n/2$ containing exactly one shoe from each
pair, where for each pair we flip a coin to decide whether to include
the left or right shoe.  Since the learning algorithm already knows
the answer will be positive to any query containing a pair of shoes,
the only interesting queries are those that contain no such pair, and
therefore it has to match the last term {\em exactly} to provide any
information.  Thus even for a randomized algorithm, an expected 
$2^{n/2-1}$ value queries are needed for exact learning of monotone
DNF formulas.

We now consider the two-bidder preference elicitation problem when
one or both of the
preferences are represented as monotone DNF expressions,
beginning with a few simple observations.

\begin{obs}\label{obs:known}
If $f$ is a {\em known} DNF preference function with $m$ terms, and
$g$ is an {\em arbitrary} unknown monotone preference function, then
preference elicitation can be performed using $m+1$ value queries.
\end{obs}
\begin{proof} Because $g$ is monotone, the optimal allocation will either be
of the form $(T_i, S - T_i)$, for some term $T_i$ in $f$, or else all of
the items in $S$ will go to the bidder with preference $g$.  So, we
simply need to query $g$ once for $S$ and once for 
each set $S-T_i$ and then pick the
best of these $m+1$ partitions.\qed
\end{proof}

\begin{obs}\label{obs:easy}
If $f$ and $g$ are boolean DNF preferences each containing
at most one term with more than two literals
(the hard case in Angluin's construction) then
preference elicitation can be performed using poly$(n)$ value queries.
\end{obs}

\begin{proof}
Since $f$ and $g$ are boolean (they each assign every bundle a value of
either $0$ or $1$), the problem is simply to find 
terms $T_f$ in $f$ and $T_g$ in $g$ which have no
items in common, if such a pair of terms exists.
We begin by finding all terms in $f$ of size $\leq 2$ by asking $n^2$
queries. Suppose two of these terms $T_1$ and $T_2$ are disjoint.  In
that case, we query $g$ on $S - T_1$ and $S - T_2$.  If one answer is
$1$ then we are done.  If both answers
are $0$ then this means all of $g$'s terms intersect both $T_1$ and
$T_2$. In particular, $g$ can have only a constant number of terms, and
therefore {\em exactly} learning $g$ is easy, after which we can then apply
Observation~\ref{obs:known} (swapping $f$ and $g$).   On the other
hand, if $f$ does not have two disjoint terms of size $\leq 2$, then the only
way $f$ can have more than three such terms is if they all share some
common item $x_i$.  It is thus now easy to learn the large term in $f$:
if $f(S - \{x_i\})=1$, we can find this term by 
``walking downward'' from the
example $S - \{x_i\}$, that is, by iteratively removing
as many items as possible from this bundle
subject to keeping $f$'s value $1$.
On the other hand, if $f(S - \{x_i\})=0$, meaning that the large term
contains $x_i$ as well,
we can walk downward from the example in
which all the {\em other} items in the small terms have been removed.
Once $f$ has been learned, we can again apply
Observation~\ref{obs:known}.
\qed
\end{proof}

We now show that even though Angluin's specific example is no longer
hard in the preference elicitation model, monotone DNF formulas 
(defining boolean preference functions) remain
hard for preference elicitation using value queries, even when the
preference functions are quite small.  We then extend this result to
demand queries as well.

\begin{theorem}\label{thm:dnfvaluelower}
Preference elicitation of monotone DNF formulas requires
$2^{\Omega(\sqrt{n})}$ value queries.  This holds even if each
bidder's preference function has only $O(\sqrt{n})$ terms.
%and the preferences are boolean.
\end{theorem}

\begin{proof}
We construct a hard example as follows.  There will be $n=m^2$ items,
arranged in an $m$-by-$m$ matrix.  Let us label the items $x_{ij}$ for
$1 \leq i,j \leq m$.   We will call the
two preference functions $f_R$ and $f_C$.  Both will be boolean
functions.  Bidder $f_R$ is happy with
any row: that is, $f_R = x_{11}x_{12}\cdots x_{1m} \vee x_{21}x_{22}
\cdots x_{2m} \vee \ldots \vee x_{m1}x_{m2}\cdots x_{mm}$.  Bidder
$f_C$ is happy with any column: that is, $f_C = x_{11}x_{21}\cdots
x_{m1} \vee x_{21}x_{22} \cdots x_{m2} \vee \ldots \vee
x_{1m}x_{2m}\cdots x_{mm}$.  Thus, at this point, it is impossible to
make both bidders happy. However, we now add one additional term to
each preference function.  We flip a coin for each of the $n$ items in
$S$, labeling the item as heads or tails.  Let $H$ be the set
of all items labeled heads, and $T$ be the set of all items
labeled tails. We now add the conjunction of all items in $H$ as one
additional term to $f_R$, and the conjunction of all items in $T$ as
one additional term to
$f_C$.   Thus now it {\em is} possible to make both bidders happy, and
the optimal allocation will be to give the items in $H$ to the ``row
bidder'' and the items in $T$ to the ``column bidder''.

We now argue that no query algorithm can find this allocation in less
than $\half 2^{\sqrt{n}}-2$ queries in expectation.
Let us enforce that the last two questions of the query protocol are the
values of the actual allocation.   That is, if the elicitor assigns
the items in $H$ to the row agent and $T$ to the column
agent, it must ask the row agent the value of $H$ and the column agent
the value of $T$. This constraint only increases the
length of the protocol by at most 2 questions.

Let us assume that the elicitor knows in advance the structure of the
problem, the row sets and the column sets, and the only information
the elicitor does not know are the sets $H$ and $T$.   In this case,
we can assume without loss of generality that the elicitor never asks
the row bidder about any bundle containing a row (because he already
knows the answer will be ``yes'')  and similarly never asks the column bidder
about any bundle containing a column. 

We now argue as follows.
If the elicitor asks a query of the row bidder, the query
must be missing at least one item in each row, and if the elicitor ask
a query of the column bidder, it must be missing at least one item in
each column.  However, notice that in the first case, the answer will
be positive only if all missing items are in $T$, and in the second
case, the answer will be positive only if all missing items are in
$H$.  Therefore, for any given such query, the probability that
the answer will be positive taken over the random coin flips is at
most $2^{-\sqrt{n}}$. Thus, for any elicitation strategy, the
probability the elicitor gets a positive response in the first $q$
queries is at most $q2^{-\sqrt{n}}$ and therefore the expected number
of queries is at least $\half 2^{\sqrt{n}}$.
\qed
\end{proof}

We now show that preference elicitation remains hard for DNF
preferences even if we allow demand queries.
\begin{theorem}\label{thm:dnfdemandlower}
Even if both demand queries and value queries are allowed, preference
elicitation of monotone DNF formulas requires $2^{\Omega(\sqrt{n})}$
queries.  This holds even if each bidder's preference function
has only $O(\sqrt{n})$ terms.
\end{theorem}
\begin{proof} We use the same example as in the proof of Theorem
\ref{thm:dnfvaluelower}.  As in that proof, we can insist that the
last question be a demand query where the agent responds with the set
$H$ or $T$ respectively.  Let us without loss of generality consider a
sequence of demand queries to the ``row bidder''.  What we need to calculate now
is the probability, for any given cost vector $w$, that the set $H$
happens to be the cheapest term in his DNF formula.  The intuition is
that this is highly unlikely because $H$ is so much larger than the
other terms.

Specifically, for a given query cost vector $w$, let $w_i$ be the
total cost of the $i$th row.  Thus, the cheapest row has cost
$\min(w_1, \ldots, w_m)$ and the {\em expected} cost of $H$ is
$\half(w_1 + \ldots + w_m)$.  One simple observation that helps in the
analysis is that if we define $h_i$ as the cost of the items in $H$
that are in the $i$th row, then $\Pr(h_i \geq w_i/2) \geq 1/2$. That
is because if any particular subset of the $i$th row has cost less
than $w_i/2$, its complement in the $i$th row must have cost greater
than $w_i/2$.  Furthermore, these events are independent over the
different rows.

So, we can reduce the problem to the following: we have $m$
independent events each of probability at least $1/2$.  If at least
two of these events occur, the elicitor gets no information ($H$ is
not the cheapest bundle because it is not cheaper than the cheapest
row).  Thus, the probability the elicitor {\em does} get some
information is at most $(m+1)2^{-m}$ and the expected number of
queries is at least $\frac{1}{2(m+1)}2^m$.
\qed
\end{proof}

\begin{open}
Can preferences expressible as polynomial-size DNF formulas be
elicited in $2^{O(\sqrt{n})}$ value queries or demand queries?
(This is open even for the boolean preference case.)
\end{open}

\subsection{log(n)-DNF Preferences}
\label{sec:logdnf}
In the previous problem, even though there were only $O(\sqrt{n})$
terms in each preference function, the terms themselves were fairly
large.  What if all of the terms are small, of size no more
than $\log n$? Observe that there are $n \choose {\log n}$ possible terms
of size $\log n$, so some members of this class cannot be represented 
in poly$(n)$ bits.
 

\begin{theorem}\label{thm:log}
If $f$ and $g$ are DNF-preferences where all terms are of
$O(\log n)$, then preference elicitation can be performed in
a number of value queries polynomial in $n$.  
\end{theorem}

\begin{proof}
We begin by giving a randomized construction and then show a
derandomization.

For convenience let us put an empty term $T_0$ of value 0 into both
$f$ and $g$.  With this convention we can assume the optimal
allocation satisfies some term $T' \in f$ and some term $T''\in g$.

We now simply notice that since $T'$ and $T''$ are both of size
$O(\log n)$, a random partition $(S',S'')$ has probability at
least $1/$poly$(n)$ of having the property that $S' \supseteq T'$ and
$S'' \supseteq T''$.  So, we simply need to try poly$(n, \log
\frac{1}{\delta})$ random 
partitions and take the best one, and with probability at least
$1-\delta$ we will have found the optimal allocation.

We can now derandomize this algorithm using the
$(n,k)$-universal sets of~\citet{NaorNa90}.  A set of
assignments to $n$ boolean variables is $(n,k)$-universal if for every
subset of $k$ variables, the induced assignments to those variables
covers all $2^k$ possible settings. \citet{NaorNa90}
give efficient explicit constructions of such sets using only
$2^{O(k)}\log n$ assignments.  In our case, we can use the case of $k
= O(\log n)$, so the construction is polynomial time and size.
Each of these assignments corresponds to a partition of the items, and
we simply ask $f$ and $g$ for their valuations on each one and take
the best.
%% Assume $S=\{1,\ldots,n\}$.
%% Suppose we have a set $T$ of binary strings of length $n$ representing
%% the questions we will ask. Given a string $s \in \{0,1\}^n$, define $C$ to be the set $\{i\in
%% \{1,\ldots,n\}:s_i=0\}$ of items for which the corresonding bit of $s$ is zero, and
%% define
%% $C'=S\backslash C$ (the set of items for which the corresponding bit of $s$ is one).  
%% We query $f$ on
%% $C$ and $g$ on $C'$. We do this for every string in $T$.
%% %Suppose that for some string $s$ in $T$, $B\subseteq C$ and $B'\subseteq C'$.
%% %Then after these two queries, we know that we can allocate $C$ to $f$ and $C'$
%% %to $g$ to get a total value of 2.
%% So if there is a string $s$ in $T$ such that $B\subseteq C$ and $B'\subseteq C'$
%% then after making these two queries we will have found an optimal allocation
%% $(C,C')$.
%% What remains is to 
%% show how to
%% construct a set of strings $T$ such that for every pair of 
%% sets $B,B'\subseteq S$ where $|B|,|B'|\leq \log_2 n$, 
%% %there exists a string $s$ in
%% %$T$ such that $B$ is all zeros and $B'$ is all ones.
%% $T$ will contain such an $s$.
%% 
%% In fact, such constructions already exist \citep{ChKoMa83}.
%% %Such sets of strings have been developed. 
%% Define a {\em $k$-projection} on $\{0,1\}^n$ to be a projection 
%% on any fixed set of $k$ of the $n$ coordinates.  
%% A $k$-projection is {\em surjective}
%% for a set $T\subseteq \{0,1\}^n$ if for any $y \in \{0,1\}^k$
%% there exists $s \in T$ such that $s$ is projected to $y$.
%% 
%% \begin{theorem}[ChKoMa] For any $1 \leq k \leq n$, there exists a set $T$ of
%% strings of length $n$ such that all $k$-projections are surjective
%% for $T$ and $|T| = O(k2^k \log n)$.  
%% \end{theorem}
%% 
%% %The $k$ indices we are concerned with are $B\cup B'$.
%% We are interested in projections on the coordinates corresponding
%% to the elements of $B\cup B'$.
%% Therefore, taking $k=2\log_2 n\geq |B \cup B'|$, we can construct a
%% set $T$ of size $O(n^2 \log^2 n)$ containing at least one string $s$
%% corresponding to an optimal allocation $(C,C')$.
%% So we need ask no more than twice
%% this many value queries, a number polynomial in $n$.
\qed
\end{proof}

\section{General Relationships}\label{sec:general}
In this section we describe a number of general relationships between query
learning and preference elicitation.   We will solely concern
ourselves here with communication/query complexity issues, and not
with the issue of computation time.

To begin with some simple relationships, it is clear that preference
elicitation is no harder than exact learning, since one way to perform
elicitation is to simply learn each bidder's preferences exactly.  On
the other hand, the results from the previous section show that this
is not true for approximate learning.  Occam's razor theorems
\citep{BEHW87} imply that {\em any} function can be approximately
learned with a number of queries polynomial in the description length
of the function (ignoring issues of computation time), and thus
Theorems \ref{thm:dnfvaluelower} and \ref{thm:dnfdemandlower} imply a
super-polynomial gap between the number of value queries needed for
preference elicitation and approximate learning for the case of
monotone DNF formulas.  In the other direction, we have seen several
examples of cases where preference elicitation is {\em easy} and yet
it is hard to perform exact learning (Theorem
\ref{thm:log}) or even approximate learning (example in Section
\ref{sec:peql}) because the target function cannot be written down,
even approximately, in a small number of bits.  

These last examples are something of a ``cheat'' because the function
cannot even be described compactly.  We now describe a case in which
preference elicitation is easy but exact learning is hard, even though
the function has a small description.   We then show that in
certain circumstances, however, the ability to elicit does imply the
ability to learn with queries. 

\subsection{Almost-Threshold Preferences}

We now define a class of boolean preference functions that we call
{\em almost-threshold}.  This class will be used to show that, even if
all of the functions in a class have representations of size
polynomial in $n$, we can still separate exact learning and preference
elicitation with respect to value queries.  In fact, the gap is
super-exponential.

An ``almost threshold'' preference function is defined by specifying
a single set $S'$.
This set in turn defines a preference function that is $1$ for
any set of size greater than or equal to $|S'|$, except for $S'$ 
itself, and is $0$ otherwise. Formally, for any $S'\ne \emptyset$, define
%%$h_{S'}:\POWER(S)\to \{0,1\}$ such that for all $S''\subseteq S$:
$$h_{S'}(S'')=\left \{ \begin{array}{ll} 
1 & \textrm{if $S''\ne S'$ and $|S''|\geq | S'|$}\\ 
0 & \textrm{otherwise} 
\end{array} \right .$$
The class $H_{AT}$ of almost-threshold preference functions
is then $H_{AT}=\{h_{S'}\}$. 


\begin{obs} It requires at least $n \choose
{\lceil n/2 \rceil}-1$ value queries to exactly learn the class $H_{AT}$.
\end{obs}

\mazcomment{
\begin{proof}Define $m=\lceil |S|/2 \rceil$. Consider a deterministic 
algorithm. Suppose the oracle responds to 
any query of a set of size greater than $m$ with a 1, any set of size
less than $m$ with a zero, and the first  
${n\choose m} - 1$ value queries on sets of size $m$
with zero.  If $n\choose {m}-1$ distinct bundles of size $\lceil n/2 \rceil$
have been queried, then answer all following questions as if $S'$ were the set 
of size $m$ not queried.
\end{proof}
}


\begin{theorem}If $f,g\in H_{AT}$ 
then
the optimal allocation can be elicited in $4+\log_2 n$ value queries.  
\end{theorem}

\begin{proof}
Recall that we use $S$ to represent the set of all items, and
assume $|S|>2$.  Also suppose $f=h_{S'}$. The first step
is to determine $|S'|$. We can do this in $\log_2 n + 1$ queries using
binary search.  
%% Specifically, if at any point in the search
%% we know $k$ and $\ell$ such that $k\leq |S'|\leq \ell$ where $\ell>k+1$, 
%% then we select a set
%% $T$ of size $m=\left \lceil \frac{k+l}{2}\right \rceil$ and test if
%% $f(T)=1$.  If $f(T)=1$, then $m\leq |S'|\leq \ell$. If $f(T)=0$, then
%% $k\leq |S'| \leq m$.
%% If $\ell=k+1$, then we select two sets $T,T'$ of size
%% $k$. $|S'|=\ell$ if and  
%% only if $f(T)=f(T')=0$. Overall, then,
%% $\log_2 n+1$ membership queries are required to find $|S'|$.
%% 
We next find two sets $T,T'$ of size $|S'|$
such that $f(T)=f(T')=1$.  This can be done by picking three
arbitrary sets of size $|S'|$ and querying the first two: at most
one of these two sets can have the value $0$, and if one of the
two sets does 
have this value then the third set must have the value $1$.  
Our final query is for the
value of $g(S- T)$.  If this query returns $1$, then $T,S- T$ is an
optimal allocation (and has value $2$). Otherwise, $T',S- T'$,
regardless of its value, is an optimal allocation.  Thus, we can find
the optimal allocation in $4+\log_2 n$ value queries, although we may
need one more query if we wish to determine the value of this
allocation.  \qed
\end{proof}

\subsection{When Easy Elicitation Implies Easy Learning}
% We now show that in
% certain circumstances, however, the ability to elicit does imply the
% ability to learn with queries.  In particular, we will show that in
% certain cases, the ability to perform preference elicitation will provide
% us with a Superset Query oracle, which together with membership
% queries can allow us to to learn concept classes not learnable by
% membership queries alone.

We now show that in certain circumstances, however, the ability to
elicit with a polynomial number of value queries does imply the
ability to exactly learn with a similar number of queries.  In
particular, we will show that if preference elicitation can be
performed query-efficiently for preferences drawn from certain boolean
classes then a superset query can be efficiently simulated using value
queries.

\begin{definition}
  A {\bf superset oracle} for a target $f^*$ in a boolean concept
  class $H$ takes a function $f \in H$ as input.  If $f$ is a superset
  of $f^*$, that is, $\{x:f(x)=1\} \supseteq \{x:f^*(x)=1\}$, then the
  query returns ``true''.  Otherwise the query produces a
  counterexample: an $x$ such that $f(x)=0$ but $f^*(x)=1$.
\end{definition}

% Notice that Angluin's algorithm \citep{An88} for learning Monotone DNF
% can use superset queries instead of equivalence queries, because  the
% hypothesis is always a subset of the target function.  Furthermore,

Recall that Angluin's algorithm \citep{An88} for learning monotone DNF
uses value (membership) and equivalence queries, but that the
equivalence oracle is always queried with a hypothesis that is a subset
of the target function (it is an improper subset, the target itself, on
the final query).  Therefore, the same algorithm can be used to learn
monotone DNF from a value and superset oracle.  In fact, it can be seen that
any subclass of monotone DNF that is closed under removal of terms can
be learned from value and superset queries by the same
algorithm. 

\comment{
\begin{obs}Given a monotone DNF function over $S$ with $L$ terms from
a hypothesis space $H$ closed under removal of a term, one can learn
it with $L$ superset queries and $(L+1)\left (\frac{n(n+1)}{2}
\right )$ value queries.
\end{obs}

\begin{proof}Suppose that $f^*$ is our target function.  First, we set
$S_1=S$ and test if $f^*(S_1)=1$. If it is not, we return
0. Otherwise, we remove one item at a time from $S_1$ keeping it
positive, using $\frac{n(n+1)}{2}-1$ queries, to find the first term
$T_1$.

At some stage $k$, we have $k$ terms $T_1,\ldots,T_k$ in $f^*$, and
have used $k-1$ superset queries and less than $k\frac{n(n+1)}{2}+1$
value queries. We form a function $f_k=\{T_1,\ldots,T_k\}$ and
test if $f_k$ is a superset of $f^*$. If it is, then $f_k=f^*$. If it
is not, then a counterexample $S_{k+1}$ is found. Observe that
$f_k(S_{k+1})=0$. We then remove items from $S_{k+1}$ to find a new
term in $f^*$, $T_{k+1}$.
\end{proof}
}

What makes this interesting is the following relationship between
preference elicitation and superset queries.  First, for any boolean
function $f$, let us define its ``dual''
%%In order to discuss the relationship between superset queries and
%%preference elicitation, for any function $f:\POWER(S)\to \{0,1\}$ 
%%we define the complement $\hat f:\POWER(S)\to \{0,1\}$ such
%%that for all $S'\subseteq S$:
$$\hat f(S')=1-f(S- S').$$
Or, in other words, $\hat{f}(x) = \bar{f}(\bar{x})$.  
Given a boolean hypothesis class $H$, define $\hat{H} = \{\hat{f}: f \in H\}$.
For example, the dual of the class of monotone $\log(n)$-DNF formulas is
the class of monotone $\log(n)$-CNF
formulas. The set of monotone functions is closed under dual.

\begin{theorem}Let $H$ be a boolean concept class with dual $\hat H$.
  If, given value oracles for any $f\in H$ and $g\in \hat H$, 
  the optimal allocation $S',S''$ can be elicited using $M$ value
  queries, then a superset query for a target $f^* \in H$ can be
  simulated using $M+2$ queries to a value oracle for $f^*$.
\end{theorem}

\begin{proof}Suppose that
% $f^*$ is the target concept and 
one wants to
perform a superset query with $g\in H$. First, compute $\hat g\in \hat
H$.  Then, perform preference elicitation on $f^*,\hat g$.  If this
procedure returns an allocation satisfying both agents, this means we
have an $x$ such that $f^*(x)=1$ and $\hat{g}(\bar{x}) = 1$.  But,
$\hat{g}(\bar{x}) = \bar{g}(x)$ so this means that $x$ is a
counterexample to the superset query.  On the other hand, if the
elicitation procedure fails to satisfy both agents then no such $x$
exists, so the superset query can return ``true'' in this case.
\qed
\end{proof}

\begin{corollary}
  If $H$ is a subclass of monotone DNF that is closed under removal of
  terms, and if preference elicitation for $(H,\hat{H})$ can be
  performed in $M$ queries, then $H$ is exactly learnable from a
  number of value queries that is polynomial in $n$, $M$, and the
  number of terms in the target monotone DNF.
\end{corollary}

\section{Boolean-Valued Versus Real-Valued Elicitation}

% {\tt [I uncommented this out but didn't go through it -- AB]}

It might seem that eliciting real-valued preference functions would
generally be much more difficult than eliciting boolean preferences.
In this section, we show that---under certain conditions---the number
of value queries necessary for elicitation of real-valued preferences
is not that much greater than the number of queries required for
eliciting boolean preferences.

First of all, for any real-valued function class $H$ we define a related
boolean-valued class as follows.
Let $\succ$ be a variable representing 
either the $>$ or $\geq$ relational operator
and let $\POWER(S)$ represent the power set of $S$.
Given a function $f:\POWER(S)\to {\mathbf R}^+$ and an $a\in {\mathbf R}$, 
define $thresh^{\succ}_{f,a}:\POWER(S)\to \{0,1\}$ to be a function such that
$$thresh^{\succ}_{f,a}(S')=\left \{ \begin{array}{ll}
1&\IF f(S')\succ a \\
0&{\mbox{ otherwise}}.
\end{array}\right .
$$
% Similarly, define $thresh^{>}_{f,a}:\POWER(S)\to \{0,1\}$ such that:
% $$thresh^>_{f,a}(S')=\left \{ \begin{array}{ll}
% 1&\IF f(S')> a \\
% 0 &\IF f(S')\leq a
% \end{array}\right .
% $$
A function $f$ is said to project onto a set of boolean-valued
functions $H'$ if for all $a\in
{\mathbf R}$, $thresh^{\geq}_{f,a},thresh^>_{f,a}\in H'$. A set of
functions $H$ is said to project onto a set $H'$ if each $f\in H$
projects onto $H'$. The \defword{boolean projection} of $H$ is the smallest
set of functions that $H$ projects onto.


Now, imagine that $f$ and $g$, the preferences for two agents, are
drawn from $H$.  This problem is closely related to the case where
preferences $f'$ and $g'$ are drawn from $H'$, the boolean projection
of $H$. By considering the ranges of the functions in $H$, it is
sometimes clear that the above two problems are equally hard. We begin
with the observations that when the functions in $H$ all share a small known
domain, it is easy to see that these problems are of similar
difficulty. We will show in the first theorem below that if the ranges
of the functions in $H$ are small sets, then these two problems are
still of similar difficulty.  On the other hand, in the second theorem
of this section, we will show that there exists a real-valued $H$ with a
corresponding boolean projection $H'$ such that exponentially more
value queries are required to perform preference elicitation on $H$
than are required to exactly learn $H'$ from value queries.

%We will consider three types of real-valued preference classes. In the
%first, it will easily , based on the size of the co-domain of the
%functions, that show how the problem of eliciting the optimal
%allocation from two agents whose preferences come from a set of
%real-valued preferences.

\subsection{Single Small Co-Domain}

First of all, suppose that $H$ is such that there exists a small set
$R_H$ which is a co-domain for every function $f\in H$.  That is, for
any $f\in H$, for every $S'\subseteq S$, $f(S')\in R_H$.  Observe that
if the elicitor knows $H$, then it knows $R_H$.  In this scenario, it
is easy to prove that the elicitation of an optimal allocation for
$f,g\in H$ and the elicitation of an optimal allocation for $f',g'\in
H'$, where $H'$ is the boolean projection of $H$, can
be performed using similar numbers of value queries.

Before we describe the proof, we define a \defword{threshold
  query}.  Let both $\succ$ and $\succ'$ be variables taking on
values in $\{>, \geq\}$.  Then a
$(a,b,\succ\succ')$ threshold query is defined as follows: 
Does there exist a set $S'\subseteq
  S$ such that $f(S')\succ a$ and $g(S- S')\succ' b$? If so, return
  $(f(S'),g(S- S'),S')$, otherwise return false.

% We will only need the last of these in this section.

\begin{obs} \label{obs:simthresh}
  Suppose class $H$ has boolean projection $H'$ such that the optimal
  allocation for any $f',g'\in H'$ can be elicited in $k$ value queries.
  Then a threshold query on any $f,g \in H$ can be performed using at
  most $k+2$ value queries.
\end{obs}

\begin{proof}
  Suppose that we are attempting to perform an $(a,b,>\geq)$ threshold
  query on $f$ and $g$, and let $f' = thresh^{>}_{f,a}$ and $g' =
  thresh^{\geq}_{g,b}$.  Then the threshold query should return false
  if and only if no allocation can satisfy both $f'$ and $g'$.  So, we
  simply perform elicitation on $f'$ and $g'$, using value queries to
  $f$ and $g$ to simulate value queries to $f'$ and $g'$ respectively,
  and see if both can be satisfied.  If so, we perform two more
  queries (one each to $f$ and $g$) to determine the actual value
  of this allocation.
%% On the other hand, if both of these functions can be satisfied then the
%%  allocation found can be used to return an appropriate non-false
%%  value from the threshold query by performing a value query on each
%%  of $f$ and $g$.  Finally, since a value query to $f'$ or $g'$ can be
%%  simulated using a value query to $f$ or $g$, respectively, the
%%  optimal allocation for $f',g'$ can be determined using at most $k$
%%  value queries to $f$ and $g$.
%  This is like finding the optimal allocation for
%   $thresh^{\geq}_{f,b}$ and $thresh^{\geq}_{g,b}$, and these two
%   functions are in $H'$ and so this requires $k$ value queries.
%   Observe that a value query can be made on $thresh^{>}_{f,a}$ or
%   $thresh^{\geq}_{g,b}$ by using a value query on $f$ or $g$
%   respectively. After we have found the optimal allocation $S'$, two
%   more queries might be required to find the values $f(S')$ and
%   $g(S- S')$ and verify that the optimal allocation is a
%   solution to the threshold query.
\end{proof}

\begin{obs} \label{obs:singlerange}
  Suppose class $H$ has boolean projection $H'$, and suppose that
  $R_H$ is a co-domain for every function $f\in H$.
  If $|R_H|=m$, and the optimal allocation for two preferences $f',g'\in
  H'$ can be elicited in $k$ value queries, then the optimal allocation for
  any two preferences $f,g\in H$ can be elicited in $(k+2) m^2$ value queries.
\end{obs}

\begin{proof}
  
  The algorithm to elicit the optimal allocation for $f,g\in H$ is as
  follows.  For all $(a,b)\in R_H^2$, perform an $(a,b,\geq\geq)$
  threshold query, and let $X$ be the set of all non-false responses
  $(a,b,S')$ returned by these queries.  Return the allocation $(S'',
  S- S'')$ from the triple $(a'',b'',S'')\in X$ that
  maximizes $a''+b''$.
  
  By the previous observation, all of these threshold queries can be
  simulated using at most $(k+2) m^2$ value queries.  To see that this
  algorithm returns an optimal allocation, let $(S^*, S-
  S^*)$ be a fixed optimal allocation, and define $f^* = f(S^*)$ and
  $g^* = g(S- S^*)$.  Observe that
  $(f^*,g^*)\in R_H^2$, so the algorithm will make
  the threshold query $(f^*,g^*,\geq,\geq)$.
  Furthermore, this query will return some set $S''$ such that $f(S'')
  = f^*$ and $g(S- S'') = g^*$, since such
  an $S''$ exists and since by the optimality of $S^*$ any response
  $(a,b,S'')$ to this query must have $a \leq f^*$ (since
  $b \geq g^*$) and $b \leq g^*$ (since $a \geq f^*$).  
  Thus $X$ contains at least one optimal
  allocation.
%   where\footnote{Note that $f(S'')+g(S- S'')$
%     cannot be greater than $f(S^*)+g(S- S^*)$ because
%     $S^*$,$S- S^*$ is an optimal allocation.}
%   $f(S'')+g(S- S'')=f(S^*)+g(S- S^*)$. Thus, there
%   exists a triplet in $X$ where $a''+b''= f(S^*)+g(S- S^*)$.
%   Moreover, any such triplet will have a set $S''$ such that
%   $f(S'')+g(S- S'')=f(S^*)+g(S- S^*)$.
\end{proof}

\subsection{Many Small Ranges}

We again consider a set of real valued preference functions $H$.
However, we will not assume a finite co-domain shared by all of the
functions $f\in H$. Instead, we will assume that there exists an $m$ such that
for every $f\in H$, the size
of the range\footnote{The size of the range of a function is the
  number of elements in the range. Technically, for a function
  $f:X\rightarrow Y$, the size of the range is $|\{y\in Y:\exists x\in
  X\mbox{ such that }f(x)=y\}|$.} of $f$ is bounded by $m$.

%An example of such a class of preferences are functions where an agent
%is interested in one or zero of a set of $m$ bundles
%$\{S_1,\ldots,S_m\}$, and a value function $v:\{S_1,\ldots,S_m\}\rightarrow {\mathbf R}$.
%Thus,
%$f(S')=\max_{S_i\subseteq S'} v(S_i)$.

%An example of a class of functions where this is not the case is where
%$f(S')=\sum_{S_i\subseteq S'} v(S_i)$. We will discuss this more in
%the next subsection.

Such problems are not as conducive to the easy analysis of the earlier
section.  For instance, given a function $f\in H$, we may not be able
to discover its entire range without a number of queries exponential in
the number of items. However:
\begin{theorem}
  Given an integer $m$ and a set $H$ such that each function $f\in H$
  has a range of size less than $m$, if $H'$ is the boolean projection of $H$,
  and the optimal allocation for $f',g'\in H'$ can be elicited using
  $k$ value queries, then the optimal allocation for $f,g\in H$
  can be elicited using $2+4(k+2)m^2$ value queries.
\end{theorem}

\begin{proof}

%  As in the previous proof, 
  Let $(S^*,S- S^*)$ be any fixed optimal allocation,
  $f^* = f(S^*)$, and $g^* = g(S- S^*)$.
  We give an algorithm that will iteratively construct subsets of
  the ranges of $f$ and $g$ such that, when the construction is
  complete, the final subsets will contain
%  First, we will find a subset of the range of $f$ and a subset of the
%  range of $g$. Later, we will prove that these subsets contain
  $f^*$ and $g^*$, respectively.
  By the analysis of Observation~\ref{obs:singlerange}, if the
  algorithm of that observation is run using the cross product
  of these two subsets in place of $R_H^2$, the algorithm will still
  successfully locate an optimal allocation.

  The full algorithm is as follows:

  \begin{enumerate}
  \item Initialize $R_f=\{f(\emptyset)\}$ and $R_g=\{g(\emptyset)\}$.
  \item \label{itm:threshqueries}For all $(a,b)\in R_f \times R_g$, if
    one has not already done so, perform three threshold queries
    $(a,b,>>)$, $(a,b,>\geq)$, and $(a,b,\geq>)$.
  \item For every triple $(a',b',S')$ returned in the previous step, add
    $a'$ to $R_f$ and $b'$ to $R_g$.
  \item If $R_f$ and $R_g$ increased in size on the previous step, return
    to step~\ref{itm:threshqueries}.
  \item If $R_f$ and $R_g$ did not increase in size, run the algorithm
    of Observation~\ref{obs:singlerange} using
    $R_f \times R_g$ in place of $R_H^2$.
  \end{enumerate}

  Let the final values of $R_f$ and $R_g$ be denoted by
  $R^*_f$ and $R^*_g$, respectively.
  Observe that
  $R^*_f$ is a subset of the range of $f$, because only
  values of $f$ are inserted into it. Similarly, $R^*_g$ is a subset of
  the range of $g$. Thus $|R^*_f\times R^*_g|\leq m^2$. Observe that 2
  value queries are made in step 1, $3|R^*_f\times R^*_g|$ threshold
  queries
  are made in step 2
  (which, by Observation~\ref{obs:simthresh}, can be simulated
  by 
  at most $3(k+2)m^2$ value queries), and, by
  Observation~\ref{obs:singlerange} and the earlier analysis, no more
  than $(k+2)m^2$ value queries are made in step 5. Thus, no more than
  $2+4(k+2)m^2$ value queries are made.
  
  Now, consider the sets $R_f\subseteq R^*_f$ and $R_g\subseteq R^*_g$
  just before the $i$th execution of step~\ref{itm:threshqueries}
  of the algorithm.  We will show below that if at least one of
  $f^*$ and $g^*$ is not contained in $R_f$ and $R_g$, respectively,
  then at least one of these sets will increase in size when this step
  is executed.  Thus, the algorithm will continue iterating
  this step until $f^* \in R_f$ and $g^* \in R_g$.
  
  First, assume that both $f^* \notin R_f$ and $g^* \notin R_g$, and
  let $f^<$ ($g^<$) be the largest value in $R_f$ ($R_g$) that is less
  than $f^*$ ($g^*$).  Note that the value $f^<$ exists\footnote{If $f(\emptyset)=f^*$, then $f^*\in R_f$ at all stages.} because
  $f(\emptyset) \in R_f$ and for all $S'$, $f(\emptyset) \leq f(S')$
  by the monotonicity of preference functions.  Similarly, $g^<$
  exists.  Therefore, at some iteration of the algorithm the threshold
  query $(f^<,g^<,>>)$ will be made, and when it is made it will not
  return ``false'' because $(f^*,g^*,S^*)$ is a valid response.
  Furthermore, any response $(a, b, S')$ must either have $a \leq f^*$
  or $b \leq g^*$, since $a+b \leq f^*+g^*$.  But, by the definition
  of $f^<$ and $g^<$ as well as of the threshold query, this means
  that at least one of $a$ or $b$ is a value that is not contained in
  $R_f$ or $R_g$.  But both $a$ and $b$ will be contained in their
  respective $R^*$ sets.  Therefore, at least one of the conditions
  $R_f \neq R^*_f$ and $R_g \neq R^*_g$ holds, so at least one of
  the sets $R_f$ and $R_g$ must grow during execution $i$ of
  step~\ref{itm:threshqueries}.
  
  Next, consider the case when $f^* \in R_f$ and $g^* \notin R_g$ (the
  remaining case $f^* \notin R_f$ and $g^* \in R_g$ is symmetric).
  Define $g^<$ as above and consider the threshold query
  $(f^*,g^<,\geq >)$.  Reasoning as above shows that this query will
  produce a response $(a,b,S')$ such that $b \notin R_g$.  Thus, in
  all cases when at least one of $f^*$ or $g^*$ is not in its
  respective set, one of the sets grows at
  step~\ref{itm:threshqueries}.

%   where $f(\emptyset)\in R'_f$ and $g(\emptyset)\in R'_g$. In the next
%   part we will prove that if $f(S^*)\notin R'_f$ or $g(S-
%   S^*)\notin R'_g$, then $R'_f\ne R_f$ or $R'_g\ne R_g$. Thus, this
%   will prove that $f(S^*)\in R_f$ and $g(S- S^*)\in R_g$.
%   Define $f'\in R'_f$ to be the largest value in $R'_f$ less than or
%   equal to $f(S^*)$, and $g'\in R'_g$ to be the largest value in
%   $R'_g$ less than or equal to $g(S- S^*)$.
  
%   Suppose that $f\notin R'_f$ and $g\notin R'_g$. Since $f'\in R_f$
%   and $g'\in R_g$, the threshold query $(f',g',>>)$ was made. Observe
%   that $f(S^*)>f'$ and $g(S- S^*)>g'$, so some set $S'$ not
%   necessarily equal to $S^*$ would be returned when the algorithm made
%   this query, and $f(S')\in R_f$ and $g(S- S')\in R_g$.
%   Also, $f(S')> f'$ and $g(S- S')>g'$. However,
%   $f(S')+g(S- S')\leq f(S^*)+g(S- S^*)$, and so
%   either $f(S')\leq f(S^*)$ (implying that $f(S')\notin R_f$) or
%   $g(S- S')\leq g(S- S^*)$ (implying that
%   $g(S- S')\notin R_g$. This implies that $R'_f\ne R_f$ or
%   $R'_g\ne R_g$.
  
%   Another case is $f(S^*)\notin R'_f$ and $g(S- S^*)\in
%   R'_g$, and by considering the query $(f',g',>\geq)$, one can prove
%   that $R'_f\ne R_f$ or $R'_g\ne R_g$. The third case is where
%   $f(S^*)\in R'_f$, and $g(S- S^*)\notin R'_g$, and by
%   considering the query $(f',g',\geq>)$, one can prove that $R'_f\ne
%   R_f$ or $R'_g\ne R_g$. Thus, $f(S^*)\in R_f$ and $g(S-
%   S^*)\in R_g$.

  
%   Now, observe that this means that there exists an $S'$ such that
%   $(f(S^*),g(S- S^*),S')\in X$. Thus, by a very similar
%   argument to the last proof, this algorithm will obtain an optimal
%   allocation.
 

\mazcomment{  
  From this, it will be easy to obtain the optimal allocation in
  $km^2$ queries using the technique from the last proof.
  
  Now, we will start by first setting $R_f=\{f(\emptyset)\}$ and
  $R_g=\{g(\emptyset)\}$. Observe that now there exists $f'\in R_f$
  and $g'\in R_g$ where $f'\leq f(S^*)$ and $g'\leq g(S-
  S^*)$.



  As a byproduct of the algorithm, we will construct $R_f$ and $R_g$,
  subsets of the ranges of $f$ and $g$ respectively. At the end of the
  algorithm, we will be certain that $f(S^*)\in R_f$ and
  $g(S- S^*)\in R_g$. To begin, we initialize
  $R_f=\{f(\emptyset)\}$ and $R_g=\{g(\emptyset)\}$.
  
  Then, we will perform the following four \textbf{threshold queries}
  for all $(a,b)\in R_f\times R_g$.

  A threshold query has one of the following four forms:
  \begin{enumerate}
  \item $(a,b,>>)$ threshold query: Does there exist a set
    $S'\subseteq S$ such that $f(S')>a$ and $g(S- S')>b$? If
    so, return $S'$.
  \item $(a,b,>\geq)$ threshold query: Does there exist a set
    $S'\subseteq S$ such that $f(S')>a$ and $g(S- S')\geq b$?
    If so, return $S'$.
  \item $(a,b,\geq{>})$ threshold query: Does there exist a set
    $S'\subseteq S$ such that $f(S')\geq a$ and $g(S- S')>
    b$? If so, return $S'$.
  \item $(a,b,\geq\geq)$ threshold query: Does there exist a set
    $S'\subseteq S$ such that $f(S')\geq a$ and $g(S- S')\geq
    b$? If so, return $S'$.
  \end{enumerate}
  These queries can be simulated by converting preference elicitation
  protocols for $H'$ into threshold queries for $H$. If the optimal
  allocation $(S',S- S')$ for
  $thresh^{\geq}_{f,a},thresh^{\geq}_{g,b}\in H'$ is 2, then the
  threshold query $a,b,\geq\geq$ should return $S'$. There are $k$
  queries required to perform the elicitation, and two queries
  required to determine if the optimal allocation is 2.
  
  Observe that as a byproduct of this algorithm, we learn $f(S')$ and
  $g(S- S')$. If $f(S')\notin R_f$, then we add $f(S')$ to
  $R_f$. If $g(S- S')\notin R_g$, then we add $g(S-
  S')$ to $R_g$. Then we perform any threshold queries on $R_f\times
  R_g$ that we have not already performed.

  Finally, we return the set $S'$ from a positive 
  $(a,b,\geq\geq)$ query that maximized $a+b$.

  Now we will analyze the algorithm.

  First, if $f^*\in R_f$ and $g^*\in R_g$, then the $(f^*,g^*,\geq\geq)$
  query we perform will return the optimal allocation. Thus, we will have
  found the optimal allocation if $f^*\in R_f$ and $g^*\in R_g$.

  Secondly, we prove that $f^*\in R_f$ and $g^*\in R_g$.
  
  Define $f'$ to be the greatest value in $R_f$ less than or equal to
  $f(S^*)$. Define $g'$ to be the greatest value in $R_g$ less than or
  equal to $g(S- S^*)$. Observe that $f'$ and $g'$ are well
  defined because $f(\emptyset)\in R_f$ and $g(\emptyset)\in R_g$. We
  will prove by contradiction that they are equal to $f(S^*)$ and
  $g(S- S^*)$ respectively.
  
  If $f'<f(S^*)$ and $g'<g(S- S^*)$, then the query
  $(f',g',>>)$ would have returned some set $S''$, because the optimal
  allocation would be a possible set.  Observe that by the definition
  of $S''$, $f(S'')>f'$ and $g(S'')>g'$. Observe that $f(S'')\in R_f$
  and $g(S- S'')\in R_g$, or the algorithm would not have
  terminated.  Thus, by the definition of $f'$ and $g'$,
  $f(S'')>f(S^*)$, and $g(S- S'')>g(S- S^*)$. But,
  this would imply that $S^*,S- S^*$ was not an optimal
  allocation.
  
  Using a similar argument, we can prove that it cannot be the case
  that $f'<f(S^*)$ and $g'=g(S- S^*)$, using the
  $(f',g',>\geq)$ query.  Also, it cannot be the case that $f'=f(S^*)$
  and $g'<g(S- S^*)$. Thus, $f^*\in R_f$ and $g^*\in R_g$.
}
\end{proof}

\mazcomment{
Define $D_f$ to be the possible values taken by $f$, and $D_g$ to be
the possible values taken by $g$. At some time, we have observed the
values $D'_f$ for $f$ and $D'_g$ for $g$. Define $D''_f=D'_f\cup \{0\}$,
and $D''_g=D'_g \cup \{0\}$. As we find new values, for
all $a\in D''_f$, for all $b\in D''_g$, we perform
the threshold queries $(a,b,>>)$, $(a,b,>\geq)$, $(a,b,\geq>)$, and
$(a,b,\geq \geq)$. Whenever we perform a query of this form we add the
values for the agents of the resulting allocation to the sets $D''_f$
and $D''_g$. Since $|D''_f|\leq m+1$ and $|D''_g|\leq m+1$, four threshold 
queries are done per pair, and each threshold query is $k+2$ value queries,
then a total of $4(k+2)(m+1)^2$ value queries are used.


Suppose that $(S^*,S- S^*)$ is an optimal allocation. Define
$a^*=f(S^*)$, and $b^*=g(S- S^*)$. If $a^*\in D''_f$, and $b^*\in D''_g$,
then we performed a threshold query $(a^*,b^*,\geq \geq)$ and found
an optimal allocation. Now, we prove by contradiction that $a^*\in
D''_f$ and $b^*\in D''_g$.

If this is not the case, there are three possibilities for the final sets $D''_f$ and $D''_g$:
\begin{enumerate}
\item $a^*\notin D''_f$ and $b^*\notin D''_g$: Assume that $a'$ is the
greatest element in $D''_f$ less than $a^*$, and $b'$ is the greatest
element in $D''_g$ less than $b^*$. Suppose that the answer to the
query $(a',b',>>)$, was a set $S''$, and define $a''=f(S'')$ and
$b''=g(S- S'')$. Because we are finished, $a''\in D''_f$ and $b''\in
D''_g$. If $a''>a^*$ and $b''>b^*$, then $S^*$ is not an optimal
allocation. If $a''< a^*$, then $a'$ was not the greatest element in
$D''_f$ less than $a^*$. If $a''=a^*$, then $a^*\in D''_f$.  Similarly
for $b''<b^*$ and $b''=b^*$.
\item $a^*\in D''_f$ and $b^*\notin D''_g$: Assume that $b'$ is the
greatest element in $D''_g$ less than $b^*$. Consider the query
$(a^*,b',\geq{>})$. Since $a^*\in D''_f$
and $b'\in D''_g$, the query was asked. The answer must be positive, 
so suppose the set returned was $S''$. Define $a''=f(S'')$ and $b''=g(S- S'')$. 
$b''\in D''_f$, because the value of all answers are added to $D''_f$ and
$D''_g$.
Since $a''+b''\leq a^*+b^*$, but $a''\geq a^*$, then $b''\leq b^*$. However,
$b''>b'$, and so this is a contradiction of the definition of $b'$.
\item $a^*\notin D''_f$ and $b^*\in D''_g$: This is symmetric to the previous case.
\end{enumerate}
}

\subsection{When Real Values Make a Problem More Difficult}

%An observation. This comes under the category of too obvious for a
%conference paper, but necessary for the journal version.


\begin{theorem}
  There exists a class of real-valued functions that requires $2^n-1$
  value queries to elicit while its boolean projection requires at most
  $n+1$ value queries to exactly learn.
\end{theorem}

\begin{proof}

% Proof(existence proof by example):


%Define $S$ to be the set of all items, and $N$ to be the number of items.

Imagine that the items are ``more or less'' unrelated. In particular, each
item has a basic value in $\{1,2,4,8,\ldots,2^{n-1}\}$. 
For all $a\in S$, define $V(a)$ to be the basic value of $a$, and
assume that this mapping is known.
For all $S'\subseteq S$, define $V(S')=\sum_{a\in S'} V(a)$.
Thus, the basic value of any set is the sum of the basic values in
that set. Observe that for any $S'\subseteq S$, 
$V(S')+V(S- S')=2^n-1$.

Now, each agent has a special set that they value slightly more than
other agents do. Thus, for all $S',S''\subseteq S$, define
$f_{S'}(S'')=V(S'')$ if $S'\ne S''$, and
$f_{S'}(S')=V(S')+\frac{1}{2}$.  The class of preferences of interest
is therefore
$\{f_{S'}\}_{S'\subseteq S}$.

In order to determine the optimal allocation when preferences are
drawn from this class, the elicitor must find
the special set for one agent.  
And in the worst case it requires $2^n-1$ value queries
in order to find a special set, since the only information
obtained from a value query on a non-special set is that it is not
special.  Therefore, $2^n-1$ value queries are required to
elicit this preference class.

Now, consider the boolean projection of this class. For all $a\in R$,
for all $S'\subseteq S$, define $g_{a}(S')$ to be true if and only if
$V(S')\geq a$. Then the projection can be represented as $\{g_a\}_{a\in
  \{0,\ldots,2^n\}}$.
Now, using value queries, we can perform a binary search for the value
of $a$ defining a target member of this class.
Thus, we can exactly learn a target $g$ in the boolean projection with
at most $n+1$ value queries.
\end{proof}

\mazcomment{

Open problem solved and uninteresting.

Now, observe that this class of functions is not closed under a relabeling of the items. That is, there exists a function $f\in \{f_{S'}\}_{S'\subseteq S}$ and a bijection $b:S\rightarrow S$ such that
$f\circ b\notin \{f_{S'}\}_{S'\subseteq S}$.


\begin{open}  
  Does there exist a class of functions closed under a relabeling that cannot be
  elicited in a time polynomial in $N$, but whose boolean image can be
  elicited?
\end{open}

}

One point to observe is that it is easy to approximate any function
with an exponential number of values with a function with a polynomial
number of values. However, one must be careful when one computes an
allocation that is only approximately optimal, because the
traditional techniques to motivate the agents to answer truthfully
(which we describe in the next section) will no longer work.

\section{Truthfulness and VCG} \label{sec:vcg}

In combinatorial auctions and mechanism design, one key issue that
arises is that bidders have their own interests: they each want to
receive as valuable a bundle as possible, and therefore may lie in
their responses if they perceive it to be to their advantage.  For
example, if the auctioneer is not going to actually charge the bidders
anything for the bundles they get, then bidders have an incentive to
report overly high valuations, in order to make the auctioneer think
that social welfare will be improved by giving more to them.  On the
other hand, if the bidders are charged exactly the valuations that
they report, then they have an incentive to underbid, in the hope of
making a profit (paying less for a bundle than it is actually worth to
them).\footnote{Throughout this paper we have let each bidder $i$ have
some valuation function $f_i$ from bundles of items to reals.  This
notation implicitly makes the following common economic assumptions:
(1) {\em private values}: bidder $i$ knows $f_i$ (in other words, the {\em
function} $f_i$ does not depend on the other bidders in any way); and
(2) {\em no externalities}: bidder $i$ does not care who gets the items
that $i$ does not get.  For the truthfulness discussion we
additionally make the common economic assumption (3) {\em quasilinear
preferences}: the utility that bidder $i$ tries to maximize is
$u_i(S_i, p_i) = f_i(S_i) - p_i$, where $S_i$ is the set of items that
$i$ gets and $p_i$ is the total price that $i$ has to pay.}
%
In preference elicitation, the issue of motivating the bidders to
answer queries truthfully is exacerbated by the fact that the
elicitor's queries leak information to the bidder about the answers
that other bidders have given.  

Recently, a methodology was proposed by which elicitors can be made
incentive compatible in the sense that every bidder answering the
queries truthfully is an {\em ex post
equilibrium}~\citep{Conen01:Preference}.\footnote{This means that
bidding truthfully is each bidder's best strategy (for any prior
probability distribution that he may hold about the other bidders)
given that the other bidders bid truthfully.  In other words, truthful
bidding strategies form a Nash equilibrium even in hindsight.  This
does not mean that bidding truthfully is a dominant strategy: if
others bid insincerely, one may also do better by bidding insincerely.
For example, in a 2-bidder setting, if bidder 1's strategy involves
dropping out (bidding zero from then on) whenever it receives a
particular query stream, then it can be bidder 2's best strategy to
answer queries in a way that causes the elicitor to submit that query
stream to bidder 1.  In summary, implementation in {\em ex post}
equilibrium is stronger than implementation in Nash equilibrium, but
weaker than implementation in dominant strategies.} This is
accomplished by organizing the mechanism so that if all the bidders
answer truthfully, the final allocation and payments follow the {\em
Vickrey-Clarke-Groves scheme
(VCG)}~\citep{Vickrey61,Clarke71:Multipart,Groves73:Incentives}.  In
this scheme (the Clarke version), the amount bidder $i$ has to pay
is the sum of others' revealed valuations for the bundles they get had
bidder $i$ not participated, minus the sum of others' revealed
valuations for the bundles they get in the actual optimal allocation.
The elicitor can determine these payments by asking enough queries to
be able to determine the welfare maximizing allocation overall, and
{\em by asking extra queries to determine the welfare maximizing
allocation for the auctions where each agent is ignored in turn}.  The
essence of the argument is that the auction in which agent $i$ is
removed serves only to determine agent $i$'s payment, and therefore in
this auction there is no motivation for any of the participating
agents to lie.  This then means that the payments given to the bidders
can be assumed to be the correct VCG payments, which then implies by
standard VCG arguments that the optimal strategy for the bidders in
the first auction is to tell the truth as well.  Conceptually, one
could think of $k +1$ ``elicitors'', each working to solve one of
these problems.
%%However, these ``elicitors''
%%can use the same data structure for assimilating the results, which
%%leads to the advantage that queries answered for one ``elicitor'' can
%%help another ``elicitor'' on its problem.  
Once all of the ``elicitors'' have found their welfare maximizing
allocations respectively, the process can terminate.  
%% The notion of multiple ``elicitors'' is just for conceptual clarity of this
%% presentation; in practice there would be only one elicitor asking all
%% of the queries.  
Note that the extra overhead of motivating the
bidders to bid truthfully is just solving $k$ additional elicitation
problems beyond the original elicitation problem.  Therefore, if
elicitation can be done in a polynomial number of queries, then so can
elicitation that motivates the bidders to answer the queries
truthfully.
\mazcomment{
\subsection{Approximately Optimal Elicitation}

\begin{theorem}
  Suppose for some preference class $H$, for some $\epsilon<1$,
  \textit{assuming the agents are truthful} in $k$ value queries to
  $f$ and $g$ one can elicit a set $S'$ such that $f(S')+g(S-
  S')\geq (1-\epsilon)\max_{S^*\subseteq S}\left (f(S^*)+g(S-
    S^*)\right )$. Then one can construct a mechanism with $k+4$ value
  queries where there exists a deterministic Nash equilibrium where
  $f(S'')+g(S\subseteq S'')]\geq
  (1-\epsilon)\max_{S^*\subseteq S}\left (f(S^*)+g(S-
    S^*)\right )$, $S''$ being the allocation found by the
  mechanism.
\end{theorem}

\begin{proof}
  
  Our mechanism will be close to the VCG mechanism. The basic idea is
  that if an agent lies, then in expectation it will only improve the
  public good.
  
  \begin{enumerate}
  \item We will run the mechanism that assumes that the agents are
    truthful.  We will use its output, $S'$, as the allocation.
    Observe that there is no guarantee that the agents were truthful
    in this stage.
  \item We will privately ask $f$ about $f(S')$ and $f(S)$.
  \item We will privately ask $g$ about $g(S- S')$ and
    $g(S)$.
  \item We charge the $f$ agent $g(S)-g(S- S')$.
  \item We charge the $g$ agent $f(S)-f(S')$.
  \end{enumerate}
  
  The key to this mechanism is that, most likely we could obtain
  $f(S')$ and $g(S\subseteq S')$ in the first step. However, we will
  not, because we wish to give $f$ and $g$ to be truthful in the
  second and third steps even if the were not in the first steps. In
  fact, it is crucial to not even insist on consistency between the
  first and second stage and between the second and third stage.
  
  Thus, the agents have no motivation to lie in stages two and three,
  because their answers in these stages will not affect them. Thus, we
  will consider equilibria where both agents tell the truth in stages
  two and three.
  
  Thus, observe that if agent $f$ tells the truth in stage 2, then the
  utility of agent $g$ is $f(S')+g(S\subseteq S')-f(S)$. Since it
  cannot affect $f(S)$, if it lies, it will be to increase
  $f(S')+g(S\subseteq S')$ in expectation, given the strategy of $f$.
  
  Similarly, if agent $g$ tells the truth in stage 3, then agent $f$
  will only strategize to increase $f(S')+g(S\subseteq S')$. Since
  this stage is fully cooperative, then the strategy that maximizes
  everyone's utility is a Nash equilibrium. Since truthfulness obtains
  at least $(1-\epsilon)\max_{S^*\subseteq S}\left(f(S^*)+g(S\subseteq
    S^*)\right)$, there must exist a Nash equilibrium that achieves at
  least that much.
\end{proof}

Now, if we know that the agent's preferences are non-negative and
monotonic, then we can insist that in stages two and three
$f(S')<f(S)$ and $g(S\subseteq S')<g(S)$, and thus the mechanism
becomes weakly budget-balanced and individually rational, but is still
not truthful in the first stage.

}



\section{Subsequent Work}

Since the conference (COLT-03) version of this paper appeared, a
significant amount of closely related work has been done.  In this
section we summarize that work.

One of the oldest techniques for preference elicitation is an
ascending auction.  An ascending auction can be considered to be a
sequence of increasing demand queries, where if one asks a query 
$w'$ after a query $w$, then it must be the case that for all $i$,
$w'_i \geq w_i$.  In the conference (COLT-03) version of this paper we 
presented the following problem as an interesting open question: 

\begin{open}
Does there exist a preference elicitation problem that is hard (or
impossible) to elicit using an ascending auction but easy to elicit
using demand queries?
\end{open}

Since then, this question has been answered, and the answer is
affirmative.  \citet{Nisan03:Power} presents a 2-item auction
where no ascending 
item-price auction can determine the optimal allocation (using {\em any}
number of queries), but the optimal allocation can easily be determined
using (nonascending) item-price demand queries.

On the other hand, if {\em bundle-price} demand queries are allowed
--- i.e., prices are not assigned to items only, but potentially also to
bundles --- then ascending auctions exist that always determine the
optimal allocation (using potentially an exponential number of queries), at
least if each bidder is assumed to act
truthfully~\citep{Parkes02:Ascending,Ausubel02:Ascending}.  As pointed
out by \citet{Nisan03:Power}, it remains an open question whether
there exists an ascending bundle-price auction that always determines
the optimal allocation if the auction is restricted to being {\em
anonymous}, that is, at any time, the price of a bundle is the same for
each agent.  Bundle-price demand queries are quite powerful: as
mentioned in footnote \ref{footnote:dq}, one can use them to 
efficiently elicit monotone DNF formulas, and this fact as well as
other results on these queries are given by \citet{Lahaie04:Applying}.

As to preference elicitation using value queries only, new valuation
classes learnable in a polynomial number of queries have been
introduced in \citet{Conitzer03:Combinatorial} and
\citet{Santi04:Towards}.  These include valuations where items have at
most $k$-wise dependencies, and certain other valuations.
Furthermore, if two classes of valuations are each learnable in a
polynomial number of queries, then so is their union---even though the
elicitor does not know in advance in which of the two classes (or
both) the bidder's valuation belongs.
\citet{Santi04:Towards} also present severely restricted valuation
classes where learning nevertheless requires an exponential number of
value queries.  First steps toward a characterization of polynomial
learnability of valuation functions are also given.


\section{Conclusions and Open Problems}
In machine learning, one's objective is nearly always to learn or
approximately learn some target function.  In this paper, we relate
this to the notion of preference elicitation, in which the goal
instead is to find the optimal partitioning of some set of items among
the bidders.  In the case of two bidders, preference elicitation can
be thought of as a learning problem with {\em two} target functions
$f$ and $g$, where the goal is rather than necessarily learning $f$ and
$g$ to instead find the example $x$ that maximizes $f(x)+g(\bar{x})$.

We now describe several open problems left by this work.  We begin
with a problem stated in Section \ref{sec:DNF}.
\addtocounter{open}{-1}
\begin{open}
Can preferences expressible as polynomial-size DNF formulas be
elicited in $2^{O(\sqrt{n})}$ value queries or demand queries?
\end{open}

A somewhat fuzzier question related to our results on $\log(n)$-DNF
is the following.  Our algorithm in this case was non-adaptive: the
questions asked did not depend on answers to previous questions.  It
seems natural that for some classes adaptivity should help.  In fact,
it is not hard to generate artificial examples in which this is the
case.  However, we know of no natural example having this property.
\begin{open}
Are there natural classes of functions for which exact learning is
information-theoretically hard, preference elicitation via a
non-adaptive algorithm is hard (i.e., an algorithm in which the questions can
all be determined in advance) but elicitation by an adaptive algorithm
is easy. 
\end{open}

% Removed as per Tuomas's request
\mazcomment{
One of the oldest techniques for preference elicitation is an
ascending auction.  An ascending auction can be considered to be a
sequence of increasing demand queries, where if one asks a query 
$w'$ after a query $w$, then it must be the case that for all $i$,
$w'_i \geq w_i$.  One interesting open question is: 

\begin{open}
Does there exist a preference elicitation problem that is hard (or
impossible) to elicit using an ascending auction but easy to elicit
using demand queries?
\end{open}
}


\acks{This material is based upon work supported under NSF grants
CCR-0105488, ITR CCR-0122581, CCR-0209064, ITR IIS-0081246, and ITR
IIS-0121678.  Any opinion, findings, conclusions or recommendations
expressed in this publication are those of the authors and do not
necessarily reflect the views of the National Science Foundation.
Tuomas Sandholm is also supported by a Sloan Fellowship.  We would
like to thank the referees for their helpful comments.}

\begin{thebibliography}{36}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Andersson et~al.(2000)Andersson, Tenhunen, and
  Ygge]{Andersson00:Integer}
Arne Andersson, Mattias Tenhunen, and Fredrik Ygge.
\newblock Integer programming for combinatorial auction winner determination.
\newblock In {\em Proceedings of the Fourth International Conference on
  Multi-Agent Systems (ICMAS)}, pages 39--46, Boston, MA, 2000.

\bibitem[Angluin(1988)]{An88}
Dana Angluin.
\newblock Queries and concept learning.
\newblock {\em Machine Learning}, 2\penalty0 (4):\penalty0 319--342, 1988.

\bibitem[Angluin et~al.(1993)Angluin, Hellerstein, and Karpinski]{AnHeKa93}
Dana Angluin, Lisa Hellerstein, and Marek Karpinski.
\newblock Learning read-once formulas with queries.
\newblock In {\em Journal of the ACM}, volume~40, pages 185--210, 1993.

\bibitem[Ausubel and Milgrom(2002)]{Ausubel02:Ascending}
Lawrence~M. Ausubel and Paul Milgrom.
\newblock Ascending auctions with package bidding.
\newblock {\em Frontiers of Theoretical Economics}, 1, 2002.
\newblock No. 1, Article 1.

\bibitem[Bikhchandani et~al.(2001)Bikhchandani, de~Vries, Schummer, and
  Vohra]{BDSV01}
Sushil Bikhchandani, Sven de~Vries, James Schummer, and Rakesh~V. Vohra.
\newblock Linear programming and {V}ickrey auctions, 2001.
\newblock Draft.

\bibitem[Bikhchandani and Ostroy(2001)]{Bik-Ostroy:01}
Sushil Bikhchandani and Joseph~M. Ostroy.
\newblock The package assignment model.
\newblock UCLA Working Paper Series, mimeo, 2001.

\bibitem[Blumer et~al.(1987)Blumer, Ehrenfeucht, Haussler, and Warmuth]{BEHW87}
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K.~Warmuth.
\newblock Occam's razor.
\newblock {\em Information Processing Letters}, 24:\penalty0 377--380, April
  1987.

\bibitem[Clarke(1971)]{Clarke71:Multipart}
Edward H.~Clarke.
\newblock Multipart pricing of public goods.
\newblock {\em Public Choice}, 11:\penalty0 17--33, 1971.

\bibitem[Conen and Sandholm(2001)]{Conen01:Preference}
Wolfram Conen and Tuomas Sandholm.
\newblock Preference elicitation in combinatorial auctions: Extended abstract.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 256--259, Tampa, FL, October 2001.
\newblock A more detailed description of the algorithmic aspects appeared in
  the IJCAI-2001 Workshop on Economic Agents, Models, and Mechanisms, pp.
  71--80.

\bibitem[Conen and Sandholm(2002{\natexlab{a}})]{Conen02:Differential}
Wolfram Conen and Tuomas Sandholm.
\newblock Differential-revelation {VCG} mechanisms for combinatorial auctions.
\newblock In {\em AAMAS-02 workshop on Agent-Mediated Electronic Commerce
  (AMEC)}, Bologna, Italy, 2002{\natexlab{a}}.
\newblock Springer Lecture Notes in Computer Science LNCS 2531.

\bibitem[Conen and Sandholm(2002{\natexlab{b}})]{Conen02:Partial}
Wolfram Conen and Tuomas Sandholm.
\newblock Partial-revelation {VCG} mechanism for combinatorial auctions.
\newblock In {\em Proceedings of the National Conference on Artificial
  Intelligence (AAAI)}, pages 367--372, Edmonton, Canada, 2002{\natexlab{b}}.

\bibitem[Conitzer et~al.(2003)Conitzer, Sandholm, and
  Santi]{Conitzer03:Combinatorial}
Vincent Conitzer, Tuomas Sandholm, and Paolo Santi.
\newblock Combinatorial auctions with {$k$}-wise dependent valuations,
October 2003.
\newblock Draft.

\bibitem[Fujishima et~al.(1999)Fujishima, Leyton-Brown, and
  Shoham]{Fujishima99:Taming}
Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham.
\newblock Taming the computational complexity of combinatorial auctions:
  Optimal and approximate approaches.
\newblock In {\em Proceedings of the Sixteenth International Joint Conference
  on Artificial Intelligence (IJCAI)}, pages 548--553, Stockholm, Sweden,
  August 1999.

\bibitem[Groves(1973)]{Groves73:Incentives}
Theodore Groves.
\newblock Incentives in teams.
\newblock {\em Econometrica}, 41:\penalty0 617--631, 1973.

\bibitem[Hoos and Boutilier(2001)]{Hoos01:Bidding}
Holger Hoos and Craig Boutilier.
\newblock Bidding languages for combinatorial auctions.
\newblock In {\em Proceedings of the Seventeenth International Joint Conference
  on Artificial Intelligence (IJCAI)}, pages 1211--1217, Seattle, WA, 2001.

\bibitem[Hudson and Sandholm(2004)]{Hudson04:Effectiveness}
Benoit Hudson and Tuomas Sandholm.
\newblock Effectiveness of query types and policies for preference elicitation
  in combinatorial auctions.
\newblock In {\em International Conference on Autonomous Agents and Multi-Agent
  Systems}, New York, NY, USA, 2004.
%%\newblock Early versions: CMU tech report CMU-CS-02-124, AMEC-02, SITE-02.

\bibitem[Lahaie and Parkes(2004)]{Lahaie04:Applying}
Sebasti\'{e}n Lahaie and David Parkes.
\newblock Applying learning algorithms to preference elicitation.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, New York, NY, 2004.

\bibitem[Lehmann et~al.(2002)Lehmann, O'{C}allaghan, and
  Shoham]{Lehmann02:Truth}
Daniel Lehmann, Lidian~Ita O'{C}allaghan, and Yoav Shoham.
\newblock Truth revelation in rapid, approximately efficient combinatorial
  auctions.
\newblock {\em Journal of the ACM}, 49\penalty0 (5):\penalty0 577--602, 2002.
%%\newblock Early version appeared in ACMEC-99.

\bibitem[Naor and Naor(1990)]{NaorNa90}
Joseph Naor and Moni Naor.
\newblock Small-bias probability spaces: Efficient constructions and
  applications.
\newblock In {\em Proc. 22nd Annual ACM Symposium on Theory of Computing},
  pages 213--223, Baltimore, 1990.

\bibitem[Nisan(2000)]{Nisan00:Bidding}
Noam Nisan.
\newblock Bidding and allocation in combinatorial auctions.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 1--12, Minneapolis, MN, 2000.

\bibitem[Nisan(2003)]{Nisan03:Power}
Noam Nisan.
\newblock The power and limitations of item price combinatorial auctions, 2003.
\newblock Slides from the FCC Combinatorial Bidding Conference, Queenstown, MD,
  Nov. 21--23.

\bibitem[Nisan and Ronen(2000)]{Nisan00:Computationally}
Noam Nisan and Amir Ronen.
\newblock Computationally feasible {VCG} mechanisms.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 242--252, Minneapolis, MN, 2000.

\bibitem[Nisan and Segal(2003)]{Nisan03:Lindahl}
Noam Nisan and Ilya Segal.
\newblock The communication requirements of efficient allocations and
  supporting {L}indahl prices, 2003.
\newblock Working Paper (version: March 2003).

\bibitem[Parkes(1999{\natexlab{a}})]{Parkes99:iBundle}
David~C. Parkes.
\newblock {iBundle}: An efficient ascending price bundle auction.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 148--157, Denver, CO, November 1999{\natexlab{a}}.

\bibitem[Parkes(1999{\natexlab{b}})]{Parkes99:Optimal}
David~C. Parkes.
\newblock Optimal auction design for agents with hard valuation problems.
\newblock In {\em Agent-Mediated Electronic Commerce Workshop at the
  International Joint Conference on Artificial Intelligence}, Stockholm,
  Sweden, 1999{\natexlab{b}}.

\bibitem[Parkes and Ungar(2002)]{Parkes02:Ascending}
David~C. Parkes and Lyle Ungar.
\newblock An ascending-price generalized {V}ickrey auction, 2002.
\newblock Draft, Jun.

\bibitem[Rothkopf et~al.(1998)Rothkopf, Peke{\v{c}}, and
  Harstad]{Rothkopf98:Computationally}
Michael~H. Rothkopf, Aleksandar Peke{\v{c}}, and Ronald~M. Harstad.
\newblock Computationally manageable combinatorial auctions.
\newblock {\em Management Science}, 44\penalty0 (8):\penalty0 1131--1147, 1998.

\bibitem[Sandholm(2002{\natexlab{a}})]{Sandholm02:Algorithm}
Tuomas Sandholm.
\newblock Algorithm for optimal winner determination in combinatorial auctions.
\newblock {\em Artificial Intelligence}, 135:\penalty0 1--54, January
  2002{\natexlab{a}}.
%% \newblock First appeared as an invited talk at the First International
%%   Conference on Information and Computation Economies, Charleston, SC, Oct.
%%   25--28, 1998. Extended version appeared as Washington Univ., Dept. of
%%   Computer Science, tech report WUCS-99-01, January 28th, 1999. Conference
%%   version appeared at the International Joint Conference on Artificial
%%   Intelligence (IJCAI), pp. 542--547, Stockholm, Sweden, 1999.

\bibitem[Sandholm(2002{\natexlab{b}})]{Sandholm02:eMediator}
Tuomas Sandholm.
\newblock {eMediator}: {A} next generation electronic commerce server.
\newblock {\em Computational Intelligence}, 18\penalty0 (4):\penalty0 656--676,
  2002{\natexlab{b}}.
%% \newblock Special issue on Agent Technology for Electronic Commerce. Early
%%   versions appeared in the Conference on Autonomous Agents (AGENTS-00), pp.
%%   73--96, 2000; AAAI-99 Workshop on AI in Electronic Commerce, Orlando, FL, pp.
%%   46--55, July 1999; and as a Washington University, St. Louis, Dept. of
%%   Computer Science technical report WU-CS-99-02, Jan. 1999.

\bibitem[Sandholm and Suri(2001)]{Sandholm01:Side}
Tuomas Sandholm and Subhash Suri.
\newblock Side constraints and non-price attributes in markets.
\newblock In {\em IJCAI-2001 Workshop on Distributed Constraint Reasoning},
  pages 55--61, Seattle, WA, 2001.

\bibitem[Sandholm et~al.(2001)Sandholm, Suri, Gilpin, and
  Levine]{Sandholm01:CABOB}
Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and David Levine.
\newblock {CABOB}: A fast optimal algorithm for combinatorial auctions.
\newblock In {\em Proceedings of the Seventeenth International Joint Conference
  on Artificial Intelligence (IJCAI)}, pages 1102--1108, Seattle, WA, 2001.

\bibitem[Santi et~al.(2004)Santi, Conitzer, and Sandholm]{Santi04:Towards}
Paolo Santi, Vincent Conitzer, and Tuomas Sandholm.
\newblock Towards a characterization of polynomial preference elicitation with
  value queries in combinatorial auctions.
\newblock In {\em Conference on Learning Theory (COLT)}, Banff, Alberta,
  Canada, 2004.

\bibitem[Smith et~al.(2002)Smith, Sandholm, and Simmons]{Smith02:Constructing}
Trey Smith, Tuomas Sandholm, and Reid Simmons.
\newblock Constructing and clearing combinatorial exchanges using preference
  elicitation.
\newblock In {\em AAAI-02 workshop on Preferences in AI and CP: Symbolic
  Approaches}, pages 87--93, 2002.

\bibitem[Vickrey(1961)]{Vickrey61}
William Vickrey.
\newblock Counterspeculation, auctions, and competitive sealed tenders.
\newblock {\em Journal of Finance}, 16:\penalty0 8--37, 1961.

\bibitem[Wurman and Wellman(2000)]{Wurman00:AkBA}
Peter~R. Wurman and Michael~P. Wellman.
\newblock {AkBA}: A progressive, anonymous-price combinatorial auction.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 21--29, Minneapolis, MN, October 2000.

\bibitem[Zinkevich et~al.(2003)Zinkevich, Blum, and
  Sandholm]{Zinkevich03:Polynomial}
Martin Zinkevich, Avrim Blum, and Tuomas Sandholm.
\newblock On polynomial-time preference elicitation with value queries.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 176--185, San Diego, CA, 2003.

\end{thebibliography}

%\bibliography{dairefs,bibstuff}
\end{document}
