Abstract:

Consider a \emph{barter exchange} problem over a finite set of agents, where each agent owns an item and is also associated with a (privately known) \emph{wish list} of items belonging to the other agents. An outcome of the problem is a (re)allocation of the items to the agents such that each agent either keeps her own item or receives an item from her (reported) wish list, subject to the constraint that the length of the trading cycles induced by the allocation is up-bounded by a prespecified \emph{length bound} $k$. The utility of an agent from an allocation is $0$ if she keeps her own item; and it is $\lambda(\ell)$ if she receives an item from her (true) wish list and participates in a trading cycle of length $2 \leq \ell \leq k$, where $\lambda$ is a prespecified monotonically non-increasing \emph{length function}. (The agent incurs a large dis-utility if she receives an item that is neither hers nor belongs to her wish list.)

In this talk, we investigate the aforementioned barter exchange problem from the perspective of mechanism design without money, aiming for truthful (and individually rational) mechanisms whose objective is to maximize the \emph{social welfare}. As the construction of a social welfare maximizing allocation is computationally intractable for length bounds $k \geq 3$, we focus on (computationally efficient) truthful mechanisms that approximate the optimal social welfare. In particular, we establish upper and lower bounds on the guaranteed approximation ratio, expressed in terms of the length bound $k$ and the length function $\lambda$. Our main technical contribution is an algorithmic tool that can be viewed as a truthful version of the \emph{local search} paradigm.

(joint with Y. Emek)