Evolutionary simulation and development environments for innovative agent systems

Work Unit 1 (WU1)

Objective

Evolutionary simulation environments of systems of interacting trade agents are developed and investigated. This work unit focuses on obtaining characteristics in the emergent system behaviour starting from basic assumptions and settings, and the effect of parameter and property settings on the system behaviour and the ways to control these. It also investigates the generation of interaction strategies for trade agents and the effect on the emergent system behaviour. Thus, this work unit enables guidance in the design of agent systems and the generation of strategies of trade agents (``light-weight'' agents).

Approach

The development of evolutionary simulation environments starts from the base of evolutionary computing and economic mechanisms. The behavioural and interaction aspects of agents that we may incorporate in our simulations are amongst others: the design of the specific market situation, negotiation objectives and protocols, learning from other agents, following trends and hypes, passing and using information that becomes available, reputation, fairness, cooperation, and assessing trade-offs. We investigate the effects of models and parameter settings with respect to the following aspects: the realism of the models as compared to existing situations, the computational feasibility and design methodology, and the correspondence between models, their parameters, and the emergent behaviour. Types of emergent behaviour are e.g. dynamics, stability, the formation of (sub)societies, and the existence of (sub)optimal behaviour.

Important examples of the specific application areas are e.g. negotiation, marketplaces, auctions, dynamic pricing, cooperation, distribution, and brokering.

This research addresses large systems of interacting agents; large computer simulations are executed, and several practical cases and concepts are designed, modeled, and investigated.

Currently available deliverables

[0D1.1] Scientific Approaches and Techniques for Negotiation: A Game Theoretic and Artificial Intelligence Perspective
White paper on scientific techniques and approaches for negotiation are overviewed, with respect to the viewpoints of game theory and artificial intelligence. (2000 Q0)

[0D1.2] Multi-Issue Negotiation Processes by Evolutionary Simulation: Validation and Social Extensions
Scientific report on evolutionary agent systems, concerning multi-issue negotiations and the alternating-offers protocol together with a first extension concerning social aspects. (2000 Q1)

[0D1.3] Equilibrium Selection in Alternating-Offers Bargaining Models: The Evolutionary Computing Approach
Scientific report on adaptive agent systems, concerning single-issue negotiations and validation with game theory, including deadline and time-discounting effects. (2000 Q3)

[0D1.4] Evolving Automata Negotiate with a Variety of Opponents (restricted access only)
Scientific report on adaptive agent systems, concerning negotiation strategies against multiple types of opponents. (2000 Q3)

[0D1.5] A Market Mechanism for the KPN Case (restricted access only)
Scientific report on adaptive agent systems, concerning definition of and research on a first market mechanism. Especially, it consists of the design, simulation, and experimentation of the mechanism. (2000 Q4)

[1D1.1] Evolving Automata Negotiate with a Variety of Opponents - II (restricted access only)
Scientific report on automatic development of adaptive negotiation strategies for agents by means of co-evolution and finite automata. First results for the case of adaptive, evolving opponents. (2001 Q1)

[1D1.2a] A Robust Dynamic Pricing Algorithm: The Adaptive Step-Size Derivative Follower (restricted access only)
We study the performance of a derivative follower algorithm with an adaptive step-size (ADF). Unlike a previously proposed ADF variant [2], our algorithm alway converges to the optimal solution if the profit function is strictly concave. We test the performance of our ADF on a dynamic pricing problem. These computational experiments show that our ADF is able to generate high profit levels for a wide range of initial prices and step-sizes. (2001 Q2)

[1D1.2b] Negotiations within a Competitive Market: An Evolutionary Simulation Approach. (restricted access only)
We describe a system for bilateral negotiations, in which artificial agents can negotiate with a number of opponents before reaching an agreement. The negotiations are based on a finite-horizon version of the alternating-offers protocol, and extended to allow for multiple bargaining opportunities. Several issues are negotiated simultaneously. This extension models a competitive market and is closer to realistic settings than the basic negotiation game. We analyze the extended game using an evolutionary simulation, where the strategies of the negotiating agents are generated by an evolutionary algorithm. Symmetric payoffs are obtained in the simulation if agents incur no search costs. We furthermore study the effects of search costs in this game. (2001 Q2)

[2D1.1] Bargaining with Posterior Opportunities: An Evolutionary Social Simulation (restricted access only)
Negotiations have been extensively studied theoretically throughout the years. A well-known bilateral approach is the ultimatum game, where two agents negotiate on how to split a pie or a "dollar": the proposer makes an offer and responder can choose to accept or reject. In this paper a natural extension of the ultimatum game is presented, in which both agents can negotiate with other opponents in case of a disagreement. This way the basics of a competetive market are modelled where for instance a buver can try several sellers before making a purchase decision. The game is investigated using an evolutionary simulation. The outcomes appaer to depend largely on the information available to th agents. We find that if the agents' number of future bargaining opportunities is commonly known, the proposer has the advantage. If this information is held private, however, the responder can obtain a larger share of the pie. For the first case we also provide a game-theoretic analysis and compare the outcome with evolutionary results. Furthermore, the effects of search costs and allowing multiple issues to be negotiated simultaneously are investigated. (2002 Q1-3)