Efficient Dynamic Barter Exchange

摘要

We study dynamic matching policies in a stochastic marketplace for barter, with agents arriving over time. Each agent is endowed with an item and is interested in an item possessed by another agent homogeneously with probability p, independently for all pairs of agents. Three settings are considered with respect to the types of allowed exchanges: (a) only two-way cycles, in which two agents swap items, (b) two-way or three-way cycles, (c) (unbounded) chains initiated by an agent who provides an item but expects nothing in return.