Bumping strategies for the private incremental multiagent agreement problem

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 con-straints with other agents. The goal is to represent problems in which agents must agree on scheduling decisions, for ex-ample, to agree on the start time of a meeting. We investi-gate a challenging class of MAP – private, incremental MAP (piMAP) in which agents do incremental scheduling of ac-tivities and there exist privacy restrictions on information ex-change. We investigate a range of strategies for piMAP, called bumping strategies. We empirically evaluate these strate-gies in the domain of calendar management where a personal assistant agent must schedule meetings on behalf of its hu-man user. Our results show that bumping decisions based on scheduling difficulty models of other agents can significantly improve performance over simpler bumping strategies