Loading...
Please wait, while we are loading the content...
Similar Documents
Online algorithms for market clearing (2002).
| Content Provider | CiteSeerX |
|---|---|
| Author | Blum, Avrim Sandholm, Tuomas Zinkevich, Martin |
| Abstract | In this paper we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. The auctioneer is faced with an online clearing problem of deciding which buy and sell bids to match without knowing what bids will arrive in the future. For maximizing profit, we present a (randomized) online algorithm with a competitive ratio of ln(p max min )+1, when bids are in a range [p min ,p max ], which we show is the best possible. A simpler algorithm has a ratio twice this, and can be used even if expiration times are not known. For maximizing the number of trades, we present a simple greedy algorithm that achieves a factor of 2 competitive ratio if no money-losing trades are allowed. Interestingly, we show that if the online algorithm is allowed to subsidize matches --- match money-losing pairs if it has already collected enough money from previous pairs to pay for them --- then it can be 1-competitive with respect to the optimal offline algorithm that is not allowed subsidy. That is, the ability to subsidize is at least as valuable as knowing the future. We also consider the objectives of maximizing buy or sell volume, and present algorithms that achieve a competitive ratio of 2(ln(p max /p min ) + 1), or ln(p max /p min ) + 1 if the online algorithm is allowed subsidization. We show the latter is the best possible competitive ratio for this setting. For social welfare maximization we also obtain an optimal competitive ratio, which is below ln(p max /p min ). We present all of these results as corollaries of theorems on online matching in an incomplete interval graph. |
| File Format | |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
