1

I want to find the best matching algorithm to recreate an economic simulation.

I will create differents groups of customers. Each group will have particular parameters that will determine what the customers wants to buy. Example of those parameters : quality, features, marketing, etc.

Each player in my game will create differents products and try to fill out the needs of the differents groups of customers. Then, they will put a price on each product, and decide how much they will produce (limited quantity).

So, on one side, you have a limited quantity of customers. On they other side, you have a limited quantity of products. These to quantities do not need to be equal (but it can be). So you might have too much products for the quantity of customers, or too much customer for quantity of products. But one thing is sure : every customer wants to buy a product, unless there is a shortage.

I found the stable mariage algorithm, but this one doesn't seem to fit exactly my situation. What would be the best matching algorithm for this?

This question is related to a previous post about similar subject : An algorithm for economic simulation?

Community
  • 1
  • 1
NLemay
  • 2,331
  • 3
  • 29
  • 45

1 Answers1

3

One way to think about this problem is as a maximum-weight bipartite matching problem. In your setup, you can think of the problem as a graph with two groups of nodes:

  1. Nodes corresponding to customers
  2. Nodes corresponding to products

There is an edge pairing up each customer with the products that they're interested in buying, with the cost of an edge being how much the customer wants that particular product. Since customers aren't paired with customers and products aren't paired with products, this graph is bipartite.

Given this setup, one option would be to find a matching in this graph with the maximum possible possible total benefit (that is, maximizing the total amount of utility given by people buying the appropriate products). This way, everyone who can buy something will end up doing so, unless other people so disproportionately want the products that that customer wants that it makes more sense for that person not to get any of his preferred products. There are many algorithms for maximum-weight bipartite matching, and they run fairly quickly.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Hello. This is a really nice solution for my problem! So, if I understand well, I create a bipartite graph with customers on one side and products on the other one. Then, I create an edge with a value between each customers and each products. This value determine if the customer is willing to buy this product or not. 100 = very willing and 0 = not interrested. Than, I find the maximum weight possible. But only one question : how do I make sure that the cheapest products are sold first? Do I put the price as a parameters to calculate the weight? Thanks! – NLemay Feb 16 '12 at 23:08