There are m orange vendors and n clients in a market. Each client only wants to buy c = 1 orange and each vendor has a stock of r = 1 oranges. The vendors are greedy, and even with r = 1 oranges, they try to sell their oranges to k clients sorted among all the clients with the same probability. Once a client is addressed by more than one vendor, he chooses randomly from which one he'll buy the orange.
The question is: given m, n, c, r and k, what's the expected value of oranges sold?
Examples of situations with k = 1 and k = 2
In the first example, all the three oranges were sold. In the second one, only two of them were sold (with half of the chance that it was by the second vendor and another half that it was by the third). In the third example, only one orange was sold by vendor one, two or three with equal probability p = 1/3.
The fourth and fifth examples have k = 2. For these cases, let's take the assumption that vendors "prefer" clients with less competition. So, in the fourth example, vendor 1 will sell to client 1, and vendor 3 to client 5, so we'll have an expected value of 3 oranges sold. Same for the fifth example. (I'm not very sure about that)
Another two reasonable assumptions: m <= n and c <= k.
I'm struggling to solve even the more basic version of that problem (c = r = k = 1). I've tried to solve it using combinatorics and a recursive approach, but when m and n start to grow it's hard to generalize the solution. Feel free to generalize for other combinations of c, r and k.
Hope it's a nice challenge for you all! Thanks.
For the $c=r=k=1$ case, if we focus on one client, the chance he buys an orange is the chance he gets addressed by at least one vendor. The chance he is not addressed by a given vendor is $1-\frac 1n$. The chance he is not addressed at all is $(1-\frac 1n)^m$, so the expected number of oranges he buys is $1-(1-\frac 1n)^m$ By the linearity of expectation, the expected number of oranges bought is $n\left(1-(1-\frac 1n)^m\right)$