論文の概要: Online 2-stage Stable Matching
- arxiv url: http://arxiv.org/abs/2207.02057v2
- Date: Tue, 2 May 2023 12:26:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 18:02:22.385369
- Title: Online 2-stage Stable Matching
- Title（参考訳）: オンライン2段階安定マッチング
- Authors: Evripidis Bampis and Bruno Escoffier and Paul Youssef
- Abstract要約: 学生が大学に配属されるシステムを考える。
この問題を解決するための最適オンラインアルゴリズムが存在することを示す。
- 参考スコア（独自算出の注目度）: 3.124583817964757
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We focus on an online 2-stage problem, motivated by the following situation:
consider a system where students shall be assigned to universities. There is a
first round where some students apply, and a first (stable) matching $M_1$ has
to be computed. However, some students may decide to leave the system (change
their plan, go to a foreign university, or to some institution not in the
system). Then, in a second round (after these deletions), we shall compute a
second (final) stable matching $M_2$. As it is undesirable to change
assignments, the goal is to minimize the number of divorces/modifications
between the two stable matchings $M_1$ and $M_2$. Then, how should we choose
$M_1$ and $M_2$? We show that there is an {\it optimal online} algorithm to
solve this problem. In particular, thanks to a dominance property, we show that
we can optimally compute $M_1$ without knowing the students that will leave the
system. We generalize the result to some other possible modifications in the
input (students, open positions).
We also tackle the case of more stages, showing that no competitive (online)
algorithm can be achieved for the considered problem as soon as there are 3
stages.
- Abstract（参考訳）: 学生が大学に配属されるシステムを考える。
学生が応募する第1ラウンドがあり、$m_1$に対応する第1ラウンド(stable)を計算しなければならない。
しかし、一部の学生は制度を離れることを決意することがある(計画を変更したり、外国の大学に行ったり、制度にない機関へ行ったり)。
そして、(これらの削除の後)第2ラウンドで、2番目の(最終的な)安定な$M_2$を計算する。
割り当ての変更は望ましくないため、目標は2つの安定マッチングである$m_1$と$m_2$の間の離婚/修正の数を最小化することである。
すると、$M_1$と$M_2$をどうやって選ぶべきか?
この問題を解くための "it optimal online} アルゴリズムが存在することを示す。
特に、支配性のおかげで、システムを離れる学生を知らずに、最適に$m_1$を計算できることが示される。
結果は、入力(学生、オープンポジション)の他の可能な変更に一般化する。
また、さらに多くの段階についても取り組み、3つの段階が存在するとすぐに考慮された問題に対して競合的(オンライン)アルゴリズムが実現できないことを示した。
関連論文リスト
- Online Matrix Completion: A Collaborative Approach with Hott Items [19.781869063637387]
M$ユーザ,$N$アイテム,$T$ラウンド,未知のランク-$r$報酬行列$Rin mathbbRMtimes N$のオンライン設定における下位行列補完問題について検討する。
論文 参考訳（メタデータ） (2024-08-11T18:49:52Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - UniRank: Unimodal Bandit Algorithm for Online Ranking [0.0]
We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。
いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
論文 参考訳（メタデータ） (2022-08-02T15:01:33Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Online Learning with Vector Costs and Bandits with Knapsacks [8.340947016086739]
オンライン学習にベクターコスト(OLVCp)を導入し、各時間に1,ldots,T$の$tのステップで、未知のベクターコストを発生させるアクションを実行する必要がある。
オンラインアルゴリズムの目標は、コストベクトルの和の$ell_p$ノルムを最小化することである。
論文 参考訳（メタデータ） (2020-10-14T18:28:41Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。