MCS Thesis
Match-Making in Bartering Scenarios
By: Sbastien Mathieu
Supervisors: Dr. Virendra C. Bhavsar and Dr. Harold Boley
Examining Board: Dr. John DeDourek, Dr. Weichang Du, Dr. Donglei Du December 5th, 2005
Agenda Introduction Background Bartering Trees Tree Approximation Ring Bartering Algorithm
Computational Results
Conclusion
Introduction (1/5)
Internet as a market place Web portals
Simple portals ( [Link] ) Match-making portals ( [Link] ) Bartering portals ( [Link] ) Advanced portal proposals ( [Link] )
Introduction (2/5)
Bartering
The practice of exchanging goods or services without using the medium of money [2]
Introduction (3/5)
Bartering
Agent1
Similarity1
Agent2 Offer2
Aggregate Similarity
Seek1
Offer1
Similarity2
Seek2
Introduction (4/5)
Ring Bartering Agent1 Agent2
Similarity1
Seek1
Offer1
Offer2
Seek2
Agent3
Similarity4 >> Similarity2
Seek3 Offer3
Similarity3 >> Similarity2
Introduction (5/5)
Ring Bartering
O Agent2
s1
s2
O Agent1
sn
O Agentn
sn-1
sk-1
O Agentk
sk
O Agentn-1
sn-2
Background (1/4)
Different match-making techniques
IBM Websphere rules and properties Agent-Mediated eCommerce System with Decision Analysis Features [15] Bhavsar/Boley/Yang Tree similarity algorithm [1,11,12,15,16]
Background (2/4)
Arc labelled weighted trees
Labels on Nodes, fanoutunique labels on Arcs Relative importance on Arcs weights ( wi = 1.0)
Background (3/4)
Similarity Algorithm
Computes the similarity between two arc labeled weighted trees Top-down traversal / Bottom-up computation Can handle trees having different arc labels and structures
10
Background (4/4)
Different bartering approaches
The Trade Balance Problem [12] Multi-Agent Learning Improvement [20] Ring Bartering in P2P [3]
11
Bartering Trees (1/3)
12
Bartering Trees (2/3)
Computing the Aggregate Similarity
Arithmetic mean not judicious
E.g.:
Similarity ( Offer1, Seek2 ) = 1.0 Similarity ( Seek1, Offer2 ) = 0.0 Aggregate similarity = 0.5 ?
13
Bartering Trees (2/3)
Computing the Aggregate Similarity
Arithmetic mean not judicious E.g.: Similarity ( Offer1, Seek2 ) = 1.0 Similarity ( Seek1, Offer2 ) = 0.0 Aggregate similarity = 0.5 ? Aggregate similarity ~ 0.3 =
(Aggregate similarity reasonably less than 0.5)
14
Bartering Trees (3/3)
The Aggregation Function with a = -1.5
15
Tree Approximation (1/3) Motivations
To represent our Trees in a multi-dimensional space and use spatial data-structures To avoid the computation of all similarity values
Concepts
Base: Set of Trees formed by all possible unary trees The maximum depth is the level of the base The lower the level, the greater the approximation Dimension: Number of Trees in the base
16
Tree Approximation (1/3)
17
Tree Approximation (2/3)
Notion of Distance
18
Tree Approximation (3/3)
Behavior of Distance against Similarity
19
Notion of Risk The risk takes into account:
The number of participants in the trade The similarities between the corresponding seeks and offers that are involved in the trade
20
Ring Bartering Algorithm (1/6)
Our algorithm
Returns the (finite) set of rings starting from a given agent
Divided into three main phases:
Repeated selection of the closest Offers (for a given Seek) first pruning step Closure of the ring Testing of the risk second pruning step
21
Ring Bartering Algorithm (2/6)
Overall Algorithm
22
Ring Bartering Algorithm (3/6)
Selection of the closest Offers
23
Ring Bartering Algorithm (4/6)
Closure of the ring
24
Ring Bartering Algorithm (5/6)
Testing of the risk
Ideal Agent = Agent having similarity equal to one with both the previous and the following agent in the ring
25
Ring Bartering Algorithm (6/6) Properties of our algorithm
A ring starting from an Agentj of the agent database will be reported by the algorithm, called with Agentj as argument, if and only if it is Dmax/Rmax acceptable Suppose a ring is reported by the algorithm when starting with a given agent. This ring, will be also reported if we start the algorithm with any of the other agents in the ring Dmax = Maximum Distance Rmax = Maximum Risk Dmax/Rmaxacceptable = Risk below Rmax, all Distances below Dmax
26
Computational Results (1/4)
Influence of the Distance
Highest Missing Ring = Similarity of the first missing ring when sorted by aggregate similarity
Number of Highest non Missing Rings = Number of Rings before the first missing ring when sorted by aggregate similarity
27
Computational Results (2/4) Influence of the Risk
28
Computational Results (3/4) Computation Time and Size of the Rings
29
Computational Results (4/4) Computation Time without Pruning
(ie Dmax = and Rmax = 1)
30
Conclusion (1/2)
We moved from the restrictive buyer/seller scenario to bartering and ring bartering scenarios We developed an efficient algorithm using two pruning techniques based on the notions of Distance and Risk
31
Conclusion (2/2) Future Work
Pairing: to create the best combination of rings involving every agent in the virtual market place exactly once Local Similarity: can improve our tree approximation by adding information without increasing the number of dimensions Transfer tree approximation technique back to indexing in non-bartering scenario
32
Questions ?
Thanks !
33
A zero Distance example with a low similarity for a level 1 base
34
Seller weights: an example
Seller1 emphasizes his/her pool easier negotiation phase
35
An example of Base
Bases of dimension 5 and 2
36