論文の概要: Refined Mechanism Design for Approximately Structured Priors via Active
Regression
- arxiv url: http://arxiv.org/abs/2310.07874v1
- Date: Wed, 11 Oct 2023 20:34:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 11:42:40.342346
- Title: Refined Mechanism Design for Approximately Structured Priors via Active
Regression
- Title(参考訳): アクティブ回帰による略構造前駆体の精製機構設計
- Authors: Christos Boutsikas, Petros Drineas, Marios Mertzanidis, Alexandros
Psomas, Paritosh Verma
- Abstract要約: 我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
- 参考スコア(独自算出の注目度): 50.71772232237571
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of a revenue-maximizing seller with a large number of
items $m$ for sale to $n$ strategic bidders, whose valuations are drawn
independently from high-dimensional, unknown prior distributions. It is
well-known that optimal and even approximately-optimal mechanisms for this
setting are notoriously difficult to characterize or compute, and, even when
they can be found, are often rife with various counter-intuitive properties. In
this paper, following a model introduced recently by Cai and
Daskalakis~\cite{cai2022recommender}, we consider the case that bidders' prior
distributions can be well-approximated by a topic model. We design an active
learning component, responsible for interacting with the bidders and outputting
low-dimensional approximations of their types, and a mechanism design
component, responsible for robustifying mechanisms for the low-dimensional
model to work for the approximate types of the former component. On the active
learning front, we cast our problem in the framework of Randomized Linear
Algebra (RLA) for regression problems, allowing us to import several
breakthrough results from that line of research, and adapt them to our setting.
On the mechanism design front, we remove many restrictive assumptions of prior
work on the type of access needed to the underlying distributions and the
associated mechanisms. To the best of our knowledge, our work is the first to
formulate connections between mechanism design, and RLA for active learning of
regression problems, opening the door for further applications of randomized
linear algebra primitives to mechanism design.
- Abstract(参考訳): 価格が高次元の未知の事前分布から独立して引き出される戦略的入札者に対して、多数の商品が$m$で販売される収益を最大化する販売業者の問題を考察する。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで知られており、発見できたとしても、様々な反直観的な性質を持つ。
本稿では,cai と daskalakis~\cite{cai2022recommender} が最近導入したモデルに従い,入札者の事前分布がトピックモデルによってよく近似できる場合を考える。
我々は、入札者と対話し、それらのタイプの低次元近似を出力する能動的学習コンポーネントと、前者の近似型に対応するための低次元モデルのロバスト化機構を担っているメカニズム設計コンポーネントを設計する。
アクティブラーニングの分野では,回帰問題に対するランダム化線形代数学(rla)の枠組みに問題を投げ込み,その研究からいくつかのブレークスルー結果をインポートし,それらを設定に適応させることができた。
機構設計の面では、基礎となる分布と関連する機構に必要とされるアクセスの種類に関する事前作業の制約的な仮定の多くを取り除く。
我々の知る限りでは、我々の研究は機構設計と回帰問題のアクティブな学習のためのrlaの間の接続を初めて定式化し、ランダム化された線形代数プリミティブを機構設計にさらなる応用するための扉を開く。
関連論文リスト
- Deep Learning Meets Mechanism Design: Key Results and Some Novel
Applications [1.2661010067882734]
本稿では、関連する文献から、深層学習を用いたメカニズム設計の技術的詳細について述べる。
本稿では,3つのケーススタディにおいて,このアプローチのパワーを実証する。
論文 参考訳(メタデータ) (2024-01-11T06:09:32Z) - Near-Optimal Fair Resource Allocation for Strategic Agents without
Money: A Data-Driven Approach [20.771751014539532]
本研究では,PFをベンチマークとして,資源分割のためのフェアアロケーション機構の学習に基づく設計について検討する。
本稿では,誤レポートからユーティリティの相対的な利得を測定するメカニズムの「エクスロイタビリティ」の概念を紹介する。
提案するメカニズムであるExPF-Netは,低エクスプロイラビリティを維持しつつ,PF機構に強い近似を与えることを示す。
論文 参考訳(メタデータ) (2023-11-18T01:21:54Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳(メタデータ) (2023-02-02T16:30:33Z) - 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 [130.9259586568977]
本稿では,複数ラウンドの対話を通して動的ビックレー・クラーク・グローブ(VCG)機構を回復するための新しい学習アルゴリズムを提案する。
当社のアプローチの重要な貢献は、報酬のないオンライン強化学習(RL)を取り入れて、リッチな政策分野の探索を支援することである。
論文 参考訳(メタデータ) (2022-02-25T16:17:23Z) - Recommender Systems meet Mechanism Design [29.132299904090868]
提案手法では,入札者の価値分布をトピックモデルで近似できる多項目機構の設計問題を考察する。
このフレームワークの拡張により,話題モデルの表現力を利用して,問題の有効次元を低減できる。
論文 参考訳(メタデータ) (2021-10-25T00:03:30Z) - Learning Revenue-Maximizing Auctions With Differentiable Matching [50.62088223117716]
サンプル評価から,インセンティブに適合し,収益を最大化するオークションを大まかに学習する新しいアーキテクチャを提案する。
我々のアーキテクチャはシンクホーンアルゴリズムを用いて、ネットワークが防御的な収益最大化メカニズムを学習できるように、差別化可能な二部マッチングを実行する。
論文 参考訳(メタデータ) (2021-06-15T04:37:57Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳(メタデータ) (2020-04-19T18:00:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。