論文の概要: Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
- arxiv url: http://arxiv.org/abs/2302.11700v2
- Date: Fri, 30 Jun 2023 18:26:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-04 14:32:51.698207
- Title: Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
- Title(参考訳): 宝くじのメニューと2部関税を最大化する学習収益
- Authors: Maria-Florina Balcan, Hedyeh Beyhaghi
- Abstract要約: 本研究では,経済に顕著な2種類のメカニズム,すなわち宝くじのメニューと2部関税の学習可能性について検討する。
私たちの主な貢献は、宝くじのメニューと、強い後悔に満ちた保証付き関税のための最初のオンライン学習アルゴリズムの提案です。
- 参考スコア(独自算出の注目度): 21.39493074700162
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We advance a recently flourishing line of work at the intersection of
learning theory and computational economics by studying the learnability of two
classes of mechanisms prominent in economics, namely menus of lotteries and
two-part tariffs. The former is a family of randomized mechanisms designed for
selling multiple items, known to achieve revenue beyond deterministic
mechanisms, while the latter is designed for selling multiple units (copies) of
a single item with applications in real-world scenarios such as car or
bike-sharing services. We focus on learning high-revenue mechanisms of this
form from buyer valuation data in both distributional settings, where we have
access to buyers' valuation samples up-front, and the more challenging and
less-studied online settings, where buyers arrive one-at-a-time and no
distributional assumption is made about their values.
Our main contribution is proposing the first online learning algorithms for
menus of lotteries and two-part tariffs with strong regret-bound guarantees. In
the general case, we provide a reduction to a finite number of experts, and in
the limited buyer type case, we show a reduction to online linear optimization,
which allows us to obtain no-regret guarantees by presenting buyers with menus
that correspond to a barycentric spanner. In addition, we provide algorithms
with improved running times over prior work for the distributional settings.
The key difficulty when deriving learning algorithms for these settings is that
the relevant revenue functions have sharp transition boundaries. In stark
contrast with the recent literature on learning such unstructured functions, we
show that simple discretization-based techniques are sufficient for learning in
these settings.
- Abstract(参考訳): 我々は、近年の学習理論と計算経済学の交点において、経済に特有なメカニズムの2つのクラス、すなわち宝くじのメニューと二部関税の学習可能性を研究することによって、繁栄している業績の列を前進させる。
前者は複数の商品を売るために設計されたランダム化されたメカニズムのファミリーであり、後者は自動車や自転車シェアリングサービスのような現実世界のシナリオでアプリケーションを1つのアイテムの複数のユニット(コピー)を売るために設計されている。
我々は,この形態の高頻度なメカニズムを,購入者の評価データから事前に購入者の評価データにアクセスでき,かつ,購入者が1対1で到着し,その価値について分布的な仮定をしない,より困難で調査の少ないオンライン設定の両方で学習することに注力する。
私たちの主な貢献は、宝くじのメニューと2部関税のためのオンライン学習アルゴリズムの提案です。
一般に,有限個の専門家に還元を行い,限定的なバイヤータイプの場合,オンラインリニア最適化の削減を示すとともに,バイヤーにバリセントリックスパンナーに対応するメニューを提示することにより,リニア最適化の不要な保証を得ることができる。
さらに、配電設定の事前作業よりも、実行時間を改善するアルゴリズムも提供します。
これらの設定で学習アルゴリズムを導出する際の重要な困難は、関連する収益関数が急激な遷移境界を持っていることである。
このような非構造化関数の学習に関する最近の文献とは対照的に,これらの学習には単純な離散化に基づく手法が十分であることを示す。
関連論文リスト
- Refined Mechanism Design for Approximately Structured Priors via Active
Regression [50.71772232237571]
我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。
この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
論文 参考訳(メタデータ) (2023-10-11T20:34:17Z) - Machine Learning-powered Combinatorial Clock Auction [14.993021283916006]
我々はイテレーティブオークション(ICA)の設計について研究する。
本稿では,要求クエリに基づいてMLモデルをトレーニングする新しい手法を提案する。
いくつかのスペクトルオークション領域におけるMLベースの需要メカニズムを実験的に評価した。
論文 参考訳(メタデータ) (2023-08-20T10:43:50Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳(メタデータ) (2023-02-02T16:30:33Z) - Faithful Edge Federated Learning: Scalability and Privacy [4.8534377897519105]
フェデレーション学習は、ローカルデータセットの交換を必要とせずに、分散型エッジデバイスのネットワーク上で機械学習アルゴリズムをトレーニングすることを可能にする。
エージェントが自発的に参加するインセンティブに、フェデレーション学習の鍵となる特徴、不均衡データおよび非i.d.データがどのように影響するかを分析する。
経済性,スケーラビリティ,プライバシを満足する2つの忠実な連合学習機構を設計する。
論文 参考訳(メタデータ) (2021-06-30T08:46:40Z) - Learning Revenue-Maximizing Auctions With Differentiable Matching [50.62088223117716]
サンプル評価から,インセンティブに適合し,収益を最大化するオークションを大まかに学習する新しいアーキテクチャを提案する。
我々のアーキテクチャはシンクホーンアルゴリズムを用いて、ネットワークが防御的な収益最大化メカニズムを学習できるように、差別化可能な二部マッチングを実行する。
論文 参考訳(メタデータ) (2021-06-15T04:37:57Z) - Online Learning of Competitive Equilibria in Exchange Economies [94.24357018178867]
経済学では、複数の有理エージェント間の資源不足の共有は古典的な問題である。
エージェントの好みを学習するためのオンライン学習機構を提案する。
数値シミュレーションにより,本機構の有効性を実証する。
論文 参考訳(メタデータ) (2021-06-11T21:32:17Z) - Bid Prediction in Repeated Auctions with Learning [30.07778295477907]
本稿では,メインストリームの検索オークションマーケットプレースからのデータセットを用いて,繰り返しオークションにおける入札予測の問題を検討する。
提案手法は,非regret型エコノメトリを用いて入札予測を行い,ユーティリティ関数に関する非regret学習者としてプレーヤをモデル化する。
この手法は,最先端の時系列機械学習手法に匹敵する性能を示す。
論文 参考訳(メタデータ) (2020-07-26T18:14:05Z) - Certifying Strategyproof Auction Networks [53.37051312298459]
我々は、任意の数のアイテムと参加者でオークションを表現できるRegretNetアーキテクチャに焦点を当てる。
本稿では,ニューラルネットワーク検証文献から得られた手法を用いて,特定の評価プロファイルの下で戦略の安全性を明示的に検証する方法を提案する。
論文 参考訳(メタデータ) (2020-06-15T20:22:48Z) - Generalization Guarantees for Multi-item Profit Maximization: Pricing,
Auctions, and Randomized Mechanisms [86.81403511861788]
購入者の価値に根ざした分布が存在する場合のマルチイテム利益について検討する。
購入者の値の任意のセットに対して、利益はメカニズムのパラメーターにおいて断片的に線形である。
我々は、まだサンプルベースのメカニズム設計文献にはないメカニズムクラスに対する新しい境界を証明した。
論文 参考訳(メタデータ) (2017-04-29T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。