Tuomas Sandholm and Victor Lesser
In multiagent systems, interaction protocols are usually enforced by law. Enforcement is problematic among computational agents, because they may operate under incomplete or different laws, the laws may not be uniformly enforced, and the agents can vanish easily. This paper presents an enforcement free method for carrying out exchanges so that both agents are motivated to abide to their contract. This is achieved by splitting the exchanged goods into partial exchanges so that at each step, both agents benefit more from the future of the exchange than from vanishing with the goods or payment. The conditions for such exchange are presented in general, and the maximum deliveries and payments (for any point in the exchange) are explicitly solved for. Similar analysis is carried out for the case, where the agents’ current actions affect their future contracts. Strategic delaying is also discussed. The paper presents a fast algorithm that will find a sequence of independent partial deliveries in a way that enables unenforced exchange if such a sequence exists. This problem cannot be solved in polynomial time if the partial deliveries are interdependent. Finally, the paper shows that the unenforced exchange scheme hinders unfair renegotiation.