Tuesday, September 23, 2014

Nash Equilibrium for Inter Dependent Repeating Decision Making Events

Hi All,

The concept of Nash Equilibrium is well known. The idea is that the outcome of multiple decision making activities is dependent on the best decision taken by each decision making party and considering the decision by every other decision making party.

Quoting Wikipedia, if Bill and Amy are playing a game, if Bill makes his best possible decision taking into account Amy's decision and Amy makes her best possible decision taking into account Bill's decision, Bill and Amy are in Nash Equilibrium.

Now, consider that Bill and Amy are meeting for the second time. In the first meeting,  Bill and Amy did not have a great experience. Say Bill offered Amy a gift and Amy did not like the gift. The second time Bill and Amy meet, there may or may not be a partial overlap of the original input set (Bill may or may not offer Amy a gift). However, Amy's interpretation of the second event will be influenced by the outcome of the previous meeting.

Consider an advertisement rebidding auction. An intelligent system shall take into consideration the results of previous bidding outcomes. A consistent winner shall have a bigger constant of victory probability.

Based on mixed strategies Nash Equilibrium, where players choose a probability distribution, simply put, given a set of repeating interactions between a set of decision making parties with events which may or may not have overlapping input sets, each event shall lead to a certain amount of biasing of the probability distribution towards the winner.

This can help in modelling real world scenarios where improving the probability of output in a mixed strategies Nash Equilibrium state for repeated interactions between same decision making parties.
A bias towards successful interactions can lead to better and higher winning probabilities in the equilibrium state.

Nash Equilibrium assumes a same state of initial influence of each decision making party. The above model can help if the initial states are itself biased i.e. if one decision making party has a higher influence, the bias can be more towards him. However, if the party does not have an optimal equilibrium, the biasing can shift away hence normalizing the distribution.

The system is essentially introducing a 'feedback' mechanism to the decision making process for further repetitions. The probability distribution functions shall be arranged in a manner that any further interactions shall have a higher bias towards the upper half of the probability distribution spectrum.

Essentially, the idea in the theory that I am talking about in this post is that Nash Equilibrium does not have Markov property hence can be fruitfully biased based on previous events to have a better probability distribution.

I ran some tests for the theory and the results seem to be inline with what I researched above. The biasing constant can be a constant for each decision making party involved or can be experimentally determined for each decision making party involved or can be started off with a basic value and changed (learned) over time.

Of course, it is a pretty basic form and I shall have to put in more research to develop this further and submit it for peer review journals, but the initial outlook seems good!

Feedback would be great.