Online market intermediation
We study a dynamic market setting where an intermediary interacts with an unknown large sequence of agents that can be either sellers or buyers: their identities, as well as the sequence length n, are decided in an adversarial, online way. Each agent is interested in trading a single item, and all i...
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Conference item |
| Gepubliceerd in: |
Schloss Dagstuhl
2017
|
| _version_ | 1826304726145171456 |
|---|---|
| author | Giannakopoulos, Y Koutsoupias, E Lazos, FL |
| author_facet | Giannakopoulos, Y Koutsoupias, E Lazos, FL |
| author_sort | Giannakopoulos, Y |
| collection | OXFORD |
| description | We study a dynamic market setting where an intermediary interacts with an unknown large sequence of agents that can be either sellers or buyers: their identities, as well as the sequence length n, are decided in an adversarial, online way. Each agent is interested in trading a single item, and all items in the market are identical. The intermediary has some prior, incomplete knowledge of the agents’ values for the items: all seller values are independently drawn from the same distribution FS, and all buyer values from FB. The two distributions may differ, and we make common regularity assumptions, namely that FB is MHR and FS is log-concave. We focus on online, posted-price mechanisms, and analyse two objectives: that of maximizing the intermediary’s profit and that of maximizing the social welfare, under a competitive analysis benchmark. First, on the negative side, for general agent sequences we prove tight competitive ratios of Θ( √ n) and Θ(ln n), respectively for the two objectives. On the other hand, under the extra assumption that the intermediary knows some bound α on the ratio between the number of sellers and buyers, we design asymptotically optimal online mechanisms with competitive ratios of 1 + o(1) and 4, respectively. Additionally, we study the model where the number of items that can be stored in stock throughout the execution is bounded, in which case the competitive ratio for the profit is improved to O(ln n). |
| first_indexed | 2024-03-07T06:22:10Z |
| format | Conference item |
| id | oxford-uuid:f30f3623-3f7d-41e6-a27a-4617a66070c6 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:22:10Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:f30f3623-3f7d-41e6-a27a-4617a66070c62022-03-27T12:09:02ZOnline market intermediationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:f30f3623-3f7d-41e6-a27a-4617a66070c6Symplectic Elements at OxfordSchloss Dagstuhl2017Giannakopoulos, YKoutsoupias, ELazos, FLWe study a dynamic market setting where an intermediary interacts with an unknown large sequence of agents that can be either sellers or buyers: their identities, as well as the sequence length n, are decided in an adversarial, online way. Each agent is interested in trading a single item, and all items in the market are identical. The intermediary has some prior, incomplete knowledge of the agents’ values for the items: all seller values are independently drawn from the same distribution FS, and all buyer values from FB. The two distributions may differ, and we make common regularity assumptions, namely that FB is MHR and FS is log-concave. We focus on online, posted-price mechanisms, and analyse two objectives: that of maximizing the intermediary’s profit and that of maximizing the social welfare, under a competitive analysis benchmark. First, on the negative side, for general agent sequences we prove tight competitive ratios of Θ( √ n) and Θ(ln n), respectively for the two objectives. On the other hand, under the extra assumption that the intermediary knows some bound α on the ratio between the number of sellers and buyers, we design asymptotically optimal online mechanisms with competitive ratios of 1 + o(1) and 4, respectively. Additionally, we study the model where the number of items that can be stored in stock throughout the execution is bounded, in which case the competitive ratio for the profit is improved to O(ln n). |
| spellingShingle | Giannakopoulos, Y Koutsoupias, E Lazos, FL Online market intermediation |
| title | Online market intermediation |
| title_full | Online market intermediation |
| title_fullStr | Online market intermediation |
| title_full_unstemmed | Online market intermediation |
| title_short | Online market intermediation |
| title_sort | online market intermediation |
| work_keys_str_mv | AT giannakopoulosy onlinemarketintermediation AT koutsoupiase onlinemarketintermediation AT lazosfl onlinemarketintermediation |