Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916741128388608 |
|---|---|
| author | Osogami, Takayuki Kinoshita, Hirota Wasserkrug, Segev |
| author_facet | Osogami, Takayuki Kinoshita, Hirota Wasserkrug, Segev |
| contents | We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design that satisfies efficiency, incentive compatibility, strong budget balance (SBB), and individual rationality (IR), where SBB and IR are enforced in expectation. These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation. However, evaluating a key term in the solutions requires exponentially many optimization steps as the number of players $N$ increases. We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem and develop a probably approximately correct (PAC) estimator with asymptotically optimal sample complexity. This MAB-based approach reduces the optimization complexity from exponential to $O(N\log N)$. Numerical experiments confirm that our method efficiently computes mechanisms with the target properties, scaling to problems with up to $N=128$ players -- substantially improving over prior work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00345 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits Osogami, Takayuki Kinoshita, Hirota Wasserkrug, Segev Computer Science and Game Theory Machine Learning We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design that satisfies efficiency, incentive compatibility, strong budget balance (SBB), and individual rationality (IR), where SBB and IR are enforced in expectation. These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation. However, evaluating a key term in the solutions requires exponentially many optimization steps as the number of players $N$ increases. We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem and develop a probably approximately correct (PAC) estimator with asymptotically optimal sample complexity. This MAB-based approach reduces the optimization complexity from exponential to $O(N\log N)$. Numerical experiments confirm that our method efficiently computes mechanisms with the target properties, scaling to problems with up to $N=128$ players -- substantially improving over prior work. |
| title | Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2412.00345 |