Abstract
We introduce the Multiagent Agreement Problem (MAP)
to represent a class of multiagent scheduling problems.
MAP is based on the Distributed Constraint Reasoning
(DCR) paradigm and requires agents to choose values for
variables to satisfy not only their own constraints, but also
equality constraints with other agents. The goal is to represent
problems in which agents must agree on scheduling
decisions, for example, to agree on the start time of a meeting.
We investigate a challenging class of MAP – private,
incremental MAP (piMAP) in which agents do incremental
scheduling of activities and there exist privacy restrictions
on information exchange. We investigate a range of
strategies for piMAP, called “bumping” strategies. We empirically
evaluate these strategies in the domain of calendar
management where a personal assistant agent must schedule
meetings on behalf of its human user. Our results show
that bumping decisions based on scheduling difficulty models
of other agents can significantly improve performance
over simpler bumping strategies.