論文の概要: Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Sequential Auctions under Unknown Environments

• arxiv url: http://arxiv.org/abs/2506.19038v1
• Date: Mon, 23 Jun 2025 18:52:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-25 19:48:23.348689
• Title: Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Sequential Auctions under Unknown Environments
• Title（参考訳）: 未知環境下でのシークエンシャルオークションにおける動的ビックリー・クラーク・グラブのオンライン学習
• Authors: Vincent Leon, S. Rasoul Etesami,
• Abstract要約: 本研究では,未知環境におけるシーケンシャルオークションにおけるオンライン動的メカニズム設計の問題点を考察する。 我々は,販売者が基礎となるMDPモデルを学習するためのオンライン強化学習アルゴリズムを開発した。 学習したオンラインメカニズムは, 任意の確率で効率, 真理性, 合理性を実現し, 様々な後悔の概念で性能を保証できることを示す。
• 参考スコア（独自算出の注目度）: 0.9208007322096533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of online dynamic mechanism design for sequential auctions in unknown environments, where the underlying market and, thus, the bidders' values vary over time as interactions between the seller and the bidders progress. We model the sequential auctions as an infinite-horizon average-reward Markov decision process (MDP), where the transition kernel and reward functions are unknown to the seller. In each round, the seller determines an allocation and a payment for each bidder. Each bidder receives a private reward and submits a sealed bid to the seller. The state, which represents the underlying market, evolves according to an unknown transition kernel and the seller's allocation policy. Unlike existing works that formulate the problem as a multi-armed bandit model or as an episodic MDP, where the environment resets to an initial state after each round or episode, our paper considers a more realistic and sophisticated setting in which the market continues to evolve without restarting. We first extend the Vickrey-Clarke-Groves (VCG) mechanism, which is known to be efficient, truthful, and individually rational for one-shot static auctions, to sequential auctions, thereby obtaining a dynamic VCG mechanism counterpart that preserves these desired properties. We then focus on the online setting and develop an online reinforcement learning algorithm for the seller to learn the underlying MDP model and implement a mechanism that closely resembles the dynamic VCG mechanism. We show that the learned online mechanism asymptotically converges to a dynamic mechanism that approximately satisfies efficiency, truthfulness, and individual rationality with arbitrarily high probability and achieves guaranteed performance in terms of various notions of regret.
• Abstract（参考訳）: 本研究では,販売者と入札者の相互作用が進行するにつれて,市場と入札者の価値が時間とともに変化する未知の環境での連続オークションにおけるオンライン動的メカニズム設計の問題点を考察する。 逐次オークションを,遷移カーネルと報酬関数が販売者に未知な無限水平平均回帰マルコフ決定プロセス(MDP)としてモデル化する。 各ラウンドにおいて、売り手は各入札者に対する割り当てと支払いを決定する。 各入札者は個人報酬を受け取り、販売者に封印された入札を提出する。 根底にある市場を表す状態は、未知の遷移カーネルと売り手の割り当てポリシーに従って進化する。 マルチアームバンディットモデルやエピソード毎に環境が初期状態にリセットされるエピソディックMDPとしてこの問題を定式化している既存の作業とは異なり,本論文では,市場が再起動することなく進化し続ける,より現実的で洗練された環境について検討する。 まず,1ショットの静的オークションにおいて効率,真理,個々に合理的であることが知られているVickrey-Clarke-Groves(VCG)機構を逐次オークションに拡張し,これらの特性を保存する動的VCG機構を得る。 次に、オンライン設定に集中し、販売者が基礎となるMDPモデルを学習し、動的VCGメカニズムによく似たメカニズムを実装するためのオンライン強化学習アルゴリズムを開発する。 学習したオンラインメカニズムは, 効率, 真理性, 個人合理性にほぼ満足する動的なメカニズムに漸近的に収束し, 様々な後悔の概念で保証された性能を達成することを示す。

関連論文リスト

• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。 この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
  論文  参考訳（メタデータ） (2023-10-11T20:34:17Z)
• Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning [114.36124979578896]
  オフライン強化学習アルゴリズムを用いて動的メカニズムを設計する。 我々のアルゴリズムは悲観主義の原理に基づいており、オフラインデータセットのカバレッジについて軽度な仮定しか必要としない。
  論文  参考訳（メタデータ） (2022-05-05T05:44:26Z)
• Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach [123.55983746427572]
  本稿では,複数ラウンドの対話を通して動的ビックレー・クラーク・グローブ(VCG)機構を回復するための新しい学習アルゴリズムを提案する。 当社のアプローチの重要な貢献は、報酬のないオンライン強化学習(RL)を取り入れて、リッチな政策分野の探索を支援することである。
  論文  参考訳（メタデータ） (2022-02-25T16:17:23Z)
• Optimizing Multiple Performance Metrics with Deep GSP Auctions for E-commerce Advertising [28.343122250701498]
  eコマース広告では、広告プラットフォームは通常、ユーザーエクスペリエンス、広告主ユーティリティ、プラットフォーム収益など、さまざまなパフォーマンス指標を最適化するためのオークションメカニズムに依存している。 本稿では,Deep GSPオークション(Deep GSP auction)と呼ばれる新しいメカニズムを提案する。
  論文  参考訳（メタデータ） (2020-12-05T02:51:11Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。