Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2502.20346 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929734662750208 |
|---|---|
| author | Bhawalkar, Kshipra Dean, Jeff Liaw, Christopher Mehta, Aranyak Patel, Neel |
| author_facet | Bhawalkar, Kshipra Dean, Jeff Liaw, Christopher Mehta, Aranyak Patel, Neel |
| contents | We envision a marketplace where diverse entities offer specialized "modules" through APIs, allowing users to compose the outputs of these modules for complex tasks within a given budget. This paper studies the market design problem in such an ecosystem, where module owners strategically set prices for their APIs (to maximize their profit) and a central platform orchestrates the aggregation of module outputs at query-time. One can also think about this as a first-price procurement auction with budgets. The first observation is that if the platform's algorithm is to find the optimal set of modules then this could result in a poor outcome, in the sense that there are price equilibria which provide arbitrarily low value for the user. We show that under a suitable version of the "bang-per-buck" algorithm for the knapsack problem, an $\varepsilon$-approximate equilibrium always exists, for any arbitrary $\varepsilon > 0$. Further, our first main result shows that with this algorithm any such equilibrium provides a constant approximation to the optimal value that the buyer could get under various constraints including (i) a budget constraint and (ii) a budget and a matroid constraint. Finally, we demonstrate that these efficient equilibria can be learned through decentralized price adjustments by module owners using no-regret learning algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20346 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Equilibria and Learning in Modular Marketplaces Bhawalkar, Kshipra Dean, Jeff Liaw, Christopher Mehta, Aranyak Patel, Neel Computer Science and Game Theory We envision a marketplace where diverse entities offer specialized "modules" through APIs, allowing users to compose the outputs of these modules for complex tasks within a given budget. This paper studies the market design problem in such an ecosystem, where module owners strategically set prices for their APIs (to maximize their profit) and a central platform orchestrates the aggregation of module outputs at query-time. One can also think about this as a first-price procurement auction with budgets. The first observation is that if the platform's algorithm is to find the optimal set of modules then this could result in a poor outcome, in the sense that there are price equilibria which provide arbitrarily low value for the user. We show that under a suitable version of the "bang-per-buck" algorithm for the knapsack problem, an $\varepsilon$-approximate equilibrium always exists, for any arbitrary $\varepsilon > 0$. Further, our first main result shows that with this algorithm any such equilibrium provides a constant approximation to the optimal value that the buyer could get under various constraints including (i) a budget constraint and (ii) a budget and a matroid constraint. Finally, we demonstrate that these efficient equilibria can be learned through decentralized price adjustments by module owners using no-regret learning algorithms. |
| title | Equilibria and Learning in Modular Marketplaces |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.20346 |