論文の概要: Trading Transforms of Non-weighted Simple Games and Integer Weights of
Weighted Simple Games
- arxiv url: http://arxiv.org/abs/2101.07621v1
- Date: Tue, 19 Jan 2021 13:54:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-22 11:15:04.111221
- Title: Trading Transforms of Non-weighted Simple Games and Integer Weights of
Weighted Simple Games
- Title（参考訳）: 非重み付き単純ゲームのトレーディング変換と重み付き単純ゲームの整数重み付け
- Authors: Akihiro Kawana and Tomomi Matsui
- Abstract要約: 我々は、有限サイズの取引変換が存在する場合にのみ、単純なゲームが非重み付けであることを示します。
また,選手数が5人以下である場合,我々の限界が厳密であることも示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper is concerned with simple games. One of the fundamental questions
regarding simple games is that of what makes a simple game a weighted majority
game. Taylor and Zwicker (1992) showed that a simple game is non-weighted if
and only if there exists a trading transform of finite size. They also provided
an upper bound on the size of such a trading transform, if it exists. Gvozdeva
and Slinko (2009) improved on that upper bound. Their proof employs a property
of linear inequalities demonstrated by Muroga (1971). We provide a new proof of
the existence of a trading transform when a given simple game is non-weighted.
Our proof employs Farkas' lemma (1894), and yields an improved upper bound on
the size of a trading transform.
We also discuss an integer weights representation of a weighted simple game,
and improve on the bounds obtained by Muroga (1971). We show that our bounds
are tight when the number of players is less than or equal to five, based on
the computational results obtained by Kurz (2012).
Lastly, we deal with the problem of finding an integer weights representation
under the assumption that we have minimal winning coalitions and maximal losing
coalitions. We discuss a performance of a rounding method.
- Abstract（参考訳）: 本論文は単純なゲームについて述べる。
単純なゲームに関する基本的な質問の1つは、単純なゲームを重み付けされた多数派ゲームにすることである。
Taylor and Zwicker (1992) は単純ゲームが非重み付きであることと有限サイズのトレーディング変換が存在することを証明した。
彼らはまた、もし存在するならば、そのようなトレーディング変換のサイズに上限を与えた。
Gvozdeva と Slinko (2009) はその上限を改良した。
これらの証明は、Muroga (1971) によって証明された線型不等式の性質を用いる。
与えられた単純なゲームが重み付けされていない場合、トレーディングトランスフォーメーションが存在することの新たな証明を提供する。
我々の証明はFarkasの補題(1894年)を用いており、取引変換のサイズに改善された上限を与える。
また、重み付き単純ゲームの整数重み表現についても論じ、Muroga (1971) によって得られた境界値を改善する。
kurz (2012) によって得られた計算結果に基づいて、プレイヤー数が5人以下であれば、我々の境界はタイトであることを示した。
最後に、我々は最小の勝利連立と最大負け連立があると仮定して整数重み表現を見つける問題を扱う。
ラウンドリング法の性能について論じる。
関連論文リスト
- Pruning Small Pre-Trained Weights Irreversibly and Monotonically Impairs
"Difficult" Downstream Tasks in LLMs [71.56345106591789]
大型言語モデル(LLM)の重みには、かなりの冗長性が含まれていると信じられている。
本稿では,下流の難題に対処する上で必要となる重要な知識を包含する,事前訓練されたモデル重みの小さなマグニチュード重みについて述べる。
論文 参考訳（メタデータ） (2023-09-29T22:55:06Z) - Function Approximation for Solving Stackelberg Equilibrium in Large
Perfect Information Games [115.77438739169155]
汎用ゲームにおける状態値関数の一般化であるtextitEnforceable Payoff Frontier (EPF) の学習を提案する。
Stackelbergの設定にFAを適用する最初の方法です。
論文 参考訳（メタデータ） (2022-12-29T19:05:50Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳（メタデータ） (2022-09-16T13:59:42Z) - Turning Mathematics Problems into Games: Reinforcement Learning and
Gr\"obner bases together solve Integer Feasibility Problems [4.746723775952672]
我々は、線形方程式と不等式の系が整数値の解を持つかどうかを判定する問題である整数実現可能性問題を考察する。
本稿では,エージェントが整数実現可能性問題と同等のゲームをすることができる,新しい代数的強化学習フレームワークについて述べる。
概念実証として、エージェントが2方向テーブルの最も単純なバージョンをうまくプレイできることを実験で実証する。
論文 参考訳（メタデータ） (2022-08-25T16:24:34Z) - Principal Trade-off Analysis [79.16635054977068]
低次元特徴空間にゲームを埋め込む分解法であるPTA(Principal Trade-off Analysis)を示す。
PTAは2次元特徴平面の対の重み付け和として任意の2-player 0-sumゲームを表す。
ゲーム四重奏におけるPTAの有効性を示す(Kuhn poker, RPS+2, Blotto, Pokemon)。
論文 参考訳（メタデータ） (2022-06-09T18:16:28Z) - Public Information Representation for Adversarial Team Games [31.29335755664997]
対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。
本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。
この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
論文 参考訳（メタデータ） (2022-01-25T15:07:12Z) - Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game
Encodings [1.471992435706872]
ニバーは、その可算和と可算性において、不分ゲーム間の戦略的相互作用の完全な特徴づけを提供する。
Generalized Geography が自然クラス $calIP$ に対して完備であることを証明する。
また、$calIP$のすべてのPSPACE完全ルールセットが$calIP$のSprague-Grundy-completeであることも示しています。
論文 参考訳（メタデータ） (2021-09-12T22:12:13Z) - Positional Games and QBF: A Polished Encoding [0.897438370260135]
ポジショナルゲームは、Tic-tac-toeとその一般化を含む2プレイヤーゲームのクラスである。
本稿では,これらのゲームを量子ブール式 (QBF) に符号化する手法を提案する。
本手法は,従来のQBFエンコーディングよりも複数の方法で改善されている。
論文 参考訳（メタデータ） (2020-05-11T13:32:03Z) - Is Multihop QA in DiRe Condition? Measuring and Reducing Disconnected
Reasoning [50.114651561111245]
モデルは、しばしば、複数のサポート事実をまたいで情報を接続することなく、正しい回答を生成するためにデータセットアーティファクトを利用する。
我々は、支持事実のサブセットにまたがる不連結推論のような望ましくない振る舞いを定式化する。
実験によると、読書理解設定においてマルチホップQAがあまり進歩していないことが示唆されている。
論文 参考訳（メタデータ） (2020-05-02T11:01:07Z) - Counterexamples to the Low-Degree Conjecture [80.3668228845075]
ホプキンスの予想は、ある高次元仮説テスト問題に対して、非時間アルゴリズムはいわゆる「単純な統計」よりも優れていると仮定する。
この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを囲む信念を定式化する。
論文 参考訳（メタデータ） (2020-04-17T21:08:11Z) - Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games [0.4895118383237099]
架空のプレイは、2つのプレイヤーゼロサムゲームのような特定のゲームクラスにおいてナッシュ均衡に収束することが保証される。
実のところ、架空の遊びは、様々なゲームクラスやサイズに対するナッシュ均衡近似の改善につながることを示す。
論文 参考訳（メタデータ） (2020-01-30T03:47:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。