Sie sind hier

# Reachable Object in Paths and Cycles or "Good Things Come to Those Who Swap on Tour"

Matthias Bentert (TU Berlin)

We study a simple exchange market, introduced by Gourvès, Lesca and Wilczynski (IJCAI'17), where every agent initially holds a single object. The agents have preferences over the objects, and two agents may swap their objects if they both prefer the object of the other agent. The agents live in an underlying social network that governs the structure of the swaps: Two agents can only swap their objects if they are adjacent.
We investigate the Reachable Object problem, which asks whether a given starting situation can ever lead, by means of a sequence of swaps, to a situation where a given agent obtains a given object. This problem is known to be NP-complete even if the network is restricted to trees. This talk will present a polynomial-time algorithm for Reachable Object on Paths and Cycles.


Date
Speaker
Location
Language
28.11.2019
16:15
Matthias Bentert
TEL 512
English

Back to the research colloquium site.

Nach oben