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

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.

• "Each ball wants to be satisfied, that is, puts herself into a bin that has enough capacity. The unknown here is that ball 𝑗 does not know if some other balls have chosen bin 𝑖 or not." It is unclear what this means. If all balls agree on some protocol in advance, you could use any online algorithm you want -- each ball would just simulate the algorithm to know what it (and the other balls) should do. – Neal Young Nov 5 '19 at 23:54
• If we assume that the balls cannot communicate with each other, does that make the problem clearer? – zdm Nov 6 '19 at 0:25
• @NealYoung I think it is better to see a special case of the problem. Say, when bin $i$ appears, it can contain at most one ball (we can choose the weights to satisfy this condition). This special case, I think, is the classical online matching problem. – zdm Nov 6 '19 at 0:45
• Suppose for now that there is a single algorithm deciding which balls go in each bin. Maybe using online-matching-like techniques you can prove that a greedy algorithm -- pack the most balls that will fit at each time step -- achieves a decent competitive ratio like 0.5. (Ignoring that it's NP-hard to compute.) – usul Nov 6 '19 at 0:56
• Say $k=2$ and $l=2$. Say bin 1 has capacity $c_1=2$ and bin 2 has capacity $c_2=1$. Say when bin 1 appears, we have $(w_{11},w_{12})=(1,2)$ and an online algorithm puts ball 1 into bin 1. Now, when bin 2 appears, say we have $(w_{21},w_{22})=(1,2)$. The online algorithm cannot put any ball in bin 2 (it has already put ball 1 into bin 1 and ball 2 cannot be put into bin 2). However, ball 1 can be put into bin 2 and ball 2 can be put into bin 1. I meant to say that future weights and future capacities are not known. – zdm Nov 6 '19 at 2:47

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$$

• The reason for 1/2 in this case is known to follow from local-greedy for submodular function maximization subject to a partition matroid constraint. It may shed light on more general problems. I will post a pointer when I get a chance. – Chandra Chekuri Nov 6 '19 at 17:39
• Related to my other comment, here are talk slides from 2006 where I explain the connection between multiple knapsack, generalized assignment and local-greedy for submodular function maximization. Some may find this connection helpful. chekuri.cs.illinois.edu/talks/crm_submodular.pdf – Chandra Chekuri Nov 6 '19 at 20:05