論文の概要: VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback

• arxiv url: http://arxiv.org/abs/2004.08924v4
• Date: Sun, 23 Jan 2022 20:46:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-11 23:54:53.691857
• Title: VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback
• Title（参考訳）: 確率帯域フィードバックによる未知エージェント値を用いたVCG機構の設計
• Authors: Kirthevasan Kandasamy and Joseph E. Gonzalez and Michael I. Jordan and Ion Stoica
• Abstract要約: 本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
• 参考スコア（独自算出の注目度）: 104.06766271716774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. On each round, a mechanism first assigns an allocation each to a set of agents and charges them a price; at the end of the round, the agents provide (stochastic) feedback to the mechanism for the allocation they received. This setting is motivated by applications in cloud markets and online advertising where an agent may know her value for an allocation only after experiencing it. Therefore, the mechanism needs to explore different allocations for each agent so that it can learn their values, while simultaneously attempting to find the socially optimal set of allocations. Our focus is on truthful and individually rational mechanisms which imitate the classical VCG mechanism in the long run. To that end, we first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. We show that these three terms are interdependent via an $\Omega(T^{\frac{2}{3}})$ lower bound for the maximum of these three terms after $T$ rounds of allocations, and describe an algorithm which essentially achieves this rate. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets. Next, we define asymptotic variants for the truthfulness and individual rationality requirements and provide asymptotic rates to quantify the degree to which both properties are satisfied by the proposed algorithm.
• Abstract（参考訳）: 本研究では,エージェントが自分の価値を知らない場合の福祉最大化メカニズム設計問題について検討する。 各ラウンドにおいて、メカニズムはまず各エージェントにアロケーションを割り当て、それらを価格で課金する; ラウンドの最後に、エージェントは、受け取ったアロケーションのメカニズムに対して(統計的)フィードバックを提供する。 この設定は、クラウドマーケットやオンライン広告のアプリケーションによって動機付けられており、エージェントがアロケーションの価値を体験した後にのみ知ることができる。 したがって、メカニズムはそれぞれのエージェントに対して異なる割り当てを探索し、その価値を学習し、同時に社会的に最適な割り当ての集合を見つけようとする必要がある。 私たちの焦点は、長期的には古典的なVCGメカニズムを模倣する真理と個々に合理的なメカニズムにあります。 そこで,我々はまず,福祉に対する後悔,各エージェントの個人的効用,メカニズムの3つの概念を定義した。 これらの3つの項は、$t$ラウンドの後にこれら3つの項の最大値に対して$\omega(t^{\frac{2}{3}})$下界を介して相互依存であることを示し、本質的にこの速度を達成するアルゴリズムを記述する。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。 次に、真理性および個々の合理性要件に対する漸近的変種を定義し、提案アルゴリズムによって両方の特性が満たされる程度を定量化する漸近的速度を与える。

関連論文リスト

• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。 この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
  論文  参考訳（メタデータ） (2023-10-11T20:34:17Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  競売人の収益を最大化しつつ、競売人の過去の後悔を最小限にする競売メカニズムは、経済学において重要であるが複雑な問題である。 ニューラルネットワークによる最適なオークションメカニズムの学習を通じて、注目すべき進歩が達成されている。
  論文  参考訳（メタデータ） (2022-10-11T16:13:25Z)
• Online Allocation and Learning in the Presence of Strategic Agents [16.124755488878044]
  我々は,各エージェントが予め指定された各項目の分数を受けなければならないという制約の下で,$n$均質なエージェントのうち,$T$が順次到着するアイテムを割り当てる問題について検討する。 私たちの主な貢献は、ほぼベイズ的インセンティブ互換のオンライン学習ベースのアロケーションメカニズムです。
  論文  参考訳（メタデータ） (2022-09-25T00:46:53Z)
• Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning [114.36124979578896]
  オフライン強化学習アルゴリズムを用いて動的メカニズムを設計する。 我々のアルゴリズムは悲観主義の原理に基づいており、オフラインデータセットのカバレッジについて軽度な仮定しか必要としない。
  論文  参考訳（メタデータ） (2022-05-05T05:44:26Z)
• Online Learning of Competitive Equilibria in Exchange Economies [94.24357018178867]
  経済学では、複数の有理エージェント間の資源不足の共有は古典的な問題である。 エージェントの好みを学習するためのオンライン学習機構を提案する。 数値シミュレーションにより,本機構の有効性を実証する。
  論文  参考訳（メタデータ） (2021-06-11T21:32:17Z)
• Consequences of Misaligned AI [12.879600368339393]
  本稿では,報酬関数の設計をインタラクティブでダイナミックなプロセスとみなすべきである。 セットアップを変更して、完全な状態を参照したり、プリンシパルがプロキシの目的を時間とともに更新したりすることで、より高いユーティリティソリューションを実現する方法を示します。
  論文  参考訳（メタデータ） (2021-02-07T19:34:04Z)
• Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach [8.932080210400535]
  我々は、レポートのペアをスコアにマッピングするスコア関数を持つメカニズムのファミリーを設計する。 異なる種類の先行作業に必要なタスク数に対して、適切な境界を導出する方法を示す。 これはマルチタスク設定用に設計された連続信号に対する最初のピア予測機構である。
  論文  参考訳（メタデータ） (2020-09-30T15:09:56Z)

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

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