MSc Thesis Defense by Zarathustra Goertzel
Offer Networks Simulation and Dynamics
This thesis explores the feasibility of using optimization algorithms to facilitate barter as a market mechanism. A dynamic scale free graph models the variability of tasks, and a uniform acceptance probability p models the likelihood users will be satisfied with suggested exchanges. The ideal exchange size depends on p. This thesis tests an optimal polynomial time algorithm (for p=1), a greedy shortest cycle, GSC, algorithm, a dynamic matching algorithm, and a two-way matching algorithm. In addition, there is a stigmergic approach, HOR, to using the optimal algorithm with p < 1, where when a user rejects a match the surrounding users are kept in hold as another match is sought. This approach allows matching to be more effectively done with low p. The greedy shortest cycle algorithm performs almost as well as the optimal algorithm, and far better for low p. In
conclusion, GSC with HOR make barter exchange feasible.
Supervisor: Christian Wulff-Nilsen
Co-supervisor: Christina Lioma
Censor: Rasmus Pagh, professor, ITU