論文の概要: Game-Theoretically Secure Distributed Protocols for Fair Allocation in Coalitional Games
- arxiv url: http://arxiv.org/abs/2412.19192v1
- Date: Thu, 26 Dec 2024 12:13:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-30 17:24:07.917316
- Title: Game-Theoretically Secure Distributed Protocols for Fair Allocation in Coalitional Games
- Title（参考訳）: Coalitional Gamesにおけるフェアアロケーションのためのゲーム理論的セキュア分散プロトコル
- Authors: T-H. Hubert Chan, Qipeng Kuang, Quan Xue,
- Abstract要約: 我々は,Shapley値に近似して乗算誤差を小さくする連立ゲームに対して,ゲーム理論的にセキュアなプロトコルを検討する。
ゲーム理論上のマクシミン・セキュリティの概念は、たとえ他の全てのプレイヤーが敵に感受性があるとしても、正直なプレイヤーの報酬を保証するために提案されている。
- 参考スコア（独自算出の注目度）: 2.1779479916071067
- License:
- Abstract: We consider game-theoretically secure distributed protocols for coalition games that approximate the Shapley value with small multiplicative error. Since all known existing approximation algorithms for the Shapley value are randomized, it is a challenge to design efficient distributed protocols among mutually distrusted players when there is no central authority to generate unbiased randomness. The game-theoretic notion of maximin security has been proposed to offer guarantees to an honest player's reward even if all other players are susceptible to an adversary. Permutation sampling is often used in approximation algorithms for the Shapley value. A previous work in 1994 by Zlotkin et al. proposed a simple constant-round distributed permutation generation protocol based on commitment scheme, but it is vulnerable to rushing attacks. The protocol, however, can detect such attacks. In this work, we model the limited resources of an adversary by a violation budget that determines how many times it can perform such detectable attacks. Therefore, by repeating the number of permutation samples, an honest player's reward can be guaranteed to be close to its Shapley value. We explore both high probability and expected maximin security. We obtain an upper bound on the number of permutation samples for high probability maximin security, even with an unknown violation budget. Furthermore, we establish a matching lower bound for the weaker notion of expected maximin security in specific permutation generation protocols. We have also performed experiments on both synthetic and real data to empirically verify our results.
- Abstract（参考訳）: 我々は,Shapley値に近似して乗算誤差を小さくする連立ゲームに対して,ゲーム理論的にセキュアな分散プロトコルを検討する。
既知のShapley値に対する近似アルゴリズムはすべてランダム化されているため、不偏性を生成する中央権限が存在しない場合、互いに不信頼なプレイヤー間で効率的な分散プロトコルを設計することは困難である。
ゲーム理論上のマクシミン・セキュリティの概念は、たとえ他の全てのプレイヤーが敵に感受性があるとしても、正直なプレイヤーの報酬を保証するために提案されている。
置換サンプリングはしばしばShapley値の近似アルゴリズムで用いられる。
Zlotkinらによる1994年の以前の研究は、コミットスキームに基づく単純な定数単位の分散置換生成プロトコルを提案したが、急激な攻撃には弱い。
しかし、このプロトコルはそのような攻撃を検出することができる。
本研究では,このような攻撃を何回検出できるかを決定する,違反予算による敵の限られた資源をモデル化する。
したがって、置換サンプルの数を繰り返すことで、正直なプレイヤーの報酬がそのシェープリー値に近いことを保証できる。
我々は高い確率と期待される最大セキュリティを探索する。
我々は、未知の違反予算であっても、高い確率で最大セキュリティを確保するために、置換サンプルの数を上限とする。
さらに、特定の置換生成プロトコルにおいて、期待される最大セキュリティというより弱い概念に対する一致した下位境界を確立する。
また、人工データと実データの両方で実験を行い、その結果を実証的に検証した。
関連論文リスト
- Sequential Manipulation Against Rank Aggregation: Theory and Algorithm [119.57122943187086]
脆弱なデータ収集プロセスに対するオンライン攻撃を活用します。
ゲーム理論の観点からは、対決シナリオは分布的に堅牢なゲームとして定式化される。
提案手法は,ランクアグリゲーション手法の結果を逐次的に操作する。
論文 参考訳（メタデータ） (2024-07-02T03:31:21Z) - Device independent security of quantum key distribution from
monogamy-of-entanglement games [10.60608983034705]
非ローカルゲームのための汎用デバイス独立量子鍵分配プロトコルを提案する。
我々は,プロトコルの秘密鍵レートを有限かつ三分割的に最適化する。
我々のプロトコルは、雑音を最大2.2%まで非偏極化するために堅牢であることを示し、魔法の正方形の量子鍵分布に対する一般的な攻撃に対する最初の境界を提供する。
論文 参考訳（メタデータ） (2023-12-07T06:48:38Z) - Improvements on Device Independent and Semi-Device Independent Protocols
of Randomness Expansion [0.0]
デバイス独立性(DI)およびセミデバイス独立性(セミデバイス独立性)プロトコルについて論じる。
出力ランダムネス率、セキュリティ、場合によってはその両方で既存のプロトコルを超える拡張DIと半DIプロトコルを導入します。
注目すべき貢献は、CHSH不等式違反に基づくDIプロトコルの有限ラウンドランダム化率を大幅に向上させる、入力ランダム化をリサイクルするランダム性拡張プロトコルの導入である。
論文 参考訳（メタデータ） (2023-11-22T17:03:04Z) - A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks [0.6216023343793144]
ランダム性の分散生成のためのプロトコルを提供する。
無信頼であり、不偏乱数を生成する。
また、タンパー耐性があり、出力を変更したり、その分布に影響を与えない。
論文 参考訳（メタデータ） (2023-09-20T12:21:39Z) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
おもちゃの光ファイバーをベースとしたセットアップを用いてバイナリシリーズを生成し、そのランダム度をVilleの原理に従って評価する。
標準統計指標の電池、ハースト、コルモゴロフ複雑性、最小エントロピー、埋め込みのTakensarity次元、および拡張ディッキー・フラーとクワイアトコフスキー・フィリップス・シュミット・シン(英語版)でテストされ、ステーション指数をチェックする。
Toeplitz 抽出器を不規則級数に適用することにより得られる系列のランダム性のレベルは、非還元原料のレベルと区別できない。
論文 参考訳（メタデータ） (2022-08-31T17:39:29Z) - Conformal Off-Policy Prediction in Contextual Bandits [54.67508891852636]
コンフォーマルなオフ政治予測は、新しい目標ポリシーの下で、結果に対する信頼できる予測間隔を出力することができる。
理論上の有限サンプル保証は、標準的な文脈的バンディットの設定を超える追加の仮定をすることなく提供する。
論文 参考訳（メタデータ） (2022-06-09T10:39:33Z) - Algorithms for Adaptive Experiments that Trade-off Statistical Analysis
with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
トンプソンサンプリングのようなマルチアームバンディットアルゴリズムは適応的な実験を行うのに利用できる。
統計的解析のための一様ランダム化の利点を組み合わせた2つのアルゴリズムを探索する2つのアーム実験のシミュレーションを提案する。
論文 参考訳（メタデータ） (2021-12-15T22:11:58Z) - Improved device-independent randomness expansion rates using two sided
randomness [3.4376560669160394]
デバイスに依存しないランダム性拡張プロトコルは、初期乱数列を取り、より長い乱数列を生成することを目的としている。
両面のランダム性によって得られる改善の可能性を検討する。
また、入力ランダム性を再利用する修正プロトコルについても検討する。
論文 参考訳（メタデータ） (2021-03-12T19:49:17Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z) - Robust Stochastic Bandit Algorithms under Probabilistic Unbounded
Adversarial Attack [41.060507338755784]
本稿では,各ラウンドで敵が一定の確率で攻撃する攻撃モデルについて検討する。
そこで我々は, 中央値および探索支援UPBアルゴリズム(med-E-UCB)と中央値の$epsilon$-greedyアルゴリズム(med-$epsilon$-greedy)を提案する。
どちらのアルゴリズムも上記の攻撃モデルに対して確実に堅牢である。より具体的には、どちらのアルゴリズムも$mathcalO(log T)$ pseudo-regret (i.e.)を達成することを示す。
論文 参考訳（メタデータ） (2020-02-17T19:21:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。