WWW 2008 / Poster Paper April 21-25, 2008 · Beijing, China Offline Matching Approximation Algorithms in Exchange Markets Zeinab Abbassi Depar tment of Computer Science University of British Columbia 2366 Main Mall Vancouver, Canada Laks V. S. Lakshmanan Depar tment of Computer Science University of British Columbia 2366 Main Mall Vancouver, Canada zeinab@cs.ubc.ca laks@cs.ubc.ca ABSTRACT Motivated by several marketplace applications on rapidly growing online social networks, we study the problem of efficient offline matching algorithms for online exchange markets. We consider two main models of one-shot markets and exchange markets over time. For one-shot markets, we study three main variants of the problem: one-to-one exchange market problem, exchange market problem with short cycles, and probabilistic exchange market problem. We show that all the ab ove problems are NP-hard, and prop ose heuristics and approximation algorithms for these problems. Exp eriments show that the numb er of items exchanged will increase when exchanges through cycles are allowed. Exploring algorithms for markets over time is an interesting direction for future work. that can b e sp ent on another item later. In these systems, our goal is to find a collection of exchanges amongst users that maximize the numb er of items exchanged. 2. MODEL In an online exchange market a transaction happ ens at the same time as the user declares her intent to acquire the item. However, in an offline market, the user states her intent to the system by listing her wishes in a wishlist, and the system notifies her ab out a p ossible exchange later through an offline message. One-Shot exchange markets. Let U b e a set of users and I b e a set of items. For each user u U , let Su (a.k.a. item list) b e the set of items that user u owns and Wu (a.k.a. wish list) b e the set of items that user u requires. Simple exchange markets(SimpleMarket). In a simple exchange market, we only match users one-by-one, i.e, in each transaction, two users u and v can exchange two items i and j . In an instance of the the simple market problem, we are given a set of users U with the item lists Su and wish lists Wu for each user u U , and our goal is to find the maximum cardinality set of exchanges [(u, i), (v , j )] where i Su , j Wu , j Sv and i Wv . Exchange markets through cycles. In an offline exchange market, we can find cycles of size larger than 2. Clearly, we can exchange more numb er of items through these typ es of cycles compared to the one-to-one exchanges. We also assume that each user has at most one copy of each item i in their item list. Similarly, each user wishes for at most one copy of any item. In the CycleMarket problem, our goal is to find a set of conflict-free cycles: [(u1 , i1 ), (u2 , i2 ), (u3 , i3 ), . . . , (uk , ik )] where i1 Su1 , i1 Wu2 , i2 Su2 , i2 Wu3 . . ., ik Suk , ik Wu1 such that [(u, i), (, )] app ears at most once in the set of cycles to avoid conflicts. Our goal here is to maximize the numb er of items involved in exchanges, thus maximizing the numb er of transactions. Note that a transaction over a cycle can happ en if all of its exchanges happ en. As a result, it is desirable to discover short cycles, and solve the short cycle exchange market problem, denoted by ShortCycleMarket problem In this problem, given a numb er p 3, we want to find a conflict-free set of exchange cycles of at most p exchanges each. Probabilistic exchange markets(ProbMarket). A more refined model for exchange takes into takes into account the probability of a user b eing involved in an exchange, p erhaps based on the reputation of the user she must trans- Categories and Subject Descriptors F.2.2 [Theory of Computation]: Algorithms & Complexity--Nonnumerical Algorithms ; H.m [Information Systems]: [Miscellaneous] General Terms Algorithms, Performance Keywords Social Networks, Exchange Markets, Recommendation Algorithms, Set Packing, Edge Partitioning 1. INTRODUCTION Online social networks are rapidly developing. Users sp end increasing amounts of time on social network websites like MySpace and Faceb ook. A social network is a good framework to implement a market among users for exchanging items. Examples of existing exchange markets on the Web are p eerflix.com and readitswapit.co.uk. Motivated by the ab ove and in order to improve the quality of user exp erience in exchange markets, we study optimal matching algorithms for online exchange markets. In particular, we prop ose two main models of exchange markets: (i) One-shot markets in which each user receives an item in return for the item which has given away in the same time; and (ii) Over-time markets in which a user may not receive an item in return for her given item, but earn some p oints Copyright is held by the author/owner(s). WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04. 1187 WWW 2008 / Poster Paper act with, their location information, friendship, etc. As a result, we have a graph with some probability on each edge. Assuming that the probability of realizing each exchange is indep endent of other exchanges, in the ProbMarket problem, our goal is to find a set of cycles with the maximum exp ected numb er (or exp ected value) of edges that are covered. Note that the probability of a cycle is the product of the probability of its edges. April 21-25, 2008 · Beijing, China Maximal/Greedy Algorithm. To improve the running time of the greedy algorithm, we design the following heuristic. In this approach, in order to find the cycles, we can p erform the breadth first search(BFS) algorithm from each node v , and find a cycle Cv by identifying backward edges in the BFS algorithm. Then we pick the b est cycle (i.e. cycle Cu with the maximum weight) and add it to the set of conflict-free cycles. We rep eat this process until we get a maximal collection of cycles. Local Search Algorithm. In this algorithm, we iteratively 3. HARDNESS RESULT attempt to replace a small subset of the current solution The ab ove exchange market problems are related to the by some set of cycles that result in a larger total weight. kidney exchange problems studied in [1], however the slight More precisely, for any exchange cycle C that is not already difference which will b e explained, makes the problem much selected, we try to add C and remove all the conflicting harder. The prop erty that discriminates the kidney exedges. If the total weight of the collection increases by a change from our problem is that each patient needs exactly factor , add C to the collection and up date the collection of one kidney and each donor wants to donate one kidney. cycles by removing all conflicting cycles from it. We p erform We show that despite the fact that the kidney exchange this procedure until no local improvement is p ossible. In problem with cycles of size 2 is p olynomial-time solvable, the [2], the authors prove that the local search algorithm gives SimpleMarket problem is NP-hard. To prove this harda k - 1-approximation algorithm. ness result, we give a reduction from a variant of edge disGreedy/Local Search. Another heuristic algorithm is to joint partitioning problem 4-partite graphs to the Simplerun the greedy algorithm to find a collection of cycles and Market problem. We first show the NP-hardness of that then run the local search algorithm starting from this collecvariant using a reduction from the edge-partitioning of trition. In [3], it is proved that this algorithm is a 2(2k + 1)/3partite graphs [4] and then give a reduction from 4CycEdgePart approximation algorithm and show that this is asymptotito the SimpleMarket problem. Using similar methods, cally tight. we can also show NP-hardness of the ShortCycleMarket and ProbMarket problems. 5. EXPERIMENTAL RESULTS 4. OUR ALGORITHMS The one-shot exchange market problem is a sp ecial case of the weighted k-set packing problem, in which, given a collection of sets, each of which has an associated weight and contains at most k elements drawn from a finite base set, our goal is to find a collection of disjoint sets of maximum total weight. The restriction to sets of size at most k prop erly includes multi-dimensional matching, which is a generalization of the ordinary graph matching problem. Here, Using ideas from known algorithms for the k-set packing problem, we design heuristics and approximation algorithms for the ab ove exchange market problem (including the ProbMarket problem). To formalize the one-shot exchange market problem as a sp ecial case of the set packing problem, we consider sets as the exchange cycles and define the elements of the sets to consist of the user, the item, and the act of giving or wishing. The weight of each set in the given problem is the numb er of items exchanged on the corresp onding cycle, or the total exp ected value of the exchanges on the cycle. Now, using ideas from algorithms for the set packing problem, we consider the following heuristic algorithms, some of which have provable p erformance guarantee for all of the ab ove problems. A Greedy Algorithm. Given the hardness result, we look for approximation algorithms for the problem. One approach is the following greedy algorithm: at each step, we find the b est exchange cycle C with the maximum weight. In order to find the b est cycle, we can try all short cycles and then pick the cycle with the maximum weight. Then add C to the collection of cycles. Remove all the edges that are in conflict with C . In [3], it is shown that the p erformance of the ab ove greedy approach to the weighted k-set packing problem is a 2k-approximation. Exp eriments are done on a set of synthetic data. We randomly generated the data so that the numb er of items in the item lists and wish list follow a p ower law distribution. We observed that the numb er of users involved in transactions increases when cycles of length larger than 2 are allowed. This increase for the maximal/greedy algorithm is 4% to 6%, and for the local search algorithm is 6% to 10%. The exp erimental results are much b etter than the worst-case approximation factors. 6. FUTURE WORK In this pap er, we study various models for the exchange market problem. Two interesting research directions are designing improved approximation algorithms for these problems and comparing the quality of these algorithms on some real data sets. Finally, designing efficient algorithms for over time markets is left as an interesting future work. These markets can b e modeled as rep eated variants of the one-shot exchange markets. In particular, the use of virtual points (that can b e gained or redeemed by users in exchange of items) can decrease the exp ected waiting time of users. Exploring these ideas is an interesting research direction. 7. REFERENCES [1] D. J. Abraham, A. Blum, and T. Sandholm. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In ACM Conference on Electronic Commerce, pages 295­304, June 13-16 2007. [2] E. M. Arkin and R. Hassin. On local search for weighted k-set packing. In ESA 1997, pages 13­22, 1997. [3] B. Chandra and M. Halldorsson. Greedy local improvement and weighted set packing approximation. In SODA 1999, pages 169­176, 1999. [4] I. Holyer. The np-completeness of some edge-partition problems. SIAM Journal of Computing,, 10(4):713­717, November 1981. 1188