INTELLIGENT MATCHMAKERS

White Paper for Workshop on Research Directions for the Next Generation Internet

Eugene C. Freuder

e-mail: ecf@cs.unh.edu
URL: http://www.cs.unh.edu/ecf.html

Constraint Computation Center
URL: http://www.cs.unh.edu/ccc/

Department of Computer Science
University of New Hampshire
Durham, NH 03824 USA

tel: 603-862-1867
fax: 603-862-3493

Intelligent Matchmakers can be regarded as a third generation tool for
Internet accessibility, where hypertext constitutes the first generation,
and search engines the second. What the Forrester Report calls
"content-focused matchmaker" agents can provide advice to internet
consumers about complex products. These can be commercial products
(automobiles) or information products (web pages). The number of vendors,
choices and options available for these products can be overwhelming. The
Matchmaker provides an efficient link between consumers and products.

The Matchmaker agent can be impartial assistant or a vendor with its own
agenda. The Customer could be a person, but it could also be another
computer agent. In multi-agent systems we envision Matchmakers playing the
role of Customer with other Matchmakers to procure information for their
clients, and Matchmakers seeking compromise solutions for multiple clients.


The reigning paradigm for content-focused matchmaker agents is the "deep
interview", as embodied in Barry Diller's forthcoming Consumer's Edge
website, where the primary mode of interaction is the query, made by the
Customer to the Matchmaker. We believe that a different form of
interaction, exhibited by a more intelligent form of matchmaker, should
predominate.

In our Intelligent Matchmaker paradigm, the primary mode of interaction is
the "suggestion", made by the Matchmaker to the Customer. The Matchmaker
suggests a product to the Customer. The secondary mode of communication is
the "correction", made by the Customer to the Matchmaker, indicating how
the suggestion fails to meets the Customer's needs. We believe this form of
interaction is more natural and shifts more of the burden from the Customer
(who may well be a person) to the Matchmaker.

When we enter a car dealership, or a library, we may be asked a few
preliminary questions, but we are not given a questionnaire. The saleman,
or librarian, soon begins to make suggestions. A Ford Taurus? No, I wanted
something with more cargo room. A John Grisham? No, I wanted something with
more intelligence.

The good salesman and the good librarian will make suggestions that steer
us efficiently to a satisfactory conclusion, with a minimum of effort on
our part. Of course, the criteria for "satisfactory" may vary. As is the
case in conventional information retrieval, there can be some tension
between a desire to obtain a "good enough" solution quickly, and the desire
to obtain an optimal solution, which may take longer. If the salesman first
shows us the Taurus, the best selling car in America, we may drive off with
it. However, a better salesman may awaken our long-buried desire to drive
off in a little two seater sports car.

The key issue for Matchmaker agent will be to decide how best to present
the Customer with proposed solutions. Work at the UNH Constraints
Computation Center is addressing that problem with a constraint-based model
of the matchmaker process.

We model the intelligent matchmaker paradigm using formal methods drawn
from the study of constraint satisfaction problems (CSPs) in artificial
intelligence. The Matchmaker's knowledge base and the Customer's needs are
both modeled as a network of constraints. A "suggestion" corresponds to a
solution of a CSP. A "correction" specifies the Customer constraints that
the proposed solution violates. Repeating the cycle of suggestion and
correction allows the Matchmaker to improve its picture of the Customer's
problem until a suggestion constitutes a satisfactory solution. (We provide
a "description" of the solution; it could also be indexed to a product name
that meets the description.)

The constraint network representation supports the computation of
suggestions and easily incorporates corrections. In computing suggestions
the constraint solving process infers the implications of corrections in a
manner which avoids the need for the Customer to make all constraints
explicit. We believe that this form of model-based representation will be
easier to build and maintain than than the rule or decision tree based
representation that presumably underlies a deep interview matchmaker.

The objective here is to model a situation in which  Customers do not enter
the interaction with a fully explicit description of their needs. They may
be unfamiliar with what is available in the marketplace. They recognize
their constraints during the interaction with the Matchmaker. They cannot
list all their requirements up front, but they can recognize what they do
not want when they see it. We believe this to be a common form of customer
conduct. (Picture yourself browsing through a store or a catalogue, or
interacting with a salesclerk.)

The Matchmaker can facilitate this process by an appropriate choice of
suggestions (partial solutions). Some suggestion strategies may lead to a
satisfactory solution more easily for the user than others, e.g. with fewer
iterations of the suggestion/correction cycle. We are studying suggestion
strategies.

Ease of use is not the only evaluation criteria. For example, in an
environment in which the Matchmaker has an ongoing relationship with the
Customer, it can be desirable for the Matchmaker to learn as much as
possible about the Customer's constraints, to facilitate future
interactions. In our implementation it is possible, in fact it proves
experimentally the norm, for the Matchmaker to come up with a satisfactory
solution before the Matchmaker acquires all of the Customer constraints.
(Some of the constraints will be fortuitously satisfied by the suggestion.)
Thus we use the number of Customer constraints acquired by the Matchmaker
as another performance metric when comparing suggestion strategies.

Notice that this latter metric is somewhat antithetical to the ease of use
criteria. Acquiring many Customer constraints can be viewed as good,
because it facilitates future interaction; however, it also might be viewed
as bad, because it requires more Customer effort (in the form of
corrections). Another dichotomy is the one referred to earlier in which
some suggestions lead to a satisfactory solution quickly, while others lead
to a more satisfactory solution, but at greater "interaction cost" to the
Customer.

In summary:

*Intelligent Matchmakers can effect happy marriages between Next Generation
Internet consumers and Next Generation Internet products.

*Constraint satisfaction methods from artificial intelligence support a
suggestion/correction interaction with the Matchmaker that models efficient
human matchmaking.

*Research is needed to develop Matchmaker Agents that best meet the various
needs of those seeking and providing Next Generation Internet information.