Posted Price Mechanisms for Online Allocation with Diseconomies of Scale
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909476233150464 |
|---|---|
| author | Jazi, Hossein Nekouyan Sun, Bo Boutaba, Raouf Tan, Xiaoqi |
| author_facet | Jazi, Hossein Nekouyan Sun, Bo Boutaba, Raouf Tan, Xiaoqi |
| contents | This paper addresses the online $k$-selection problem with diseconomies of scale (OSDoS), where a seller seeks to maximize social welfare by optimally pricing items for sequentially arriving buyers, accounting for increasing marginal production costs. Previous studies have investigated deterministic dynamic pricing mechanisms for such settings. However, significant challenges remain, particularly in achieving optimality with small or finite inventories and developing effective randomized posted price mechanisms. To bridge this gap, we propose a novel randomized dynamic pricing mechanism for OSDoS, providing a tighter lower bound on the competitive ratio compared to prior work. Our approach ensures optimal performance in small inventory settings (i.e., when $k$ is small) and surpasses existing online mechanisms in large inventory settings (i.e., when $k$ is large), leading to the best-known posted price mechanism for optimizing online selection and allocation with diseconomies of scale across varying inventory sizes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02543 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Posted Price Mechanisms for Online Allocation with Diseconomies of Scale Jazi, Hossein Nekouyan Sun, Bo Boutaba, Raouf Tan, Xiaoqi Computer Science and Game Theory Data Structures and Algorithms This paper addresses the online $k$-selection problem with diseconomies of scale (OSDoS), where a seller seeks to maximize social welfare by optimally pricing items for sequentially arriving buyers, accounting for increasing marginal production costs. Previous studies have investigated deterministic dynamic pricing mechanisms for such settings. However, significant challenges remain, particularly in achieving optimality with small or finite inventories and developing effective randomized posted price mechanisms. To bridge this gap, we propose a novel randomized dynamic pricing mechanism for OSDoS, providing a tighter lower bound on the competitive ratio compared to prior work. Our approach ensures optimal performance in small inventory settings (i.e., when $k$ is small) and surpasses existing online mechanisms in large inventory settings (i.e., when $k$ is large), leading to the best-known posted price mechanism for optimizing online selection and allocation with diseconomies of scale across varying inventory sizes. |
| title | Posted Price Mechanisms for Online Allocation with Diseconomies of Scale |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.02543 |