Agents in electronic commerce: Component technologies for automated negotiation and coalition formation

Automated negotiation and coalition formation among self-interested agents are playing an increasingly important role in electronic commerce. Such age nts cannot be coordinated by externally imposing their strategies. Instead the interaction protocols have to be designed so that each agent is motivat ed to follow the strategy that the protocol designer wants it to follow. Th is paper reviews six component technologies that we have developed for maki ng such interactions less manipulable and more efficient in terms of the co mputational processes and the outcomes: 1. OCSM-contracts in marginal cost based contracting, 2. leveled commitment contracts, 3. anytime coalition structure generation with worst case guarantees, 4. trading off computation cost against optimization quality within each co alition, 5. distributing search among insincere agents, and 6. unenforced contract execution. Each of these technologies represents a different way of battling self-inte rest and combinatorial complexity simultaneously. This is a key battle when multi-agent systems move into large-scale open settings.