論文の概要: Learning Utilities and Equilibria in Non-Truthful Auctions

• arxiv url: http://arxiv.org/abs/2007.01722v3
• Date: Mon, 31 Oct 2022 18:04:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-14 06:18:02.614209
• Title: Learning Utilities and Equilibria in Non-Truthful Auctions
• Title（参考訳）: 非真面目オークションにおける学習ユーティリティと平衡
• Authors: Hu Fu, Tao Lin
• Abstract要約: 我々は、$tilde O(n / epsilon2)$サンプルと$n$エージェントが、全ての入札戦略の中間ユーティリティを学習するのに十分であることを示す。 また、エージェントが自分のタイプを見つけるために検索コストを支払わなければならない設定も検討する。
• 参考スコア（独自算出の注目度）: 11.682943354386868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In non-truthful auctions, agents' utility for a strategy depends on the strategies of the opponents and also the prior distribution over their private types; the set of Bayes Nash equilibria generally has an intricate dependence on the prior. Using the First Price Auction as our main demonstrating example, we show that $\tilde O(n / \epsilon^2)$ samples from the prior with $n$ agents suffice for an algorithm to learn the interim utilities for all monotone bidding strategies. As a consequence, this number of samples suffice for learning all approximate equilibria. We give almost matching (up to polylog factors) lower bound on the sample complexity for learning utilities. We also consider a setting where agents must pay a search cost to discover their own types. Drawing on a connection between this setting and the first price auction, discovered recently by Kleinberg et al. (2016), we show that $\tilde O(n / \epsilon^2)$ samples suffice for utilities and equilibria to be estimated in a near welfare-optimal descending auction in this setting. En route, we improve the sample complexity bound, recently obtained by Guo et al. (2021), for the Pandora's Box problem, which is a classical model for sequential consumer search.
• Abstract（参考訳）: 非真面目なオークションでは、戦略のためのエージェントの効用は、敵の戦略にも依存し、また彼らのプライベートタイプに対する事前分布にも依存する。 First Price Auction を主な実演例として用いて、$\tilde O(n / \epsilon^2)$サンプルと$n$エージェントが、すべての単調入札戦略の中間ユーティリティを学習するのに十分であることを示す。 その結果、このサンプル数は近似平衡をすべて学習するのに十分である。 ほぼマッチング(ポリログ因子まで)を、学習ユーティリティのサンプル複雑性に縛り付ける。 また,エージェントが検索コストを支払わなければならないような設定も検討している。 Kleinberg et al. (2016) が最近発見した, この設定と最初の価格オークションの関連性に基づいて, この設定において, 有効性および均衡性について$\tilde O(n / \epsilon^2)$サンプルが, この設定において, 最近の福祉最適下降オークションで推定されることを示す。 また,最近Guo et al. (2021) が入手した Pandora の Box 問題 (コンシューマーサーチの古典的モデル) に対して,サンプルの複雑性境界を改善した。

関連論文リスト

• Online Combinatorial Allocations and Auctions with Few Samples [9.675397292814122]
  本稿では,O(1)競合アルゴリズムの実現可能性について,基礎となる入札者分布から限られた数のサンプルにしかアクセスできないという現実的な制約の下で検討する。 最初の主な貢献は, サブモジュール/XOS評価のためのO(1)競合アルゴリズムを得るのに, 各入札者分布からのサンプルだけで十分であることを示している。
  論文  参考訳（メタデータ） (2024-09-17T11:43:55Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Improved classical shadows from local symmetries in the Schur basis [4.462208715451194]
  従来のシャドウタスクのサンプル複雑性について検討する。 サンプルの複雑さが未知の状態のランクとともにスケールする古典的影に対する最初の共同測定プロトコルを提案する。
  論文  参考訳（メタデータ） (2024-05-15T17:33:10Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
  論文  参考訳（メタデータ） (2021-07-05T07:48:52Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
  論文  参考訳（メタデータ） (2020-07-13T15:17:35Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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