  We investigate mechanism design without payments when agents have different
types of preferences. Contrary to most settings in the literature where agents
have the same preference, e.g. in the facility location games all agents would
like to stay close to (or away from) the facility, we demonstrate the
limitation of mechanism design without payments when agents have different
preferences by introducing exchanging phases. We consider two types of
exchanging phases. The first model is called central exchanges where the
exchanges are performed by a central authority. The other model is called
individual exchanges where agents exchange their outcomes by themselves. By
using facility location games as an example, we provide a truthful mechanism
that optimizes social welfare in central exchanges. We also provide a
universally truthful randomized mechanism that achieves at least a half of the
optimal social welfare in individual exchanges.
