In an evolutionary game theoretic context, I am interested in calculating expected payoffs of different strategies in a 2x2 game, given a weighted random sampling without replacement from a population. When the sampling size is 1, simple weighted sums suffice to calculate expected payoff, given the set of weights and strategies corresponding to each of the individuals in the population. The problem I am faced with here is a generalization of that scenario. I can formulate the problem as follows.


Let $S$ be a (finite) set and $\mathcal{P}(S)$ its powerset. Denote as $\mathcal{P}(S)_M$ the subset of $\mathcal{P}(S)$ for which it is the case that all of the members of $\mathcal{P}(S)_M$ have cardinality $M$. Given a set $S$, consider the function $WRS_M(S)$ with co-domain $\mathcal{P}(S)_M$ that describes the outcome of a weighted random sampling algorithm without replacement from $S$ of size $M$, with weights given by a function $w(s_i): S\rightarrow\mathbb{R}_+$.

Consider two functions $f(s_i): S\rightarrow\{A,B\}$ and $g(s_i): S\rightarrow\{C,D\}$ where $A$, $B$, $C$, and $D$ are Real-valued constants. $f$ and $g$ correspond to payoffs received by adopting strategies $1$ and $2$.

When $M=1$, expected payoffs of strategy $1$ and strategy $2$ are simply $\sum_{i\in S} w_i*f(s_i)$ and $\sum_{i\in S} w_i*g(s_i)$ respectively. The general solution (for $1\leq M\leq S$) is, as far as I've gathered, unknown.


So far, I've hit dead-ends. I do not think the general solution will be pretty, but I'm not even sure how to proceed. My hunch was to consider the likelihoods of different strategy compositions of initial segments of total permutations (somewhat along the lines described in the linked paper in the answer here: https://math.stackexchange.com/questions/316175/probability-to-choose-specific-item-in-a-weighted-sampling-without-replacement). In other words, given the various permutations of S in the weighted approach explored there, how likely is it that the first $M$ items in the permutation include $N$ members with strategy $1$ and $M-N$ members with strategy $2$? So far though, this hunch hasn't yielded anything for me.

Any help tackling this problem would be appreciated! (For what it's worth, I see no reason why the restriction to 2x2 games instead of NxN games should make a difference. On the other hand, the restriction to finite total populations--and hence finite samplings-- should make a difference.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.