Data-Driven Automated Mechanism Design using Multi-Agent Revealed Preferences

Luke Snow and Vikram Krishnamurthy

Papers from arXiv.org

Abstract: Suppose a black box, representing multiple agents, generates decisions from a mixed-strategy Nash equilibrium of a game. Assume that we can choose the input vector to the black box and this affects the utilities of the agents, but we do not know the utilities of the individual agents. By viewing the decisions from the black box, how can we steer the Nash equilibrium to a socially optimal point? This paper constructs a reinforcement learning (RL) framework for adaptively achieving this mechanism design objective. We first derive a novel multi-agent revealed preference test for Pareto optimality -- this yields necessary and sufficient conditions for the existence of utility functions under which empirically observed mixed-strategy Nash equilibria are socially optimal. These conditions take the form of a testable linear program, and this result is of independent interest. We utilize this result to construct an inverse reinforcement learning (IRL) step to determine the Pareto gap, i.e., the distance of observed strategies from Pareto optimality. We pair this IRL step with an RL policy gradient algorithm and prove convergence to a mechanism which minimizes the Pareto gap, thereby inducing social optimality in equilibria strategies. We also reveal an intimate connection between our constructed loss function and several robust revealed preference metrics; this allows us to reason about algorithmic suboptimality through the lens of these well-established microeconomic principles. Finally, in the case when only finitely many i.i.d. samples from mixed-strategies (partial strategy specifications) are available, we derive concentration bounds for our algorithm's convergence, and we construct a distributionally robust RL procedure which achieves mechanism design for the fully specified strategies.

Date: 2024-04, Revised 2025-03
New Economics Papers: this item is included in nep-des, nep-gth, nep-mic and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2404.15391 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2404.15391

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().