論文の概要: 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つの領域において、さらに、新しい望ましい規範的性質が非ランダム化の結果出現することを示す。

関連論文リスト

• Correcting Subverted Random Oracles [55.4766447972367]
  簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。 この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2024-04-15T04:01:50Z)
• A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks [0.6216023343793144]
  ランダム性の分散生成のためのプロトコルを提供する。 無信頼であり、不偏乱数を生成する。 また、タンパー耐性があり、出力を変更したり、その分布に影響を与えない。
  論文  参考訳（メタデータ） (2023-09-20T12:21:39Z)
• Strategic Resource Selection with Homophilic Agents [48.83208975886834]
  類似エージェントとの共同資源利用を目指す異種エージェントを用いたリソース選択ゲームを提案する。 モデルでは,異なるタイプのエージェントを考慮し,その決定的特徴はユーザ間の同一型エージェントの割合である。 このような有界な有理性はゲーム理論上有利な性質を持つことを示す。
  論文  参考訳（メタデータ） (2023-05-01T14:14:58Z)
• Randomness: what is it and why does it matter? [0.0]
  広く受け入れられているランダム性の定義は科学的厳密さに欠けており、その結果は疑わしい。 本稿では,乱数生成自体の物理過程に着目した情報理論に基づくランダム性の定義を提案する。 ランダム性偏差」と呼ばれる新しい量により、乱数生成プロセスや装置の品質の実用的な測定が可能となる。
  論文  参考訳（メタデータ） (2023-03-14T16:38:16Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。