Learning to Maximize Gains From Trade in Small Markets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913397712355328 |
|---|---|
| author | Babaioff, Moshe Frey, Amitai Nisan, Noam |
| author_facet | Babaioff, Moshe Frey, Amitai Nisan, Noam |
| contents | We study the problem of designing a two-sided market (double auction) to maximize the gains from trade (social welfare) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our goal is to do so for an unknown distribution from which we are given a polynomial number of samples. Our first result is a general impossibility for the case of correlated distributions of values even between just one seller and two buyers, in contrast to the case of one seller and one buyer (bilateral trade) where this is possible. Our second result is an efficient learning algorithm for one seller and two buyers in the case of independent distributions which is based on a novel algorithm for computing optimal mechanisms for finitely supported and explicitly given independent distributions. Both results rely heavily on characterizations of (dominant-strategy) incentive compatible mechanisms that are strongly budget-balanced. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11596 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning to Maximize Gains From Trade in Small Markets Babaioff, Moshe Frey, Amitai Nisan, Noam Computer Science and Game Theory Artificial Intelligence Machine Learning F.0; I.2; I.2.6; J.4 We study the problem of designing a two-sided market (double auction) to maximize the gains from trade (social welfare) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our goal is to do so for an unknown distribution from which we are given a polynomial number of samples. Our first result is a general impossibility for the case of correlated distributions of values even between just one seller and two buyers, in contrast to the case of one seller and one buyer (bilateral trade) where this is possible. Our second result is an efficient learning algorithm for one seller and two buyers in the case of independent distributions which is based on a novel algorithm for computing optimal mechanisms for finitely supported and explicitly given independent distributions. Both results rely heavily on characterizations of (dominant-strategy) incentive compatible mechanisms that are strongly budget-balanced. |
| title | Learning to Maximize Gains From Trade in Small Markets |
| topic | Computer Science and Game Theory Artificial Intelligence Machine Learning F.0; I.2; I.2.6; J.4 |
| url | https://arxiv.org/abs/2401.11596 |