論文の概要: A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search
- arxiv url: http://arxiv.org/abs/2603.08679v1
- Date: Mon, 09 Mar 2026 17:49:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-10 15:13:16.685101
- Title: A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search
- Title（参考訳）: AI誘導進化探索による二国間貿易におけるランダムオファー機構の新しい下界
- Authors: Yang Cai, Vineet Gupta, Zun Li, Aranyak Mehta,
- Abstract要約: 二国間貿易では、メカニズムは同時に効率よく、ベイズ的インセンティブ互換(BIC)、予算均衡(BB)は不可能である。
この研究は、AI誘導の進化的検索フレームワークであるAlphaEvolveを使用して、価値分布の空間を探索する。
- 参考スコア（独自算出の注目度）: 8.960486358735311
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The celebrated Myerson--Satterthwaite theorem shows that in bilateral trade, no mechanism can be simultaneously fully efficient, Bayesian incentive compatible (BIC), and budget balanced (BB). This naturally raises the question of how closely the gains from trade (GFT) achievable by a BIC and BB mechanism can approximate the first-best (fully efficient) benchmark. The optimal BIC and BB mechanism is typically complex and highly distribution-dependent, making it difficult to characterize directly. Consequently, much of the literature analyzes simpler mechanisms such as the Random-Offerer (RO) mechanism and establishes constant-factor guarantees relative to the first-best GFT. An important open question concerns the worst-case performance of the RO mechanism relative to first-best (FB) efficiency. While it was originally hypothesized that the approximation ratio $\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}}$ is bounded by $2$, recent work provided counterexamples to this conjecture: Cai et al. proved that the ratio can be strictly larger than $2$, and Babaioff et al. exhibited an explicit example with ratio approximately $2.02$. In this work, we employ AlphaEvolve, an AI-guided evolutionary search framework, to explore the space of value distributions. We identify a new worst-case instance that yields an improved lower bound of $\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}} \ge \textbf{2.0749}$. This establishes a new lower bound on the worst-case performance of the Random-Offerer mechanism, demonstrating a wider efficiency gap than previously known.
- Abstract（参考訳）: 有名なマイヤーソン-サッタースウェイトの定理は、二国間貿易において、いかなるメカニズムも同時に完全に効率よく、ベイズ的インセンティブ互換(BIC)と予算均衡(BB)は成り立たないことを示している。
このことは、BICとBB機構によって達成可能な貿易(GFT)の利得が、どれだけ(完全に効率のよい)最初のベンチマークを近似できるかという疑問を自然に提起する。
最適BICとBBの機構は典型的には複雑で分布に依存しており、直接的に特徴付けることは困難である。
その結果、文献の多くはRandom-Offerer (RO) 機構のような単純なメカニズムを分析し、第1のbest GFTに対する定数要素保証を確立する。
重要なオープンな疑問は、第1ベスト(FB)効率に対するRO機構の最悪の性能に関するものである。
当初、近似比 $\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}}$ が 2$ に制限されていると仮定されていたが、最近の研究は、この予想に反例を提示した: Cai et al は、この比が 2$ より厳密に大きいことを証明し、Babaioff et al は、約 2.02$ の明示的な例を示した。
本研究では,AI誘導の進化的探索フレームワークであるAlphaEvolveを用いて,価値分布の空間を探索する。
我々は、$\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}} \ge \textbf{2.0749}$という改善された低いバウンダリを持つ新しい最悪のケースを識別する。
これにより、Random-Offerer機構の最悪の性能に対する新たな低い境界が確立され、従来よりも広い効率ギャップが示される。
関連論文リスト
- PACE: Defying the Scaling Hypothesis of Exploration in Iterative Alignment for Mathematical Reasoning [30.94339415375379]
N$のスケーリングは検証器のノイズを増幅し、有害分布シフトを誘導することを示す。
textbfPACE (Proximal Alignment via Corrective Exploration) を導入し、ブルートフォースマイニングを世代ベースの補正戦略に置き換える。
実証的な評価では、PACEはDPO-R1$(N=16)$より優れており、計算の約1/5$しか使用していない。
論文 参考訳（メタデータ） (2026-02-05T06:47:40Z) - Prediction-Augmented Mechanism Design for Weighted Facility Location [1.6552489352816389]
非一様重みを持つ戦略エージェントに対して、一貫性と堅牢性のバランスをとるための拡張アルゴリズムフレームワークを提供する。
重み付き FLP における$Oleft(n cdot fracW_maxW_min right)$Oleft(n cdot fracW_maxW_min right)$-robustness in weighted FLP, with fully predictions of all agent。
論文 参考訳（メタデータ） (2025-07-09T03:13:52Z) - Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
一般化ガウス機構(英語版)を考察し、ある$beta geq 1$に対して$e-frac| x |sigmabeta $ に比例した付加雑音項 $x$ をサンプリングする。
GGメカニズムとその変種に対するプライバシ会計は独立であり、プライバシ会計の計算コストを大幅に向上させることを示す。
論文 参考訳（メタデータ） (2025-06-14T15:49:25Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。
また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
論文 参考訳（メタデータ） (2022-04-14T20:57:50Z) - Rate-matching the regret lower-bound in the linear quadratic regulator
with unknown dynamics [6.287145010885044]
本稿では、O_p(sqrtT,textpolylog(T))$という新しい後悔の上限を確立する。
同時に$O_p(sqrtT,textpolylog(T))$の動的値に縛られる推定誤差を確立する。
論文 参考訳（メタデータ） (2022-02-11T17:50:14Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-16T17:52:32Z) - Towards Assessment of Randomized Smoothing Mechanisms for Certifying
Adversarial Robustness [50.96431444396752]
主な課題は、各ランダム化メカニズムの適切性を評価する方法である。
まず最初に、ガウスのメカニズムが$ell$-normを証明するための適切な選択肢であると結論付ける。
驚いたことに、ガウスのメカニズムは指数機構の代わりに$ell_infty$-normを証明するための適切な選択肢でもある。
論文 参考訳（メタデータ） (2020-05-15T03:54:53Z) - A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。
予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。
SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
論文 参考訳（メタデータ） (2020-02-12T18:54:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。