Building probability distribution functions from observation

Question

There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same object. However the value of each object is divided evenly among every player that has chosen it. There will be 9000 rounds(choices) per game. Our goal is to maximize the values that we accumulate at the end of the game.

Question: how can I build a probability distribution function for each playing assuming that their decisions are random variables?

Current Approach: My current approach is to count the frequency of a player choosing a specific object and dividing by the total number of rounds, that would give a probability a player is likely to choose that specific object.

Problem: With each player playing aggressively trying to be unpredictable as possible(noise), with my current approach the probability distribution functions are not accurate(9000 rounds doesn't seem to be enough data). Is there a better way to build these distribution functions?

Note: I've read somewhere that (Bayes model and HMM) are more superior than frequency counts, but I am not sure how to adapt it to this situation.

Answer 1

i am not sure i understand correctly what the question is or rather what are the observations from which the (experimental) distributions are going to be estimated.

The problem of a distribution estimation is related more to statistics than computer science althougn it can be relevant in this area as well.

There are various methods using 2 main approaches:

1. Parametrized models of a probability distribution, where one (assuming prior knowledge) uses a pre-defined model (or form or function) of the distribution (e.g a Gaussian) with some free parameters depending on data (observations) and estimates these parameters (eg through Maximum Likelihood or EM algorithm or Maximum Entropy etc..). Even if the form of the prob distribution is not known this method can still be used on approximations like Gauusian Mixture Models. This method produces smooth (and usually robust) estimated distributions assuming the prior form is close to the underlying prob. distribution.

2. Un-parametrized models, estimate the whole PD (including its form) directly from the data. methods in this category are Parzen windows and kernel estimation. This method can be better from parametrized estimation provided the form of the underlying pdf is completely unknown or non-trivial or irregular in some sense.

All the previous methods are computationally efficient (although not necessarily polynomial). This is like the way the Simplex algorithm works, although it is not polynomial-time, it is efficient in many practical situations.

Answer 2

I think you are using the wrong approach. I suggest you use game theory, to figure out your optimal play.

Start with the special case of $N=2$; each player has $M$ choices, so we have a $M\times M$ payout matrix. The payout matrix is easy to define. The optimal strategy is (in general) a randomized strategy. There are standard methods to compute the optimal strategy, given the payout matrix. Then, you can play the optimal strategy. So, for $N=2$, solving this game is easy.

For $N>2$, the game theory gets a bit more complicated, but I think similar ideas still represent a better approach to this problem than trying to estimate the distribution that each player has chosen in the past. After all, past history is not necessarily representative of future play; players might change their choices over time, so the distribution of their choices earlier in the game might not be representative of the distribution of their choices later in the game.