論文の概要: Double Matching Under Complementary Preferences
- arxiv url: http://arxiv.org/abs/2301.10230v1
- Date: Tue, 24 Jan 2023 18:54:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 12:41:17.227512
- Title: Double Matching Under Complementary Preferences
- Title(参考訳): 相補的選好下での二重マッチング
- Authors: Yuantong Li, Guang Cheng, Xiaowu Dai
- Abstract要約: 本稿では,市場を補完的な選好でマッチングする問題に対処する新しいアルゴリズムを提案する。
相補的な選好の存在は、マッチングプロセスにおける不安定をもたらす可能性がある。
このアルゴリズムは、トンプソンサンプリングの強度を二重マッチング手法と組み合わせて、安定したマッチング結果を得る。
- 参考スコア(独自算出の注目度): 18.03464967426957
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a new algorithm for addressing the problem of
matching markets with complementary preferences, where agents' preferences are
unknown a priori and must be learned from data. The presence of complementary
preferences can lead to instability in the matching process, making this
problem challenging to solve. To overcome this challenge, we formulate the
problem as a bandit learning framework and propose the Multi-agent Multi-type
Thompson Sampling (MMTS) algorithm. The algorithm combines the strengths of
Thompson Sampling for exploration with a double matching technique to achieve a
stable matching outcome. Our theoretical analysis demonstrates the
effectiveness of MMTS as it is able to achieve stability at every matching
step, satisfies the incentive-compatibility property, and has a sublinear
Bayesian regret over time. Our approach provides a useful method for addressing
complementary preferences in real-world scenarios.
- Abstract(参考訳): 本稿では,エージェントの嗜好が未知であり,データから学ばなければならない市場と相補的な選好とのマッチング問題に対処する新しいアルゴリズムを提案する。
相補的な選好が存在するとマッチングプロセスが不安定になり、この問題を解くのが難しくなる。
この課題を克服するために、バンドレート学習フレームワークとして問題を定式化し、マルチエージェントマルチタイプトンプソンサンプリング(MMTS)アルゴリズムを提案する。
このアルゴリズムは、トンプソンサンプリングの強度を二重マッチング手法と組み合わせ、安定したマッチング結果を得る。
理論的解析により,MMTS の有効性が示され,各段階の安定が達成され,インセンティブ・コンパチビリティ特性を満足し,時間とともにサブリニアなベイズ的後悔が生じる。
本手法は,現実シナリオにおける補完的嗜好に対処するための有用な手法を提供する。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Stability-penalty-adaptive follow-the-regularized-leader: Sparsity,
game-dependency, and best-of-both-worlds [46.30750729936261]
FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。
我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
論文 参考訳(メタデータ) (2023-05-26T23:20:48Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳(メタデータ) (2022-11-29T05:52:17Z) - Advertising Media and Target Audience Optimization via High-dimensional
Bandits [2.5137859989323537]
我々は、広告主がオンラインパブリッシャーのデジタル広告管理を自動化するために利用できるデータ駆動アルゴリズムを提案する。
このアルゴリズムにより、広告主は利用可能なターゲットオーディエンスと広告メディアをまたいで検索し、オンライン実験を通じてキャンペーンの最良の組み合わせを見つけることができる。
論文 参考訳(メタデータ) (2022-09-17T21:00:53Z) - Thompson Sampling with Virtual Helping Agents [0.0]
我々は、オンラインのシーケンシャルな意思決定の問題、すなわち、現在の知識を活用して即時パフォーマンスを最大化し、新しい情報を探索して長期的な利益を得るというトレードオフに対処する。
本稿では,マルチアームバンディット問題に対する2つのアルゴリズムを提案し,累積的後悔に関する理論的境界を提供する。
論文 参考訳(メタデータ) (2022-09-16T23:34:44Z) - Learn to Match with No Regret: Reinforcement Learning in Markov Matching
Markets [151.03738099494765]
我々は、市場の両側でプランナーと戦略エージェントのセットを含むマルコフマッチング市場について検討する。
本稿では,楽観的な値反復と最大重みマッチングを組み合わせた強化学習フレームワークを提案する。
我々は,アルゴリズムがサブ線形後悔を実現することを証明した。
論文 参考訳(メタデータ) (2022-03-07T19:51:25Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Doubly-Adaptive Thompson Sampling for Multi-Armed and Contextual Bandits [28.504921333436833]
本稿では,トンプソンサンプリングに基づくアルゴリズムの変種について,両腕の真の平均報酬に対する2倍頑健な推定器の項を適応的に再検討する。
提案アルゴリズムは, 半合成実験における最適(最小)後悔率とその経験的評価に適合する。
このアプローチは、適応データ収集とは別に、より多くのバイアス源が存在するコンテキスト的包帯に拡張する。
論文 参考訳(メタデータ) (2021-02-25T22:29:25Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。