0

I'm coding an algorithm in C that would need a little bit of optimization I think.

Imagine I have a population of N individuals, separated in two classes. Some of the individuals are from class A, and the others from class B.

Individuals meet each other randomly in this population, by pairs, according to an encounter rate beta. When two individuals meet, one of them is randomly chosen to offer an amount of money to the other individual. This amount is class-specific (the offer made to an individual from class A will be different from the offer made to an individual from class B). If the other individual accepts the offer, the two individuals go to a "paired" state where they can't meet other individuals until a certain delay.

So each individual is characterized by 4 random variables:

  • offer made to an individual from class A
  • offer made to an individual from class B
  • minimal offer accepted vs an individual from class A
  • minimal offer accepted vs an individual from class B

So this is all my algorithm does: take two random individuals in the solitary population, see if their parameters match, and remove them from the solitary population for a certain time if they do match.

Now imagine that at some point of my simulation, in the population, all variables are inconsistent: all offers are always smaller than minimal offers accepted. Because the encounter rate is constant, my algorithm will keep trying to match individuals even if this is not possible. This behaviour is generating a lot of calculations for nothing. So I'm looking for the best way to adapt the encounter rate to the composition of the population. In other words, I would like the encounter rate to reflect the theoretical number of offers that would be accepted in the solitary population: the bigger the number of offers theoretically accepted, the bigger the encounter rate.

For example, I could go through each individual and see how his parameters match with other individuals, and compute the percentage of encounters that will be accepted in the whole population, but this is not very efficient and leads to many calculations if my population is large... As this calculation will be repeated at each step (once two individuals are removed from the solitary population we have to recompute the encounter rate somehow) I need something that is not too long to compute.

I could also calculate the average offer made by individuals from class A to individuals from class B, and average minimal offer accepted by individuals from class B versus individuals from class A, and see which one is larger, and do the same for A vs A, B vs B, B vs A, etc... But how to determine the new encounter rate from there?

I hope I didn't forget any relevant detail and the question is not too localized, but I've tried to find a simple and efficient way to do that with no luck!

Sulli
  • 101

1 Answers1

1

The simplest thing is to keep track of the maximum offer available and minimum acceptance. If the maximum offer is less than the minimum acceptance, quit.

You talk about tailoring the encounter rate based on offer/acceptance values, but that is inconsistent with randomly choosing the individuals that encounter each other. Should somebody who will offer a lot of money be more prone to meet other people?

Note that the encounter rate is not really a rate as a number of encounters per time, it is an encounter probability for a given individual.

Ross Millikan
  • 374,822
  • I like this idea for its simplicity, but I don't know in practice if it will save me a lot of time. For example, if my population of solitary individuals is very large, and all interactions are impossible except one... It will take a long time for the algorithm to find this couple. But I will try. If I could implement what you say in your second paragraph it wouldn't be a big deal, but unfortunately I can't assume such "smart" individuals in my model. It is necessary for me to keep a random selection of the solitary individuals. – Sulli Apr 10 '13 at 15:29
  • Also about the "If the maximum offer is less than the minimum acceptance, quit", I don't think we can do something so simple. We could if we had found this condition when ALL individuals are solitary. But if some of them are paired, they could come back to the solitary population at a later stage and be compatible with other solitary individuals. So we can't just "quit" the simulation in this case, it would be better to be able to decrease the encounter rate accordingly so that less encounter events are computed until more compatible individuals come back to the solitary population. – Sulli Apr 10 '13 at 15:34