論文の概要: Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
- arxiv url: http://arxiv.org/abs/2402.08547v1
- Date: Tue, 13 Feb 2024 15:53:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 14:54:01.266180
- Title: Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
- Title（参考訳）: デッサートを乗り越えて、繰り返しケーキをカットする技術を習得する
- Authors: Simina Br\^anzei and MohammadTaghi Hajiaghayi and Reed Phillips and
Suho Shin and Kun Wang
- Abstract要約: 我々は,アリスとボブという2人の選手の間で,ケーキ上での個人的評価の相違を繰り返す公平な分割の設定について検討する。
我々は2つのバージョンを考える: シーケンシャル: ボブがアリスのカットポイントを左と右を選ぶ前に観察し、同時に、ボブが選択した後のみ彼女のカットポイントを観察する。
- 参考スコア（独自算出の注目度）: 10.50673995077851
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the setting of repeated fair division between two players,
denoted Alice and Bob, with private valuations over a cake. In each round, a
new cake arrives, which is identical to the ones in previous rounds. Alice cuts
the cake at a point of her choice, while Bob chooses the left piece or the
right piece, leaving the remainder for Alice. We consider two versions:
sequential, where Bob observes Alice's cut point before choosing left/right,
and simultaneous, where he only observes her cut point after making his choice.
The simultaneous version was first considered by Aumann and Maschler (1995).
We observe that if Bob is almost myopic and chooses his favorite piece too
often, then he can be systematically exploited by Alice through a strategy akin
to a binary search. This strategy allows Alice to approximate Bob's preferences
with increasing precision, thereby securing a disproportionate share of the
resource over time.
We analyze the limits of how much a player can exploit the other one and show
that fair utility profiles are in fact achievable. Specifically, the players
can enforce the equitable utility profile of $(1/2, 1/2)$ in the limit on every
trajectory of play, by keeping the other player's utility to approximately
$1/2$ on average while guaranteeing they themselves get at least approximately
$1/2$ on average. We show this theorem using a connection with Blackwell
approachability.
Finally, we analyze a natural dynamic known as fictitious play, where players
best respond to the empirical distribution of the other player. We show that
fictitious play converges to the equitable utility profile of $(1/2, 1/2)$ at a
rate of $O(1/\sqrt{T})$.
- Abstract（参考訳）: 我々は、アリスとボブという2人のプレイヤーがケーキよりもプライベートなバリュエーションで繰り返し公平に分割することを考える。
各ラウンドに新しいケーキが登場し、前ラウンドと同じである。
アリスは自分の選択した時点でケーキを切るが、ボブは左のピースか右のピースを選び、残りはアリスに任せる。
我々は2つのバージョンを考える: シーケンシャル: ボブがアリスのカットポイントを左と右を選ぶ前に観察し、同時に、ボブが選択した後のみ彼女のカットポイントを観察する。
同時版は Aumann and Maschler (1995) によって最初に検討された。
ボブがほとんど近視的であり、彼の好きな曲をあまり頻繁に選ぶなら、二分探索に似た戦略を通じてアリスによって体系的に悪用されるのである。
この戦略により、アリスはボブの好みを精度を上げることで近似し、時間とともに資源の不均等な共有を確保することができる。
プレイヤーが他のプレイヤーをどの程度利用できるかの限界を分析し、公正なユーティリティプロファイルが実際に達成可能であることを示す。
特に、プレイヤーは、他のプレイヤーの効用を平均で約1/2$に保ちながら、平均で約1/2$の保証をすることで、プレーの軌跡ごとに、同等の効用プロファイルに$(1/2, 1/2)$を課すことができる。
この定理はブラックウェルのアプローチ可能性との接続を用いて示される。
最後に、プレイヤーが他のプレイヤーの経験的分布に最も反応する架空の遊びとして知られる自然力学を分析する。
虚数プレイは、$(1/2, 1/2)$の公平なユーティリティプロファイルに$O(1/\sqrt{T})$の速度で収束することを示す。
関連論文リスト
- Optimal Strategies for Winning Certain Coset-Guessing Quantum Games [8.03451158784716]
最近発表されたコセット推測ゲームでは、アリスがボブとチャーリーと対戦し、共同勝利を狙った。
ボブとチャーリーの予想が同時に正しい確率は、m が増加するにつれて指数関数的にゼロとなることを示す。
CNOT と Hadamard ゲートのみを用いた符号化回路を考案した。
論文 参考訳（メタデータ） (2024-10-10T17:42:30Z) - Quantum advantage in a unified scenario and secure detection of
resources [55.2480439325792]
我々は、量子優位性を持つ異なるアプローチを研究するために単一のタスクを考える。
我々は、キュービット通信の全体プロセスにおける最適成功確率が、cbit通信のそれよりも高いことを示す。
論文 参考訳（メタデータ） (2023-09-22T23:06:20Z) - Offline Reinforcement Learning for Human-Guided Human-Machine
Interaction with Private Information [110.42866062614912]
個人情報を含む人間と機械の相互作用について検討する。
本ゲームでは,オフライン強化学習(RL)に注目した。
そこで我々は,新たな識別結果を開発し,それを用いて新たな非政治評価手法を提案する。
論文 参考訳（メタデータ） (2022-12-23T06:26:44Z) - Identifying the value of a random variable unambiguously: Quantum versus classical approaches [44.99833362998488]
量子リソースは、古典的なリソースよりも有利である。
我々は、Refereeが仲介し、AliceとBobの間でプレイするゲームに基づいてそのようなタスクを構築する。
アリスが古典的情報を限られた量送った場合、ゲームに勝つには「古典的情報の限られた量」の量子アナログが十分であるのに対し、ゲームは勝てないことを示す。
論文 参考訳（メタデータ） (2022-11-16T20:28:49Z) - Two quantum algorithms for communication between spacelike separated
locations [0.7614628596146599]
我々は、アシラ量子ビットを用いた高次元ヒルベルト空間における状態判別によって超光通信が可能であると論じる。
本稿では,AliceとBobの2人の観測者間の通信のための状態判別による2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-16T06:54:22Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Experimental test of Tsirelson's bound with a single photonic qubit [8.8709589922781]
Clauser-Horne-Shimony-Holt ゲームでは、Alice と Bob はそれぞれ古典的なビット $a$ と $b$ を割り当てられる。
ゲームでは、プレイヤーが古典的な戦略を使用する場合、最適な成功確率は$w(textCHSH)=0.75$である。
ポープスクとローリッヒは、完全成功確率1ドルは、符号なしの仮定に違反することなくより一般的な理論でも達成できると述べた。
論文 参考訳（メタデータ） (2022-01-25T09:06:53Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳（メタデータ） (2021-02-15T09:09:16Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-21T17:51:57Z) - Arbitrarily many independent observers can share the nonlocality of a
single maximally entangled qubit pair [4.061135251278187]
任意に多くの独立系Bobが単一Aliceに対してCHSH違反を期待できることを示す。
我々の研究は、デバイス非依存のランダム性が1組の量子ビットからどれだけ堅牢に生成できるかという制約を最終的に理解するための一歩である。
論文 参考訳（メタデータ） (2020-03-26T18:38:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。