Back to search

University of British Columbia

On efficient recommendations for online exchange markets

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Abbassi, Zeinab

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/3961

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Abbassi, Zeinab. On efficient recommendations for online exchange markets. master's thesis, University of British Columbia, 2008. http://hdl.handle.net/2429/3961