論文の概要: Parameterized Analysis of Bribery in Challenge the Champ Tournaments
- arxiv url: http://arxiv.org/abs/2403.17587v1
- Date: Tue, 26 Mar 2024 10:53:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-27 15:47:16.910144
- Title: Parameterized Analysis of Bribery in Challenge the Champ Tournaments
- Title(参考訳): チャンプトーナメントにおけるブライリーのパラメータ解析
- Authors: Juhi Chaudhary, Hendrik Molter, Meirav Zehavi,
- Abstract要約: 本研究では,初期チャンプに対する勝利確率を低くするために,選手を賄うことができる環境について検討する。
ゴールは、他の選手を刺してトーナメントに勝った最初のシャンプの確率を最大にすることであり、贈賄の予算を超えないことである。
プレイヤー数によってパラメータ化される場合、問題はNP-hard と W[1]-hard に弱いことが示される。
- 参考スコア(独自算出の注目度): 8.616793249732263
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Challenge the champ tournaments are one of the simplest forms of competition, where a (initially selected) champ is repeatedly challenged by other players. If a player beats the champ, then that player is considered the new (current) champ. Each player in the competition challenges the current champ once in a fixed order. The champ of the last round is considered the winner of the tournament. We investigate a setting where players can be bribed to lower their winning probability against the initial champ. The goal is to maximize the probability of the initial champ winning the tournament by bribing the other players, while not exceeding a given budget for the bribes. Mattei et al. [Journal of Applied Logic, 2015] showed that the problem can be solved in pseudo-polynomial time, and that it is in XP when parameterized by the number of players. We show that the problem is weakly NP-hard and W[1]-hard when parameterized by the number of players. On the algorithmic side, we show that the problem is fixed-parameter tractable when parameterized either by the number of different bribe values or the number of different probability values. To this end, we establish several results that are of independent interest. In particular, we show that the product knapsack problem is W[1]-hard when parameterized by the number of items in the knapsack, and that constructive bribery for cup tournaments is W[1]-hard when parameterized by the number of players. Furthermore, we present a novel way of designing mixed integer linear programs, ensuring optimal solutions where all variables are integers.
- Abstract(参考訳): チャンプトーナメントへの挑戦は、(最初に選ばれた)シャンプが他のプレイヤーによって繰り返し挑戦される最も単純な競技形態の1つである。
プレイヤーがシャンプを打つと、そのプレイヤーは新しい(現在の)シャンプと見なされる。
競技者の各選手は、現在のシャンパンを1度、一定の順序で挑戦します。
最終ラウンドのシャンプはトーナメントの勝者と見なされている。
本研究では,初期チャンプに対する勝利確率を低くするために,選手を賄うことができる環境について検討する。
ゴールは、他の選手を刺してトーナメントに勝った最初のシャンプの確率を最大にすることであり、贈賄の予算を超えないことである。
Mattei et al [Journal of Applied Logic, 2015] は、問題を擬似ポリノミカル時間で解くことができ、プレイヤー数によってパラメータ化されると XP であることを示した。
プレイヤー数によってパラメータ化される場合、問題はNP-hard と W[1]-hard に弱いことが示される。
アルゴリズム側では、異なる収差値の個数または異なる確率値の個数によってパラメータ化される場合、その問題は固定パラメータ抽出可能であることを示す。
この目的のために、我々は独立した関心を持ついくつかの結果を確立する。
特に、製品knapsack問題は、knapsack内のアイテム数でパラメータ化された場合W[1]-hardであり、また、プレイヤー数でパラメータ化された場合、カップトーナメントの構成的収賄はW[1]-hardであることを示す。
さらに、混合整数線形プログラムを設計し、全ての変数が整数である最適解を確保する新しい方法を提案する。
関連論文リスト
- Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-08-20T13:57:00Z) - Competitions in AI -- Robustly Ranking Solvers Using Statistical
Resampling [9.02080113915613]
比較結果の標準的な解釈から得られたランキングは、評価の基礎として使われるベンチマークインスタンスセットのマイナーな変更にも非常に敏感であることを示す。
本稿では,性能データの再サンプリングに基づく競争結果の統計的に有意な分析手法を提案する。
提案手法は,競合スコアの信頼区間を生成するとともに,有界誤差を持つ統計的に堅牢な解法ランキングを生成する。
論文 参考訳(メタデータ) (2023-08-09T16:47:04Z) - Player-optimal Stable Regret for Bandit Learning in Matching Markets [12.54215178882448]
ここでは、各プレイヤーの最適な安定な後悔は、$O(Klog T/Delta2)$、$K$は腕の数、$T$は地平線、$Delta$は、最初の$N+1$の腕の中でプレイヤーの最小の好みの差であることを示す。
我々の研究は、プレイヤー・ペシミカルの安定したマッチング目標がより弱かったり、特別な仮定を持った市場のみに適用されたりした以前の作品を大幅に改善する。
論文 参考訳(メタデータ) (2023-07-20T14:10:33Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳(メタデータ) (2023-03-22T03:28:12Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳(メタデータ) (2023-01-29T20:42:54Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳(メタデータ) (2023-01-19T11:36:50Z) - Competing Bandits in Time Varying Matching Markets [1.1470070927586014]
両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。
非定常性を扱うための単純な再起動戦略を組み合わせたRCB(Restart Competing Bandits)アルゴリズムを提案する。
提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変動数に対して,$widetildemathcalO(L1/2_TT1/2)$の均一なサブ線形後悔を受けることを示す。
論文 参考訳(メタデータ) (2022-10-21T02:36:57Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳(メタデータ) (2022-03-18T08:03:20Z) - Surface Form Competition: Why the Highest Probability Answer Isn't
Always Right [70.71122438366142]
Domain Conditional Pointwise Mutual Informationは、サーフェスフォームの競争を補償します。
キャリブレーション機能とアンキャリブレーション機能の両方でゼロショット性能の一貫したゲインを実現します。
論文 参考訳(メタデータ) (2021-04-16T18:57:19Z) - Ordinal Monte Carlo Tree Search [0.0]
多くの問題設定、特にゲームプレイでは、エージェントはアクションに対しておそらく遅延した報酬を受け取る。
単純な端末のみの報酬でさえ、勝利が1に等しく、負けが1に等しく、偏見のない文とは見なされない。
本稿では、MDPを解くための一般的なアルゴリズムであるMCTSを調べ、報酬の順序付け処理がこの問題を克服することを示す。
論文 参考訳(メタデータ) (2021-01-26T10:01:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。