Reviewed by
David L. Sallach
Social Science Research
Computing, The University of Chicago.
I shall meet the snowy North again -
but with changed eyes next time round
...for I learned by now never to expect
what it can not give me
Bob Dylan
There is an interesting and largely productive relationship between agent-based application software and agent-based social simulation. The former is designed to make distributed systems work together effectively, including when they are under contention for limited resources (Rosenschein and Zlotkin 1994, Haddadi 1995, Sandholm and Lesser 1995, Muller 1996 and Stone 2000), while the latter is a research programme designed to generate insights into artificial and natural social processes (cf., Epstein and Axtell 1996, Axelrod 1997 and Cederman 1997). While each approach has productive lines of research, their divergence of purposes means that cross-fertilisation may be limited or difficult.
The subject of this review, Strategic Negotiation in Multiagent Environments by Sarit Kraus, is a focused work that builds upon and refines earlier models of multiagent negotiation. Its contributions are considered and incremental rather than path breaking. Kraus's strategic-negotiation model is based on game-theoretic precedents and, in particular, draws upon and extends Rubinstein's (1982, 1985) model of alternating offers, applying it to various problem areas. Indeed, the range of applications, which includes negotiations about data allocation, resource allocation, task distribution, pollution reduction and hostage release, is one of the strengths of the work.
Within the game-theoretic literature, the basic assumptions upon which Kraus builds are familiar: 1) agents are rational, behave according to (settled) preferences and seek to maximise their utilities, 2) if an agreement is reached, both sides honour it, 3) agents cannot commit themselves to action further in the future than the immediate negotiations, 4) in a situation where accepting an offer has the same utility as opting out, the agent will agree to the offer, and 5) the previous four assumptions comprise a common belief for all participating agents. While these assumptions are far removed from the embodied practices of human agents, they form a 'boundary structure' out of which a variety of computational experiments can arise.
Rosenschein and Zlotkin (1994) define three types of problem domains: task-oriented, state-oriented and worth-oriented, in which each introduces additional complexity to the preceding type. The first involves task-coordination where there are no synergies or adverse side effects. In the state-oriented domain, the interaction of agent choices introduces side effects. If agents share a car, for example, one agent's decision to use the car impacts on its availability to the other. Worth-oriented domains add a function that assigns a 'worth' to each state, greatly increasing the flexibility of negotiation options. Kraus's strategic negotiation model draws upon the worth-oriented domain.
Kraus's most substantial contribution is in the area of time coordination. For Rosenschein and Zlotkin, time does not play an explicit role. For Kraus, in contrast, time preferences are capable of influencing the outcome of the negotiations and, in fact, comprise one of the driving forces of the model.
Kraus evaluates negotiation protocols based on seven criteria: 1) the decision-making process should be distributed, 2) co-ordination should only be based on relevant agent attributes,[1] 3) briefer negotiations are preferred over longer, 4) efficient outcomes are preferred over inefficient, 5) simple processes are preferred to complex, 6) stability in negotiation strategies is valued,[2] and 7) although monetary exchanges may be used to resolve conflicts, protocols that do not rely on money transfers are preferred.[3] His strategic negotiation model meets the first two criteria. Results on the other criteria are more domain specific, but encourage Kraus to regard the model as a unified solution to a wide range of cooperation and coordination problems.
Regarding negotiation time, in the data allocation domain, after a preliminary round of broadcast messages, agents reach agreement rapidly. If there is incomplete information, then an additional revelation phase consisting of one round of broadcast messages is required. In the resource allocation domain, negotiations end in the first or second time periods. However, under incomplete information, one or more agents may opt out, ending negotiations. In the task allocation and pollution domains, if a sequential protocol is used, negotiations end quickly. Using a simultaneous response protocol, an additional phase of broadcast messages is required.
In most problem areas, efficiency is accomplished by agents arriving at Pareto-optimal agreements. However, in the pollution domain, and in the data allocation domain when the simultaneous response protocol is used, agents reach only sub optimal agreements. In one additional case from the resource allocation domain, time pressures result in an agreement that is not Pareto-optimal.
Regarding simplicity, most agent strategies in most domains can be found in polynomial time. However, in the data allocation and pollution domains, heuristics were required to overcome complexity problems. All domains achieved stability by identifying strategies that are in sub game perfect or sequential equilibria. Finally, monetary systems are not needed in most examples. However, in pollution allocation, the best results are achieved through the use of money transfers.
The author rightly concludes that the strategic negotiation model may be of value in a variety of domains including negotiation training, electronic commerce and (it may be added) decision process design. From the perspective of social simulation, however, the varied strengths of this work are nonetheless limited. For research programmes in which agent negotiation is required, but does not serve as the primary research focus, this book will serve as a valuable source of ideas. The efficiencies achieved will assist the researcher in devising an algorithmic representation of negotiation processes.
However, the work reported here is not designed to simulate the process of human negotiation, with its contingencies, novel strategies, indexical responses and endogenously defined practices. To gain insight into naturally occurring negotiation practices, social simulation researchers will have to model the process of meaning construction, maintenance and repair with a more fluid focus, and probably at an entirely different level of abstraction.
There are models that attempt to address such situated complexities: situation theory as a mathematical formalism (Barwise 1989, Devlin 1991, 1994, Devlin and Rosenberg 1993), computational models of interaction (Chapman 1991 and Agre and Rosenschein 1996) as implemented examples, and behavioural or endogenous design (Bryson and Stein 2001, Sallach 2002) as software development strategies. Not all of the works cited represent emergent cooperation, and none address the nuanced complexity of human negotiation in natural settings. But they do begin to address situated action, tacit knowledge and indexical interaction.
A vast dialogue is underway in which insights are being stitched together and used as the basis for computational experiments. Within this broad scheme, the book under review plays a valuable but specialised role.
Notes1 In the examples considered in the book two attributes, agent role in the encounter and agent utility function, are relevant.
2 A strategy is stable when, if all other agents included in the set follow their strategies, it will be beneficial for the focal agent to follow its strategy as well.
3 Maintaining a monetary system consumes resources and efforts that subvert the efficiency of protocol operations.
ReferencesAGRE P. E. and S. J. Rosenschein, editors, 1996. Computational Theories of Interaction and Agency. The M. I. T. Press, Cambridge, MA.
AXELROD R. 1991. The Complexity of Co-operation: Agent-Based Models of Competition and Collaboration. Princeton University Press, Princeton, NJ.
BARWISE J. 1989. The Situation in Logic. CSLI, Stanford, CA.
BRYSON J. and L. A. Stein 2001. Modularity and design in reactive intelligence. In B. Nebel, editor, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001. Morgan Kaufmann, San Francisco, CA.
CEDERMAN L.-E. 1997. Emergent actors in world politics: How states and nations develop and dissolve. Princeton University Press, Princeton, NJ.
CHAPMAN D. 1991. Vision, Instruction and Action. The M. I. T. Press, Cambridge, MA.
DEVLIN K. 1991. Logic and Information. Cambridge University Press, New York, NY.
DEVLIN K. 1994. Situation theory and social structure. In M. Masuch and L. Polos, editors, Knowledge Representation and Reasoning under Uncertainty. Springer-Verlag, Berlin.
DEVLIN K. and D. Rosenberg 1993. Situation theory and co-operative action. In P. Aczel, D. Israel, Y. Katagiri and S. Peters, editors, Situation Theory and Its Applications, Volume 3. CSLI, Stanford, CA.
EPSTEIN J. M. and R. Axtell 1996. Growing Artificial Societies: Social Science from the Bottom Up. The M. I. T. Press, Cambridge, MA.
HADDADI A. 1995. Communication and Co-operation in Agent Systems. Springer-Verlag, Berlin.
MULLER J. P. 1996. The Design of Intelligent Agents: A Layered Approach. Springer-Verlag, Berlin.
ROSENSCHEIN J. S. and G. Zlotkin 1994. Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. The M. I. T. Press, Cambridge, MA.
RUBINSTEIN A. 1982. Perfect equilibrium in a bargaining model. Econometrica, 50:97-109.
RUBINSTEIN A. 1985. A bargaining model with incomplete information about time preferences. Econometrica, 53:1151-1172.
SALLACH D. L. 2002. Situated social ecology: An integrated design hermeneutic. In Proceedings of Agent 2002: Ecology, Exchange and Evolution. Argonne National Laboratory, Argonne, IL.
SANDHOLM T. and V. Lesser 1995. Issues in automated negotiation and electronic commerce: Extending the contract net framework. In M. N. Huhns and M. P. Singh, editors, Readings in Agents. Morgan Kaufmann, San Francisco, CA.
STONE P. 2000. Layered Learning in Multiagent Systems: A Winning Approach to Robotic Soccer. The M. I. T. Press, Cambridge, MA.
Return to Contents
of this issue
© Copyright Journal of Artificial Societies and Social Simulation, 2003