Currently studying the following paper:
“Fair Allocation in Online Markets” – Gollapudi and Panigrahi 2014
In which they present Theorem 2 as a hardness result for online maxmin matchings (without proof). My thinking for a counterexample which demonstrates that a random ordered stream can give an arbitrarily bad result say with a standard greedy algorithm (and thus verify this theorem):
Assume we have $n$ agents to which we must match a good as they arrive online in a random order (assume we implement a greedy algorithm which always allocates to the least satisfied agent, breaking ties arbitrarily). Additionally, assume an adversary has selected $n$ goods with the following properties: $n-1$ goods have value 1 for exactly one agent $i$ and 0 for all other agents $j$ ($v_j(g_i) = 1 iff j = i$) meaning there is a leftover agent who does not have a specified good, and there is one good of value 1 for all $n$ agents. Thus, if the item of equal value to all agents is assigned improperly the maxmin value is 0.
My questions are
- Does the above accurately capture the hardness of online matching with random order?
- I am not sure how to approach a probabilistic argument that with high probability, the worst case scenario will occur. My thinking is that we can construct a probability that if the good of equal value to all agents arrives in the first $n/2$ items, then the probability it is given to the wrong agent is some X and thus this is the probability that maxmin = 0? Any help here would be greatly appreciated!