Go to  Advanced Search

On efficient recommendations for online exchange markets

Show simple item record

dc.contributor.author Abbassi, Zeinab
dc.date.accessioned 2009-01-28T16:21:15Z
dc.date.available 2009-01-28T16:21:15Z
dc.date.copyright 2008 en
dc.date.issued 2009-01-28T16:21:15Z
dc.identifier.uri http://hdl.handle.net/2429/3961
dc.description.abstract 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. en
dc.format.extent 1602972 bytes
dc.format.mimetype application/pdf
dc.language.iso eng en
dc.publisher University of British Columbia
dc.subject Social networds en
dc.subject Online exchange en
dc.title On efficient recommendations for online exchange markets en
dc.type Electronic Thesis or Dissertation
dc.degree.name Master of Science - MSc en
dc.degree.discipline Computer Science en
dc.degree.grantor University of British Columbia
dc.date.graduation 2008-11 en
dc.degree.campus UBCV en


Files in this item

Files Size Format Description   View
ubc_2008_fall_abbassi_zeinab.pdf 1.602Mb Adobe Portable Document Format   View/Open
 

This item appears in the following Collection(s)

Show simple item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893