論文の概要: Learning-Based Pricing and Matching for Two-Sided Queues
- arxiv url: http://arxiv.org/abs/2403.11093v2
- Date: Mon, 18 Nov 2024 17:58:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-19 14:26:17.014722
- Title: Learning-Based Pricing and Matching for Two-Sided Queues
- Title（参考訳）: 2段階のキューに対する学習ベース価格とマッチング
- Authors: Zixian Yang, Lei Ying,
- Abstract要約: 複数のタイプの顧客とサーバを持つ動的システムについて検討する。
各キューの到着率は、未知の需要または供給機能に応じて価格によって決定される。
このシステムは、乗客やドライバーとの乗り合い市場のような、両側の市場をモデル化するのに使用することができる。
- 参考スコア（独自算出の注目度）: 14.854050478428727
- License:
- Abstract: We consider a dynamic system with multiple types of customers and servers. Each type of waiting customer or server joins a separate queue, forming a bipartite graph with customer-side queues and server-side queues. The platform can match the servers and customers if their types are compatible. The matched pairs then leave the system. The platform will charge a customer a price according to their type when they arrive and will pay a server a price according to their type. The arrival rate of each queue is determined by the price according to some unknown demand or supply functions. Our goal is to design pricing and matching algorithms to maximize the profit of the platform with unknown demand and supply functions, while keeping queue lengths of both customers and servers below a predetermined threshold. This system can be used to model two-sided markets such as ride-sharing markets with passengers and drivers. The difficulties of the problem include simultaneous learning and decision making, and the tradeoff between maximizing profit and minimizing queue length. We use a longest-queue-first matching algorithm and propose a learning-based pricing algorithm, which combines gradient-free stochastic projected gradient ascent with bisection search. We prove that our proposed algorithm yields a sublinear regret $\tilde{O}(T^{5/6})$ and anytime queue-length bound $\tilde{O}(T^{1/6})$, where $T$ is the time horizon. We further establish a tradeoff between the regret bound and the queue-length bound: $\tilde{O}(T^{1-\gamma})$ versus $\tilde{O}(T^{\gamma})$ for $\gamma \in (0, 1/6].$
- Abstract（参考訳）: 複数のタイプの顧客とサーバを持つ動的システムについて検討する。
待機している顧客またはサーバのそれぞれが別々のキューに参加し、カスタマ側キューとサーバ側キューの2部グラフを形成する。
このプラットフォームは、タイプが互換性がある場合、サーバと顧客にマッチする。
マッチしたペアがシステムを離れる。
プラットフォームは、到着時にタイプに応じて料金を課金し、タイプに応じてサーバに料金を支払う。
各キューの到着率は、未知の需要や供給機能に応じて価格によって決定される。
我々のゴールは、顧客とサーバのキューの長さを所定の閾値以下に保ちながら、要求と供給機能の不明なプラットフォーム利益を最大化するために、価格とマッチングアルゴリズムを設計することである。
このシステムは、乗客やドライバーとの乗り合い市場のような、両側の市場をモデル化するのに使用することができる。
問題の難点は、同時学習と意思決定、利益の最大化と待ち行列の長さの最小化とのトレードオフである。
提案手法は,2項探索と2項探索とを併用した,最長待ち行列マッチングアルゴリズムと学習に基づく価格決定アルゴリズムである。
提案アルゴリズムはサブ線形後悔$\tilde{O}(T^{5/6})$と、任意のキュー長境界$\tilde{O}(T^{1/6})$を出力する。
さらに、後悔境界と待ち行列長境界の間のトレードオフを確立する:$\tilde{O}(T^{1-\gamma})$対$\tilde{O}(T^{\gamma})$ for $\gamma \in (0, 1/6]。
$
関連論文リスト
- Queueing Matching Bandits with Preference Feedback [10.988222071035198]
我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。
各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。
我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
論文 参考訳（メタデータ） (2024-10-14T02:29:06Z) - Online Linear Programming with Batching [18.989352151219336]
オンライン線形プログラミング(OLP)をOmegaで研究する。
後悔によって測定されたように、意思決定を遅らせる能力は、より良い運用パフォーマンスをもたらすことが示されます。
提案されたアルゴリズムはすべて、最初のバッチと最後のバッチにのみ到着する顧客の決定を遅らせる。
論文 参考訳（メタデータ） (2024-08-01T06:13:24Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Timely Asynchronous Hierarchical Federated Learning: Age of Convergence [59.96266198512243]
クライアント-エッジ-クラウドフレームワークを用いた非同期階層型フェデレーション学習環境について検討する。
クライアントはトレーニングされたパラメータをエッジサーバと交換し、ローカルに集約されたモデルを更新する。
各クライアントの目標は、クライアントのタイムラインを維持しながら、グローバルモデルに収束することだ。
論文 参考訳（メタデータ） (2023-06-21T17:39:16Z) - Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
K$キューからなるワンホップ単一サーバキューシステムについて検討する。
我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-03T07:17:09Z) - 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) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-02T15:37:02Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud
System [54.588242387136376]
エッジクラウドシステムのための学習ベースのスケジューリングフレームワークkaisを紹介する。
まず,分散した要求ディスパッチに対応するために,協調型マルチエージェントアクタ-クリティックアルゴリズムを設計する。
次に,多種多様なシステムスケールと構造について,グラフニューラルネットワークを用いてシステム状態情報を埋め込む。
第3に、リクエストディスパッチとサービスオーケストレーションを調和させる2段階のスケジューリングメカニズムを採用します。
論文 参考訳（メタデータ） (2021-01-17T03:45:25Z) - Matched Queues with Matching Batch Pair (m, n) [8.02548118934175]
一致したキューは、新しい双方向レベル依存準生死プロセスとして表現できることを示す。
本稿では,システム安定性,待ち行列の平均時間,A-顧客,B-顧客の平均所要時間など,この待ち行列の詳細な分析を行う。
論文 参考訳（メタデータ） (2020-09-06T14:14:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。