1
$\begingroup$

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$ (i.e., $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 the probability the good of equal value to all agents arrives at any time point $t$ is $\frac{1}{n}$ and the probability that is matched correctly at that point is $\frac{1}{n-t}$. Therefore the probability it is matched correctly overall is $\sum_{t=0}^{n-1} \frac{1}{n(n-t)} \leq \frac{\log n}{n} \rightarrow 0$.
Improve this question
$\endgroup$
4
  • $\begingroup$ Theorem 2 is a lower bound on all algorithms, not just the greedy algorithm. It is a lot stronger than what you show. $\endgroup$
    – Yuval Filmus
    Sep 13, 2021 at 15:24
  • $\begingroup$ That makes sense. If instead of the greedy algorithm, I say a random algorithm which uniformly at random picks an agent to assign to, does this demonstrate the result of Theorem 1 instead? $\endgroup$
    – user143196
    Sep 13, 2021 at 15:28
  • $\begingroup$ The second half of Theorem 1 uses this algorithm. $\endgroup$
    – Yuval Filmus
    Sep 13, 2021 at 15:40
  • $\begingroup$ Right, my question is does my probability argument in (2) give a sensible proof of that Theorem (as they just give the sketch of idea) $\endgroup$
    – user143196
    Sep 13, 2021 at 18:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.