0
$\begingroup$

1. Settings:

  • There are $n$ clients. Each client $i$ has a budget of $B_i$ dollars. There are $P$ periods and each period contains $D$ days. Every client $i$ can make a bid $b_{ip}$ in period $p\in P$ such that $\sum_{p\in P}b_{ip}=B_i$. We can assume wlog that $b_{ip}$ belongs to some discrete set, i.e., $b_{ip}\in\{0,1,2,\ldots,B_i\}$.

  • On day $d\in D$ of period $p\in P$, a product appears that can be bought by one and only one client. Each client that chooses its bid larger than the price of the product can buy the product on that period. An online algorithm has to match at most one client to the product on day $d$ of period $p$. (Of course the online algorithm does not know the price of the product beforehand.) A client can be matched once in a period but can be matched in different periods. Similarly, on the next day, another product appears and the online algorithm has to match (in that day of the period $p$) at most one client (that was not previously matched) to it (using the bids of the clients in period $p$).

2. Objective:

  • The online algorithm has to choose the bids of the clients in each period and has to match clients to products in each day of each period in order to maximize the number of times clients matched.

3. Observation:

  • We can see that, for a single period, the problem is equivalent to the online matching problem in a bipartite graph. Clients are vertices on the left and products are vertices on the right that appear one-by-one in an online fashion. Once a client chooses a bid and a product appears, we have an edge between a client and a product if and only if the bid of that client is larger than the price of the product.

  • I can also see that if the number of periods is not known beforehand, then no online algorithm is competitive! (I am not sure but if $P$ is unknown then an adversary can always wait until the clients have spent all of their budgets and then introduce lots of cheap products that could have been matched otherwise.)

4. Question:

  • Is this multiple online matching problem has been studied before? Can you see any related problem in the literature? What do you suggest to solve it?
$\endgroup$
  • $\begingroup$ You asked a related question recently. Is this part of some research exploration? $\endgroup$ – Chandra Chekuri Nov 9 at 1:58
  • $\begingroup$ Yes, I am trying to use online algorithms (which I don't have much knowledge about) in solving some research problem. $\endgroup$ – zdm Nov 9 at 2:10
  • $\begingroup$ The online algorithm has to make its bid $b_{ip}$ for period $p$ at the start of the period? At that time what does it know about the prices that will be set for the products released during that period? $\endgroup$ – Neal Young Nov 10 at 14:36
  • $\begingroup$ Yes, the online algorithm has to make its bid $b_{ip}$ at the start of the period $p$. On day $d$ of period $p$, the online algorithm knows only the product that appears on that day. The problem is like having online matching problem in each period; the relation between the periods is the budget $B_i$. After some research, I found that the problem is somehow similar (not very similar) to the AdWords problem. $\endgroup$ – zdm Nov 10 at 17:52
  • $\begingroup$ Consider an instance with 1 client, with budget 1, and two periods. The first period has two days, in the first, the adversary offers an item of price 2. If the client's bid for the period is 1, the adversary offers an item of price 2 in the second day, and then an item of price 1 in the second period (which has one day). Otherwise (the clients bid for period 1 is less than 1), the adversary offers an item of price 1 in the second day, and then an item of price 2 in the second period. Either way, the algorithm gets nothing, but the offline OPT gets 1. So there is no competitive algorithm. $\endgroup$ – Neal Young Nov 10 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.