(Im)possibility of Safe Exchange Mechanism Design

Abstract

Safe exchange is a key issue in multiagent systems, especially in electronic transactions where nondelivery is a major problem. In this paper we present a unified framework for modeling safe exchange mechanisms. It captures the disparate earlier approaches as well as new safe exchange mechanisms (e.g., reputation, locking). Being an overarching framework, it also allows us to study what is inherently possible and impossible in safe exchange. We study this under different game-theoretic solution concepts, with and without a trusted third party, and with an offline third party that only gets involved if the exchange fails. The results vary based on the generality of the exchange setting, the existence (or creative construction) of special types of items to be exchanged, and the magnitude of transfer costs, defection costs, and escrow fees. Finally, we present an incentive-compatible negotiation protocol for selecting the best safe exchange mechanism when the agents do not know each others' costs for the different alternatives.