Automated Design of Affine Maximizer Mechanisms in Dynamic Settings
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_ | 1866910832077570048 |
|---|---|
| author | Curry, Michael Thoma, Vinzenz Chakrabarti, Darshan McAleer, Stephen Kroer, Christian Sandholm, Tuomas He, Niao Seuken, Sven |
| author_facet | Curry, Michael Thoma, Vinzenz Chakrabarti, Darshan McAleer, Stephen Kroer, Christian Sandholm, Tuomas He, Niao Seuken, Sven |
| contents | Dynamic mechanism design is a challenging extension to ordinary mechanism design in which the mechanism designer must make a sequence of decisions over time in the face of possibly untruthful reports of participating agents. Optimizing dynamic mechanisms for welfare is relatively well understood. However, there has been less work on optimizing for other goals (e.g. revenue), and without restrictive assumptions on valuations, it is remarkably challenging to characterize good mechanisms. Instead, we turn to automated mechanism design to find mechanisms with good performance in specific problem instances. In fact, the situation is similar even in static mechanism design. However, in the static case, optimization/machine learning-based automated mechanism design techniques have been successful in finding high-revenue mechanisms in cases beyond the reach of analytical results. We extend the class of affine maximizer mechanisms to MDPs where agents may untruthfully report their rewards. This extension results in a challenging bilevel optimization problem in which the upper problem involves choosing optimal mechanism parameters, and the lower problem involves solving the resulting MDP. Our approach can find truthful dynamic mechanisms that achieve strong performance on goals other than welfare, and can be applied to essentially any problem setting-without restrictions on valuations-for which RL can learn optimal policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08129 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Automated Design of Affine Maximizer Mechanisms in Dynamic Settings Curry, Michael Thoma, Vinzenz Chakrabarti, Darshan McAleer, Stephen Kroer, Christian Sandholm, Tuomas He, Niao Seuken, Sven Computer Science and Game Theory Dynamic mechanism design is a challenging extension to ordinary mechanism design in which the mechanism designer must make a sequence of decisions over time in the face of possibly untruthful reports of participating agents. Optimizing dynamic mechanisms for welfare is relatively well understood. However, there has been less work on optimizing for other goals (e.g. revenue), and without restrictive assumptions on valuations, it is remarkably challenging to characterize good mechanisms. Instead, we turn to automated mechanism design to find mechanisms with good performance in specific problem instances. In fact, the situation is similar even in static mechanism design. However, in the static case, optimization/machine learning-based automated mechanism design techniques have been successful in finding high-revenue mechanisms in cases beyond the reach of analytical results. We extend the class of affine maximizer mechanisms to MDPs where agents may untruthfully report their rewards. This extension results in a challenging bilevel optimization problem in which the upper problem involves choosing optimal mechanism parameters, and the lower problem involves solving the resulting MDP. Our approach can find truthful dynamic mechanisms that achieve strong performance on goals other than welfare, and can be applied to essentially any problem setting-without restrictions on valuations-for which RL can learn optimal policies. |
| title | Automated Design of Affine Maximizer Mechanisms in Dynamic Settings |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.08129 |