A stochastic algorithm for online bipartite resource allocation problems
© 2016 Elsevier Ltd This paper deals with online resource allocation problems whereby buyers with a limited total budget want to purchase items which become available one at a time and which consume some amount of various limited resources upon allocation. A central resource allocation platform is i...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134661 |
| _version_ | 1811068745899048960 |
|---|---|
| author | Legrain, Antoine Jaillet, Patrick |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Legrain, Antoine Jaillet, Patrick |
| author_sort | Legrain, Antoine |
| collection | MIT |
| description | © 2016 Elsevier Ltd This paper deals with online resource allocation problems whereby buyers with a limited total budget want to purchase items which become available one at a time and which consume some amount of various limited resources upon allocation. A central resource allocation platform is in charge of allocating the items to the potential buyers, with the goal of maximizing the total revenue subject to budget and resource constraints. Sponsored search advertising is a typical example: in order to maximize revenue, search engines try to choose the best available advertisement to display on a web page resulting from a search query. Two main approaches have been proposed to address such online problems, depending on the assumptions made about the input sequence: one is trying to guarantee a performance against a worst case scenario (sometimes called the adversarial model); the other one, based on specific probabilistic assumptions about the input, is concerned with expected performance guarantee. However, combining the strengths of these two approaches could potentially outperform both in some settings. In this paper we propose such a practical method which goes beyond the adversarial model but requires only a limited amount of information about the future. We provide extensive computational results which demonstrate settings under which the performance of the proposed algorithm becomes attractive. |
| first_indexed | 2024-09-23T08:00:30Z |
| format | Article |
| id | mit-1721.1/134661 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:00:30Z |
| publishDate | 2021 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1346612023-02-28T21:39:29Z A stochastic algorithm for online bipartite resource allocation problems Legrain, Antoine Jaillet, Patrick Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Operations Research Center © 2016 Elsevier Ltd This paper deals with online resource allocation problems whereby buyers with a limited total budget want to purchase items which become available one at a time and which consume some amount of various limited resources upon allocation. A central resource allocation platform is in charge of allocating the items to the potential buyers, with the goal of maximizing the total revenue subject to budget and resource constraints. Sponsored search advertising is a typical example: in order to maximize revenue, search engines try to choose the best available advertisement to display on a web page resulting from a search query. Two main approaches have been proposed to address such online problems, depending on the assumptions made about the input sequence: one is trying to guarantee a performance against a worst case scenario (sometimes called the adversarial model); the other one, based on specific probabilistic assumptions about the input, is concerned with expected performance guarantee. However, combining the strengths of these two approaches could potentially outperform both in some settings. In this paper we propose such a practical method which goes beyond the adversarial model but requires only a limited amount of information about the future. We provide extensive computational results which demonstrate settings under which the performance of the proposed algorithm becomes attractive. 2021-10-27T20:06:03Z 2021-10-27T20:06:03Z 2016 2019-09-25T15:39:36Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134661 Legrain, A., and P. Jaillet. "A Stochastic Algorithm for Online Bipartite Resource Allocation Problems." Computers & Operations Research 75 (2016): 28-37. en 10.1016/J.COR.2016.05.004 Computers and Operations Research Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV MIT web domain |
| spellingShingle | Legrain, Antoine Jaillet, Patrick A stochastic algorithm for online bipartite resource allocation problems |
| title | A stochastic algorithm for online bipartite resource allocation problems |
| title_full | A stochastic algorithm for online bipartite resource allocation problems |
| title_fullStr | A stochastic algorithm for online bipartite resource allocation problems |
| title_full_unstemmed | A stochastic algorithm for online bipartite resource allocation problems |
| title_short | A stochastic algorithm for online bipartite resource allocation problems |
| title_sort | stochastic algorithm for online bipartite resource allocation problems |
| url | https://hdl.handle.net/1721.1/134661 |
| work_keys_str_mv | AT legrainantoine astochasticalgorithmforonlinebipartiteresourceallocationproblems AT jailletpatrick astochasticalgorithmforonlinebipartiteresourceallocationproblems AT legrainantoine stochasticalgorithmforonlinebipartiteresourceallocationproblems AT jailletpatrick stochasticalgorithmforonlinebipartiteresourceallocationproblems |