# randomness – Hardness result for online matching

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

1. Does the above accurately capture the hardness of online matching with random order?
2. 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!