Toward Understanding the Value of Anarchy: Empirical Studies on Best Response Dynamics

概要

We study experimental results of best response dynamics (BRD) in randomly generated weighted action networked multiagent optimization problems where agent utility is the agent's marginal contribution to the system objective. We compare those results to the Price of Anarchy (PoA) established in the literature for marginal contribution and to the expected value of randomly choosing from the available equilibria. PoA is used as a metric to describe the performance of various solutions to multiagent optimization problems, but the utility of this metric may be overrated if such worst-case instances are rare in practice. Our study provides evidence to support this doubt, showing that simple best response mechanics tend to out perform the PoA prediction and a uniform random equilibrium selection, even when agents are unable to observe all other agents' actions. In the process of seeking a more ideal metric, we discover that BRD appears to perform better than average. That is, when multiple equilibria exist, BRD appears to be biased toward the higher-performance ones. This evidence also demonstrates that further investigation into a more robust metric for multiagent optimization solutions is warranted and pushes us to understand whether the bias toward better equilibria hold in more general cases.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Toward Understanding the Value of Anarchy: Empirical Studies on Best Response Dynamics

# 概要
We study experimental results of best response dynamics (BRD) in randomly generated weighted action networked multiagent optimization problems where agent utility is the agent's marginal contribution…

# 原典
https://arxiv.org/abs/2610.38081

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。