Data-Driven Mechanism Design using Multi-Agent Revealed Preferences
Luke Snow, Vikram Krishnamurthy
我们研究了一系列独立的单枪不合作游戏,其中代理玩由可调机制确定的均衡。 我们只观察平衡决策,没有实用程序的参数或分配知识,我们的目标是引导均衡走向社会最优性,并证明由于游戏的结构而不可能。 我们为该机制设计目标开发了一个自适应RL框架。 首先,我们对帕累托最优性进行了多代理揭示偏好测试,为公用事业的存在提供了必要和充分的条件,在这些实用程序下,经验观察的混合策略纳什均衡是社会最优的。 条件形成一个可处理的线性程序。 使用此功能,我们构建了一个 IRL 步骤,该步骤可以计算帕累托间隙、观察到的策略与帕累托最优度的距离,并将其与策略梯度更新相结合。 我们证明了全球将帕累托差距最小化的机制的趋同。 这产生了一个原则性的可成就性测试:如果给定的游戏可以实现社会最优性并观察到平衡,则算法1达到它;否则,该算法证明无法实现,同时与最接近社会最优性的机制融合。 我们还展示了我们的损失和强大的揭示偏好指标之间的紧密联系,允许通过既定的微观经济概念来解释算法的次优性。 最后,当只有有限数量的混合策略(部分策略规范)的i.d.样本可用时,我们得出收敛的浓度边界,并设计一个分布稳健的RL过程,以实现完全指定策略的机制设计目标。
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 optimalit...