Open Collections

On efficient recommendations for online exchange markets

University of British Columbia

Motivated by the popularity of marketplace applications over social net works, we study optimal recommendation algorithms for online exchange markets. Examples of such markets include peerflix. corn and readitswapit.co.uk. We model these markets as a social network in which each user has two as sociated lists: The item list, i.e, the set of items the user is willing to give away, and the wish list, i.e., the set of items the user is interested in receiv ing. A transaction involves a user giving an item to another user. Users are motivated to engage in transactions in expectation of realizing their wishes. Wishes may be realized by a pair of users swapping items corresponding to each otherâ s wishes, but more generally by means of users exchanging items through a cycle, where each user gives an item to the next user in a cycle, in accordance with the receiving userâ s wishes. In this thesis, we first consider the problem of how to efficiently gener ate recommendations for item exchange cycles in an online market social network. We consider deterministic and probabilistic models and show that under both models, the problem of determining an optimal set of recommen dations that maximizes the expected value of items exchanged is NP-hard and develop efficient approximation algorithms for both models. Next, we study exchange markets over time and try to optimize usersâ waiting times, and fairness whereby fairness we mean: give higher priority to users who contribute more to the system in addition to maximizing expected value. We show that by introducing the concept of points, average waiting time can be improved by a large factor. By designing a credit system, we try to maxi mize fairness in the system. We show not only is the fairness optimization problem NP-hard, but also inapproximable within any multiplicative factor. We propose two heuristic algorithms, one of which is based on rounding the solution to a linear programming relaxation and the other is a greedy algorithm. For both the one-shot market and the overtime market studied in this thesis, we conduct a comprehensive set of experiments, and explore the performance and also scalability of the proposed algorithms. Our experiments suggest that the performance of our algorithms in practice could be much better than the worst-case performance guarantee factors.

Thesis/Dissertation

application/pdf

2009-01-28

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/3961

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/