Preference Matching Algorithm

Question

There's this side project I'm working on where I need to structure a solution to the following problem.

I have two groups of people (clients). Group A intends to buy and group B intends to sell a determined product X. The product has a series of attributes x_i, and my objective is to facilitate the transaction between A and B by matching their preferences. The main idea is to point out to each member of A a corresponding in B whose product better suits his needs, and vice versa.

Some complicating aspects of the problem:

1. The list of attributes is not finite. The buyer might be interested in a very particular characteristic or some kind of design, which is rare among the population and I can't predict. Can't previously list all the attributes;

2. Attributes might be continuous, binary, or non-quantifiable (ex: price, functionality, design);

Any suggestion on how to approach this problem and solve it in an automated way?

I would also appreciate some references to other similar problems if possible.

---

Great suggestions! Many similarities in to the way I'm thinking of approaching the problem.

The main issue on mapping the attributes is that the level of detail to which the product should be described depends on each buyers. Let’s take an example of a car. The product “car” has lots and lots of attributes that range from its performance, mechanical structure, price etc.

Suppose I just want a cheap car, or an electric car. Ok, that's easy to map because they represent main features of this product. But let’s say, for instance, that I want a car with Dual-Clutch transmission or Xenon headlights. Well there might be many cars on the data base with this attributes but I wouldn't ask the seller to fill in this level of detail to their product prior to the information that there is someone looking them. Such a procedure would require every seller fill a complex, very detailed, form just try to sell his car on the platform. Just wouldn't work.

But still, my challenge is to try to be as detailed as necessary in the search to make a good match. So the way I'm thinking is mapping main aspects of the product, those that are probably relevant to everyone, to narrow down de group of potential sellers.

Next step would be a “refined search”. In order to avoid creating a too detailed form I could ask buyers and sellers to write a free text of their specification. And then use some word matching algorithm to find possible matches. Although I understand that this is not a proper solution to the problem because the seller cannot “guess” what the buyer needs. But might get me close.

The weighting criteria suggested is great. It allows me to quantify the level to which the seller matches the buyer’s needs. The scaling part might be a problem though, because the importance of each attribute varies from client to client. I'm thinking of using some kind of pattern recognition or just asking de buyer to input the level of importance of each attribute.

Answer 1

My first suggestion would be to somehow map the non-quantifiable attributes to quantities with the help of suitable mapping functions. Otherwise, simply leave them out.

Secondly, I don't think that you need to assume that the list of attributes is not finite. A standard and intuitive approach is to represent each attribute as an individual dimension in a vector space. Each product is then simply a point in this space. In that case, if you want to dynamically add more attributes you simply have to remap the product vectors into the new feature space (with additional dimensions).

With this representation, a seller is a point in the feature space with product attributes and a buyer is a point in the same feature space with the preference attributes. The task is then to find out the most similar buyer point for a given seller point.

If your dataset (i.e. the number of buyers/sellers) is not very large, you can solve this with a nearest neighbour approach implemented with the help of k-d trees.

For very large sized data, you can take an IR approach. Index the set of sellers (i.e. the product attributes) by treating each attribute as a separate term with the term-weight being set to the attribute value. A query in this case is a buyer which is also encoded in the term space as a query vector with appropriate term weights. The retrieval step would return you a list of top K most similar matches.

Answer 2

As suggested, going wild. First of all, correct me if I’m wrong:

• Just a few features exist for each unique product;
• There is no ultimate features list, and clients are able to add new features to their products.

If so, constructing full product-feature table could be computational expensive. And final data table would be extremely sparse.

The first step is narrowing customers (products) list for matching. Let’s build a bipartite graph, where sellers would be type-1 nodes, and buyers would be type-2 nodes. Create an edge between any seller and buyer every time they reference a similar product feature, as in the following sketch:

Using the above graph, for every unique seller’s product you can select only buyers who are interested in features that match the product (it’s possible to filter at least one common feature, match the full set of features, or set a threshold level). But certainly, that’s not enough. The next step is to compare feature values, as described by the seller and buyer. There are a lot of variants (e.g., k-Nearest-Neighbors). But why not try to solve this question using the existing graph? Let’s add weights to the edges:

• for continuous features (e.g., price):

  

• for binary and non-quantifiable features - just logical biconditional:

  

The main idea here is to scale every feature to the interval [0, 1]. Additionally, we can use feature coefficients to determine most important features. E.g., assuming price is twice as important as availability of some rare function:

One of the final steps is simplifying the graph structure and reducing many edges to one edge with weight equal to the sum of the previously calculated weights of each feature. With such a reduced structure every pair of customers/products could have only one edge (no parallel edges). So, to find the best deal for exact seller you just need to select connected buyers with max weighted edges.

Future challenge: introduce a cheap method for weighting edges on first step :)