We consider trading indivisible and easily transferable \emph{durable goods}, which are goods that an agent can receive, use, and trade again for a different good. This is often the case with books that can be read and later exchanged for unread ones. Other examples of such easily transferable durable goods include puzzles, video games and baby clothes. We introduce a model for the exchange of easily transferable durable goods. In our model, each agent owns a set of items and demands a different set of items. An agent is interested in receiving as many items as possible from his demand set. We consider mechanisms that exchange items in cycles in which each participating agent receives an item that he demands and gives an item that he owns. We aim to develop mechanisms that have the following properties: they are \emph{efficient}, in the sense that they maximize the total number of items that agents receive from their demand set, they are \emph{strategyproof} (i.e., it is in the agents' best interest to report their preferences truthfully) and they run in \emph{polynomial time}. One challenge in developing mechanisms for our setting is that the supply and demand sets of the agents are updated after a trade cycle is executed. This makes constructing strategyproof mechanisms in our model significantly different from previous works, both technically and conceptually and requires developing new tools and techniques. We prove that simultaneously satisfying all desired properties is impossible and thus focus on studying the tradeoffs between these properties. To this end, we provide both approximation algorithms and impossibility results.
翻译:我们认为贸易是不可分割和容易转让的 \ emph{ 可转让货物}, 这是一种代理人可以接受、使用和交易的商品, 是一种不同的商品。 经常是这样的, 书本可以阅读, 以后可以换成未读的。 此类容易转让的耐用货物的其他例子包括谜题、 视频游戏和婴儿衣物。 我们引入了易转让的耐用货物交换模式。 在我们的模式中, 每个代理人拥有一套不同的物品, 需要一套不同的物品。 一个代理人有兴趣从他的需求集中接收尽可能多的物品。 我们考虑的是在每个参与的代理人收到他所要求的物品和提供他拥有的物品的周期中交换物品的机制。 我们的目标是开发具有以下特性的机制: 它们具有效率, 因为它们能最大限度地增加从需求集中获得的物品的总数, 它们拥有一套防腐蚀性物品, 并且要求一套不同的物品。 ( e) 代理商们最有兴趣从他的需求中报告其喜好的东西。 并且他们用一种机制来交换他所需要的物品, 并且用他拥有一个他拥有的物品。 ( polomyalalal) 时间。 我们的目标是开发一个不可靠的机制, 。