This paper reviews six component technologies for automated negotiation and coalition formation.
1. OCSM-contracts in marginal cost based contracting
Different agents may have different resource so they have different abilities to handle the tasks. A model which allow agents to reallocate tasks. Agents make contracting decisions based on marginal cost (I am not very sure what is the marginal cost here). The model also defines how agents reallocate task and how to pay for the changing. The author also gives the proof that the globally optimal task allocation can be reached by any hill-climbing algorithm in a finite number of steps. However, the time cost on a large-scale system is still a problem. [2] gives experimental results.
2. leveled commitment contracts
The contract is binding among agents in traditional negotiation protocols. However, there are events may cause agents decommit. Self-interest agents will decommit when they can get more utility and they will try to avoid the penalty. Thus, the contracts should be able to avoid this situation. Leveled commitment contracts implement the backtracking method for avoiding local optima.
3. anytime coalition structure generation with worst case guarantees
This part discuss the superadditive and how to guarantee the worst cast is within a bound.
4. trading off computation cost against optimization quality within each coalition
5. distributing search among insincere agents
A method for distributing search works among self-interest agents without a trusted third party.
6. unenforced contract execution.
For 4 & 6, I think I need to read again before I write something...
[1] T. Sandholm “Agents in Electronic Commerce: Component Technologies for Automated Negotiation and Coalition Formation” Autonomous Agents and Multi-Agent Systems, 3(1), 73-96. 2000.
[2] M. R. Andersson and T. W. Sandholm, ‘‘Time-quality tradeoffs in reallocative negotiation with combinatorial contract types,’’ in Proceedings of the National Conference on Artificial Intelligence (AAAI), Orlando, FL, 1999, pp. 3-10.
