論文の概要: Reachability Poorman Discrete-Bidding Games
- arxiv url: http://arxiv.org/abs/2307.15218v1
- Date: Thu, 27 Jul 2023 22:30:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-31 14:11:32.259746
- Title: Reachability Poorman Discrete-Bidding Games
- Title（参考訳）: reachability poorman discrete-bidding games(英語)
- Authors: Guy Avni, Tobias Meggendorfer, Suman Sadhukhan, Josef Tkadlec and
{\DJ}or{\dj}e \v{Z}ikeli\'c
- Abstract要約: 2人のプレイヤーによるゼロサムエムグラフゲームのクラスであるエム入札ゲームについて検討する。
本研究では,連続バイディング条件下でのしきい値の誤差境界でしきい値の予算を近似できることを示す。
しきい値の予算を求めるアルゴリズムを実装し実験する。
- 参考スコア（独自算出の注目度）: 3.009888538361211
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider {\em bidding games}, a class of two-player zero-sum {\em graph
games}. The game proceeds as follows. Both players have bounded budgets. A
token is placed on a vertex of a graph, in each turn the players simultaneously
submit bids, and the higher bidder moves the token, where we break bidding ties
in favor of Player 1. Player 1 wins the game iff the token visits a designated
target vertex. We consider, for the first time, {\em poorman discrete-bidding}
in which the granularity of the bids is restricted and the higher bid is paid
to the bank. Previous work either did not impose granularity restrictions or
considered {\em Richman} bidding (bids are paid to the opponent). While the
latter mechanisms are technically more accessible, the former is more appealing
from a practical standpoint. Our study focuses on {\em threshold budgets},
which is the necessary and sufficient initial budget required for Player 1 to
ensure winning against a given Player 2 budget. We first show existence of
thresholds. In DAGs, we show that threshold budgets can be approximated with
error bounds by thresholds under continuous-bidding and that they exhibit a
periodic behavior. We identify closed-form solutions in special cases. We
implement and experiment with an algorithm to find threshold budgets.
- Abstract（参考訳）: 2人のプレイヤーのゼロサム・グラフゲームのクラスである「em bidding games」を考える。
ゲームは以下の通り進行する。
両選手とも予算制限がある。
トークンはグラフの頂点に配置され、各ターンでプレイヤーが同時に入札を行い、上位の入札者がトークンを移動させ、そこでプレイヤー1に有利な入札関係を打ち破る。
プレイヤー1がゲームに勝利し、トークンが指定されたターゲット頂点を訪問する。
我々は、入札の粒度が制限され、より高い入札が銀行に支払われる、初めて、貧しい人による離散入札を考える。
以前の仕事は、粒度制限を課さないか、あるいは「em richman」入札を検討するかのどちらかであった(bidは相手に対して支払われる)。
後者のメカニズムは技術的にはよりアクセスしやすいが、前者は実用的な観点からより魅力的である。
本研究は,プレーヤ1が所定のプレーヤ2の予算に勝つために必要な,必要かつ十分な初期予算である,しきい値予算に焦点をあてる。
まず閾値の存在を示します。
DAGでは、しきい値の予算を連続バイディング下でのしきい値による誤差境界に近似し、周期的な振舞いを示す。
特殊ケースで閉形式解を同定する。
我々は,しきい値予算を求めるアルゴリズムを実装し,実験する。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Honor Among Bandits: No-Regret Learning for Online Fair Division [20.38824614301761]
本研究では, 商品の種類が有限であり, プレイヤーの値が未知の方法で分布から引き出される場合, プレイヤーに対する不特定商品のオンライン公平分割の問題点を考察する。
我々の主な成果は、公正な制約を維持しながら、$tildeO(T2/3)の後悔を達成できる探索列コミットアルゴリズムの設計である。
論文 参考訳（メタデータ） (2024-07-01T20:44:52Z) - State-Constrained Zero-Sum Differential Games with One-Sided Information [19.964883571758502]
状態制約と一方的な情報を持つゼロサム差分ゲームについて検討する。
我々の貢献は、状態制約のあるゲームの拡張であり、行動戦略の計算に必要な原始的および双対的準力学原理の導出である。
論文 参考訳（メタデータ） (2024-03-05T07:51:38Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - Learning and Collusion in Multi-unit Auctions [17.727436775513368]
均一な価格で複数ユニットのオークションを繰り返し検討する。
このオークションの特性をオフラインとオンラインの両方で分析する。
ここでは、$(K+1)$-stの価格形式が入札者間の共謀の影響を受けやすいことを示す。
論文 参考訳（メタデータ） (2023-05-27T08:00:49Z) - Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
with Bandit Feedback [49.1061436241109]
非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。
我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
論文 参考訳（メタデータ） (2023-03-05T18:08:54Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。
対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。
我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
論文 参考訳（メタデータ） (2021-07-05T07:48:52Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。