Data-Driven Mechanism Design using Multi-Agent Revealed Preferences
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911254036086784 |
|---|---|
| author | Snow, Luke Krishnamurthy, Vikram |
| author_facet | Snow, Luke Krishnamurthy, Vikram |
| contents | We study a sequence of independent one-shot non-cooperative games where agents play equilibria determined by a tunable mechanism. Observing only equilibrium decisions, without parametric or distributional knowledge of utilities, we aim to steer equilibria towards social optimality, and to certify when this is impossible due to the game's structure. We develop an adaptive RL framework for this mechanism design objective. First, we derive a multi-agent revealed-preference test for Pareto optimality that gives necessary and sufficient conditions for the existence of utilities under which the empirically observed mixed-strategy Nash equilibria are socially optimal. The conditions form a tractable linear program. Using this, we build an IRL step that computes the Pareto gap, the distance of observed strategies from Pareto optimality, and couple it with a policy-gradient update. We prove convergence to a mechanism that globally minimizes the Pareto gap. This yields a principled achievability test: if social optimality is attainable for the given game and observed equilibria, Algorithm 1 attains it; otherwise, the algorithm certifies unachievability while converging to the mechanism closest to social optimality. We also show a tight link between our loss and robust revealed-preference metrics, allowing algorithmic suboptimality to be interpreted through established microeconomic notions. Finally, when only finitely many i.i.d. samples from mixed strategies (partial strategy specifications) are available, we derive concentration bounds for convergence and design a distributionally robust RL procedure that attains the mechanism-design objective for the fully specified strategies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15391 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Data-Driven Mechanism Design using Multi-Agent Revealed Preferences Snow, Luke Krishnamurthy, Vikram Computer Science and Game Theory General Economics Economics We study a sequence of independent one-shot non-cooperative games where agents play equilibria determined by a tunable mechanism. Observing only equilibrium decisions, without parametric or distributional knowledge of utilities, we aim to steer equilibria towards social optimality, and to certify when this is impossible due to the game's structure. We develop an adaptive RL framework for this mechanism design objective. First, we derive a multi-agent revealed-preference test for Pareto optimality that gives necessary and sufficient conditions for the existence of utilities under which the empirically observed mixed-strategy Nash equilibria are socially optimal. The conditions form a tractable linear program. Using this, we build an IRL step that computes the Pareto gap, the distance of observed strategies from Pareto optimality, and couple it with a policy-gradient update. We prove convergence to a mechanism that globally minimizes the Pareto gap. This yields a principled achievability test: if social optimality is attainable for the given game and observed equilibria, Algorithm 1 attains it; otherwise, the algorithm certifies unachievability while converging to the mechanism closest to social optimality. We also show a tight link between our loss and robust revealed-preference metrics, allowing algorithmic suboptimality to be interpreted through established microeconomic notions. Finally, when only finitely many i.i.d. samples from mixed strategies (partial strategy specifications) are available, we derive concentration bounds for convergence and design a distributionally robust RL procedure that attains the mechanism-design objective for the fully specified strategies. |
| title | Data-Driven Mechanism Design using Multi-Agent Revealed Preferences |
| topic | Computer Science and Game Theory General Economics Economics |
| url | https://arxiv.org/abs/2404.15391 |