A Recommendation-Based Book-Exchange System Without Using Wish Lists Maria Soledad Pera Yiu-Kai Ng Department of Computer Science Computer Science Department Boise State University Brigham Young University Boise, Idaho, U.S.A. Provo, Utah, U.S.A. solepera@boisestate.edu ng@compsci.byu.edu ABSTRACT of these approaches, however, require users who participate We introduce EasyEx, a recommendation-based book ex- in the exchange to create and maintain their own wish lists, change system which identifies potential exchanges for a user each of which is a list of items that a user wants in return solely based on the user’s item list. EasyEx is novel, since it for giving up the items specified in an item list. The wish effectively identifies books that are likely appealing to users, list of a user must be updated periodically, which takes time and optimizes book-exchange cycles to increase serendipity, and efforts, to reflect the current needs and interests of the instead of simply swapping books on users’ wish lists as per- user. Subsequently, this list may be outdated or incomplete, formed by existing item-exchange algorithms. Experimental since the user might not be aware of the existence of other results have verified that EasyEx offers users recommended items of interest. With that in mind, we propose a new books that satisfy their interests and contributes to the item- book-exchange system, called EasyEx, which does not re- exchange mechanism with a new design methodology. quire its users to specify their wish list of books. Instead, EasyEx analyzes books of interest to a user based on a num- ber of commonly-used recommendation algorithms provided Keywords by LensKit(.org) Recommendation Toolkit and configures Book recommendation, item exchange, rating the optimal book exchange cycles involving multiple users using OptaPlanner(.org), a constraint satisfaction solver. 1. INTRODUCTION EasyEx is novel, since it employs a recommendation-based Internet users have been taking advantage of the free ser- book-exchange mechanism that suggests books of interest vices offered by existing websites to exchange items online, to a user to generate unanticipated exchanges in return and which include books, CDs, and DVDs. A significant num- thus increase serendipity. EasyEx is unique, since to the ber of these item-exchange websites establish a platform for best of our knowledge, EasyEx is the only book-exchange users trading books. Instead of selling used books to book- system (which can easily be extended to other domains of stores for less than half of their original prices or a fraction interest) that incorporates a recommendation mechanism in of their purchasing costs through garage sales, book owners book-exchange cycles. Furthermore, unlike most of the ex- have found another way to maximize the values of their used isting item-exchange tools that limit the exchanges to pairs books by exchanging them with other users’ books online. of users, EasyEx can create multiple exchange cycles that The online book-swapping option is attractive, since access- involve more than two users at a time. EasyEx is a valu- ing these book-exchange websites is free and it just costs the able contribution and attractive option in book exchanges, postage to swap books. Popular book-exchange websites in- since users and books can find each other by pure serendip- clude Readitswapit.co.uk, WhatsOnMyBookShelf.com, Pa- ity. This discovery offers the users books to read to gain perBackSwap.com, and BookMooch.com. new knowledge or for entertainment purpose. We were inspired by the online swapping task performed by existing book-exchange sites and would like to further 2. EASYEX enhance their service by simplifying the book-exchange pro- Given a group of users, each of which is associated with a cess. We are interested in book exchanges, instead of other list of books (s)he is interested in exchanging for new read- item-swapping services, such as stock exchanges, since read- ing material, EasyEx initiates its recommendation-based ex- ing enhances people’s learning, especially at the young ages. change process by identifying potential exchange transac- A number of book, in addition to other item, exchange tions among the users. Each exchange transaction consists approaches have been presented in the literature [1, 3]. All of a user and candidate book to be received. EasyEx gener- ates candidate exchange transactions by examining the pos- sible combinations between users and books they are willing to exchange and excludes transactions that associate users with books already specified in their respective item list. Each candidate transaction is assigned an exchange appeal score, which captures the predicted degree of interest of a user in receiving a particular book as part of the exchange Copyright is held by the author/owner(s). RecSys’15 Poster Proceedings, September 16–20, 2015, Vienna, Austria. process. In computing these scores, EasyEx simultaneously Copyright 20XX ACM X-XXXXX-XX-X/XX/XX ...$10.00. considers both the Personalized Mean and Matrix Factoriza- tion recommendation strategies implemented by the LensKit Datasets Solution Score Late Simulated Hill Tabu Ideal framework. While the former is a simple, yet effective, base- Acceptance Annealing Climbing Search line algorithm for rating prediction based on user and item Opt 5 3.5 3.5 3.5 3.5 4.55 average rating offsets from the global rating, the latter is Opt 15 2.05 3.73 3.73 3.73 4.77 used to learn the latent characteristics of users and items Opt 25 1.12 3.64 3.63 3.64 3.62 so that it is possible to predict unknown ratings using the Opt 50 0.39 0.54 2.27 3.58 3.71 latent characteristics [2]. EasyEx depends on a multiple lin- ear regression model1 to merge rating predictions generated Table 1: The effectiveness of OptaPlanner solutions by the aforementioned strategies. EasyEx analyzes the degree of appeal of each user with effectiveness of the different optimization strategies consid- each candidate book available to be exchanged during its ered by OptaPlanner, we have included in Table 1 the ideal optimization step to generate the optimal set of exchanges solution for the corresponding dataset. An ideal solution among users. The goal is to identify in a timely man- is defined as the average degree of appeal of each user on ner the set of transactions that maximizes the number of each book received as part of an exchange, assuming that users that are interested in the books they receive as part every user was given the book that is the most appealing to of the recommendation-based exchange process. To achieve him among the ones available for swapping. This scenario this goal, EasyEx relies on OptaPlanner, an open source, is highly unlikely in reality, since within an exchange cycle, lightweight, constraint satisfaction solver. It combines so- a book can only be assigned to one of the users involved in phisticated heuristics and metaheuristics with very efficient the exchange regardless the number of users who want it. score calculations (i.e., intermediate solution assessments) to It turns out that the difference between the solution score optimize planning problems, from employee shift rostering generated by using Tabu Search and the ideal solution score to vehicle routing. To the best of our knowledge, OptaPlan- is the lowest among the optimization approaches as shown ner has never been applied for optimization problems related in Table 1 regardless of the dataset examined, which further to online book swapping. (See goo.gl/hTd46P for details.) illustrates the appropriateness of choosing Tabu Search. 3. EXPERIMENTAL RESULTS 4. CONCLUSIONS The dataset employed to evaluate EasyEx and compare To further enhance existing online book-exchange mecha- its performance with respect to other recommenders is the nisms and facilitate the exchange cycles that increase seren- well-known and widely-used BookCrossing2 dataset [4]. dipity on books received by users, we have proposed EasyEx, The quality of exchanges created by EasyEx is determined a new recommendation-based book exchange system. EasyEx by the effectiveness of the recommendation predictions. We (i) relies on widely-used recommendation algorithms pro- computed the Root Mean Square Error (RMSE) on the rat- vided by LensKit and multiple regression to make sugges- ing predictions generated by EasyEx’s recommender, as well tions on books to be received by users and (ii) depends on as personalized mean and matrix factorization, which are the optimal book exchange cycles generated by OptaPlanner 0.57, 0.76, and 0.74, respectively. The significant (p < 0.05) to handle user requests on exchanging books online. EasyEx decrease in RMSE achieved by EasyEx further demonstrates is novel, since unlike existing book-exchange websites, it can the correctness of merging the aforementioned prediction generate unexpected exchanges among users who might oth- strategies into a single one using regression. erwise never know the existence of exchanged items of inter- To determine the most effective algorithm to be applied ests. Moreover, EasyEx is unique, since to the best of our by OptaPlanner to iteratively identify an optimal set of knowledge, it is the first recommendation-based system on exchanges among users and books available for swapping, book exchanges, which can easily be adopted for exchanging we first created subsets of users of different sizes. There- other items besides books online. after, we considered OptaPlanner’s processing time in gen- We plan to further assess the performance of EasyEx by erating an optimal solution for each subset, in addition to considering groups of users with diverse degrees of cohesive- the corresponding solution score3 achieved by each of Op- ness. We will also enhance EasyEx to alert a user U if an taPlanner’s optimization algorithms. These algorithms in- exchange is not possible, which occurs when the likelihood clude Tabu Search, Hill Climbing, Simulated Annealing, and of U enjoying the suggested book as part of the swap is low. (Hill Climbing with) Late Acceptance (see http://goo.gl/ OgF0mH for further details on these algorithms). 5. REFERENCES We have empirically verified that Tabu Search (i) con- sistently outperforms or generates solutions as good as its [1] Z. Abbassi and L. Lakshmanan. On Efficient counterparts as reflected by its solution scores (see Table 1), Recommendations for Online Exchange Markets. In and (ii) minimizes the time required for locating optimal IEEE ICDE, pages 712–723, 2009. solutions for datasets of different sizes, especially for large [2] M. Jamali and M. Ester. A Matrix Factorization numbers of user-book pairs. To provide some context on the Technique with Trust Propagation for Recommend- ation in Social Networks. In ACM RecSys, pages 1 135–142, 2010. We empirically verified that regression-based rating fusion yields better prediction accuracy than other models. [3] Z. Su, A. Tung, and Z. Zhang. Supporting Top-K Item 2 Disjoints subsets of BookCrossing were used for training Exchange Recommendations in Large Online the prediction and regression models, as well as evaluating Communities. In IDBT, pages 97–108, 2012. the performance of EasyEx. 3 [4] C. Ziegler, S. McNee, J. Konstan, and G. Lausen. A solution score quantifies the effectiveness of a solution by averaging the degree of appeal of each user with the book Improving Recommendation Lists Through Topic received as part of the exchange. Diversification. In WWW, pages 22–32, 2005.