Meeting Agenda Meeting Agenda
COMPUTER SCIENCE SEMINAR
-Thursday, April 11, 1996
Tuomas Sandholm, Dept. Comp. Sci., Univ. Massachusetts
at Amherst, will speak on ``Negotiation among
Computationally Limited Self-Interested Agents''.
TIME: 11:00 a.m.- 12:00 p.m.
ROOM: DC 1302
ABSTRACT
In multiagent systems, computational agents make
contracts on behalf of the real world parties that they
represent. The significance of such systems is likely
to increase due to the developing communication
infrastructure, the advent of electronic commerce, and
the industrial trend toward outsourcing. My research
normatively analyses such negotiations among agents
that try to maximize payoff without concern for the
global good. The most advanced normative theoretical
tools available are game theoretic. However, in game
theory full rationality of the agents is usually
assumed. My work extends these normative approaches to
settings in which computational limitations restrict
each agent's rationality because combinatorial
complexity precludes enumerating and evaluating all
possible outcomes.
Within the subfield of automated contracting, I
extended the contract net framework to work among
self-interested agents. The original contract net
lacked a formal model for making bidding and awarding
decisions, while in my TRACONET system these decisions
are based on marginal cost calculations. I developed an
iterative scheme for anytime task reallocation where
agents pay each other for handling tasks. I uncovered
and solved problems regarding contracting while old
bids are pending. I constructed three new contract
operators and proved that they are necessary and
sufficient for reaching a globally optimal task
allocation in a finite number of contracts. I also
proved that a leveled commitment contracting protocol
enables contracts that are impossible via classical
full commitment contracts. In addition, it enhances the
efficiency of contracts when full commitment contracts
are possible. Finally, I identified and solved problems
of distributed asynchronous implementation.
Within coalition formation, I developed a normative
theory that states which self-interested
computationally limited agents should form coalitions
and which coalition structures are stable. These
prescriptions depend on the performance profiles of the
agents' problem solving algorithms, and differ
significantly from those for fully rational agents. My
theory includes an application independent domain
classification with bounded rational agents, and
relates it to two traditional domain classifications
with fully rational agents.
Within contract execution, unenforced exchange methods
are desirable among computational agents because
litigation is difficult. I developed such a method
based on splitting the exchange into chunks that are
delivered one at a time. I developed two chunking
algorithms as well as a nontrivial sound and complete
quadratic chunk sequencing algorithm. I also derived
the optimal stable strategies for carrying out the
exchange. Finally, I analyzed the role of real-time and
developed deadline methods that do not themselves
require enforcement.
I evaluated these domain independent methods on an
NP-complete distributed vehicle routing problem with
large-scale instances collected from five real-world
dispatch centers. My methods resulted in significant
transportation cost savings on this problem where
classical game theoretic techniques are inapplicable
due to intractability.
COMPUTER SCIENCE SEMINAR
-Monday, April 8, 1996
Darrell Raymond, University of Western Ontario, will
speak on ``Using Partial Orders to Manage Software''.
TIME: 11:00 a.m. - 12:00 p.m.
ROOM: DC 1302
ABSTRACT
Programmers have long relied on tools like make and RCS
to assist in managing medium-sized software projects.
The usefulness of these tools is compromised by the
idiosyncracies and gratuitous differences of their
various implementations. What is lacking is a general
model of the process of building, versioning, and
configuring software. Such a model could serve as a
benchmark for comparing software tools, and would
provide a language with which to describe semantics
independently of implementations. In this talk I
present the beginnings of such a model, based on an
algebra for partial orders. We will see that building
programs can be usefully expressed algebraically, and
that such expressions suggest more general and fruitful
approaches to the problem of managing software.
Logging off workstations when not in use