論文の概要: Mechanisms that play a game, not toss a coin
- arxiv url: http://arxiv.org/abs/2308.10413v1
- Date: Mon, 21 Aug 2023 01:43:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 15:27:54.883331
- Title: Mechanisms that play a game, not toss a coin
- Title(参考訳): コインを投げるのではなく、ゲームをするメカニズム
- Authors: Toby Walsh
- Abstract要約: 本稿では,コインを投げる代わりにエージェントがゲームをしてランダム化メカニズムをデランドマイズすることを提案する。
このデランドマイゼーションは、元のメカニズムのよい規範的特性の多くを保っているが、決定論的で容易に監査できるメカニズムを与える。
- 参考スコア(独自算出の注目度): 18.168659230989384
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Randomized mechanisms can have good normative properties compared to their
deterministic counterparts. However, randomized mechanisms are problematic in
several ways such as in their verifiability. We propose here to derandomize
such mechanisms by having agents play a game instead of tossing a coin. The
game is designed so an agent's best action is to play randomly, and this play
then injects ``randomness'' into the mechanism. This derandomization retains
many of the good normative properties of the original randomized mechanism but
gives a mechanism that is deterministic and easy, for instance, to audit. We
consider three related methods to derandomize randomized mechanism in six
different domains: voting, facility location, task allocation, school choice,
peer selection, and resource allocation. We propose a number of novel
derandomized mechanisms for these six domains with good normative properties.
Each mechanism has a mixed Nash equilibrium in which agents play a modular
arithmetic game with an uniform mixed strategy. In all but one mixed Nash
equilibrium, agents report their preferences over the original problem
sincerely. The derandomized methods are thus ``quasi-strategy proof''. In one
domain, we additionally show that a new and desirable normative property
emerges as a result of derandomization.
- Abstract(参考訳): ランダム化機構は、決定論的機構と比較して良い規範的特性を持つことができる。
しかし、ランダム化されたメカニズムは、検証可能性などいくつかの方法で問題となる。
ここでは,コインを投げるのではなく,エージェントにゲームをさせる仕組みを提案する。
ゲームはエージェントの最善のアクションがランダムにプレイするように設計され、このプレイはメカニズムに ``randomness'' を注入する。
この非ランダム化は、元のランダム化機構の良質な規範的性質の多くを保ちながら、決定論的で、例えば監査が容易なメカニズムを与える。
ランダム化メカニズムを6つの異なる領域でデランドマイズする方法として,投票,施設配置,タスク割り当て,学校選択,ピア選択,リソース割り当ての3つを検討した。
本稿では,この6つの領域において,ノルマ的性質に優れた非ランダム化機構をいくつか提案する。
各機構は混合ナッシュ平衡を持ち、エージェントは一様混合戦略を持つモジュラーな算術ゲームを行う。
1つの混合ナッシュ均衡を除いて、エージェントは元の問題を誠実に報告する。
分割された方法は ``quasi-strategy proof''' である。
1つの領域において、さらに、新しい望ましい規範的性質が非ランダム化の結果出現することを示す。
関連論文リスト
- Strategic Resource Selection with Homophilic Agents [68.19497461624208]
類似エージェントとの共同資源利用を目指す異種エージェントを用いたリソース選択ゲームを提案する。
モデルでは,異なるタイプのエージェントを考慮し,その決定的特徴はユーザ間の同一型エージェントの割合である。
このような有界な有理性はゲーム理論上有利な性質を持つことを示す。
論文 参考訳(メタデータ) (2023-05-01T14:14:58Z) - Shortcomings of Top-Down Randomization-Based Sanity Checks for
Evaluations of Deep Neural Network Explanations [67.40641255908443]
モデルランダム化に基づく正当性チェックの限界を,説明書の評価のために同定する。
トップダウンモデルランダム化は、フォワードパスアクティベーションのスケールを高い確率で保存する。
論文 参考訳(メタデータ) (2022-11-22T18:52:38Z) - Random Rank: The One and Only Strategyproof and Proportionally Fair
Randomized Facility Location Mechanism [103.36492220921109]
我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。
次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。
我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
論文 参考訳(メタデータ) (2022-05-30T00:51:57Z) - Using Non-Stationary Bandits for Learning in Repeated Cournot Games with
Non-Stationary Demand [11.935419090901524]
本稿では,非定常要求の繰り返しCournotゲームについてモデル化する。
エージェントが選択できる武器/アクションのセットは、個別の生産量を表す。
本稿では,よく知られた$epsilon$-greedyアプローチに基づく,新しいアルゴリズム"Adaptive with Weighted Exploration (AWE) $epsilon$-greedy"を提案する。
論文 参考訳(メタデータ) (2022-01-03T05:51:47Z) - Modelling Cournot Games as Multi-agent Multi-armed Bandits [4.751331778201811]
繰り返しCournot oligopolyゲームにおけるマルチエージェントマルチアーム・バンディット(MA-MAB)の設定について検討した。
私たちは、$epsilon$-greedyアプローチが、従来のMABアプローチよりもより実行可能な学習メカニズムを提供することに気付きました。
順序付けられたアクション空間を利用する新しいアプローチとして、$epsilon$-greedy+HLと$epsilon$-greedy+ELを提案する。
論文 参考訳(メタデータ) (2022-01-01T22:02:47Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳(メタデータ) (2021-07-30T15:25:13Z) - Rational Verification for Probabilistic Systems [2.4254101826561847]
我々は確率的システムにおける合理的な検証の理論とアルゴリズムを開発する。
複雑なマルチエージェント環境における不確実性とランダム性をモデル化するための並列ゲーム(CSG)に焦点を当てる。
論文 参考訳(メタデータ) (2021-07-19T19:24:16Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳(メタデータ) (2020-04-19T18:00:58Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z) - Randomization matters. How to defend against strong adversarial attacks [17.438104235331085]
敵の攻撃と防御は、古典的な結果が適用されない無限ゼロサムゲームを形成することを示す。
本研究の防御方法は,最先端攻撃に対する対人訓練を著しく上回っていることを示す。
論文 参考訳(メタデータ) (2020-02-26T15:31:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。