How to design an online algorithm for secretary problem with multiple players?

Question

We have $k$ bins of capacity $c_i$ each. These bins appear in an online fashion, say on day $i$, bin $i$ appears. There are $l$ balls. Ball $j$ has weight $w_{ij}$ with bin $i$.

Each ball knows that there will be $k$ bins. On day $i$, bin $i$ appears and ball $j$ gets to know the bin and its capacity $c_i$. Also, ball $j$ gets to know $w_{i1},w_{i2},\ldots,w_{il}$; the weights of all balls with bin $i$ (including her weight of course). Ball $j$ must decide either to put herself into bin $i$ or not, once and forever (i.e., once decided, the game is over for ball $j$).

Each ball wants to be satisfied, that is, puts herself into a bin that has enough capacity. Ball $j$ does not know if some other balls have chosen bin $i$ or not. Also, Ball $j$ knows only the current information, does not know the weights of the balls with bins that will appear in the future.

Is there a way to find an online algorithm that maximizes the number of satisfied balls? I think this is somehow related to secretary problem but I am not sure how to prove this claim.

Answer 1

Per @usul's suggestion, consider the following online greedy algorithm $A$. When bin $i$ is revealed, $A$ considers all subsets $S$ of not-yet assigned balls such that all balls in $S$ can fit together in bin $i$. It chooses any largest such set, say $A_i$, then assigns all balls in $A_i$ to bin $i$.

The post asks for an algorithm that each ball can use independently. To achieve this, just have each ball independently simulate $A$, and decide to join a given bin only if $A$ says it should.

Lemma 1. This greedy algorithm is 0.5-competitive.

Proof. Let $A^* = \bigcup_{i} A_i$ denote the set of balls assigned by $A$. Let $O_i$ denote the set of balls assigned by OPT to bin $i$. Let $O^* = \bigcup_i O_i$ be the set of all balls assigned by OPT.

The set $O_i \setminus A^*$ is one possible set that $A$ could have assigned to bin $i$. Set $A_i$ is at least as large as this set, so $|O_i \setminus A^*| \le |A_i|$. Summing over $i$ gives $|O^*\setminus A^*| \le |A^*|$. That is, the number of balls assigned by OPT but not $A$ is at most the number assigned by $A$. This implies the desired bound. Specifically, as $O^* \subseteq A^* \cup (O^*\setminus A^*)$, it follows that $$|O^*| \le |A^*| + |O^*\setminus A^*| \le |A^*| + |A^*| = 2|A^*|.~~~~~~~~\Box$$

If you want a polynomial-time algorithm, you can modify $A$ to choose each set $A_i$ so that it is within a factor of $1-\epsilon$ of the largest possible. (E.g., to achieve $\epsilon=1/2$ just order the not-yet-assigned balls by increasing $w_{ij}$, and take as many as will fit in bin $i$. Or use a PTAS at each step to achieve any fixed $\epsilon>0$.) Then $|O_i \setminus A^*| \le |A_i|/(1-\epsilon)$ and the algorithm will be $(1-\epsilon)/(2-\epsilon)$-competitive. (E.g. $1/3$-competitive for $\epsilon=1/2$.)

And just for the record, per OP's comment:

Lemma 2. No deterministic online algorithm has competitive ratio more than 0.5.

Proof. Consider the instance with two balls and two capacity-1 bins, where each ball has weight 1 for bin 1, but only the ball put by the online algorithm in bin 1 can fit in bin 2.$~~~\Box$