AI 기반 진화 탐색을 활용한 양방향 거래에서의 랜덤 오퍼러 메커니즘에 대한 새로운 하한 경계

A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search

유명한 마이어슨-새터스웨이트 정리에서는 양방향 거래에서 어떤 메커니즘도 동시에 완전 효율성, 베이지안 인센티브 호환성(BIC) 및 예산 균형(BB)을 만족할 수 없다는 것을 보여줍니다. 이는 BIC 및 BB 메커니즘이 달성할 수 있는 거래 이득(GFT)이 최적(완전 효율적인) 기준에 얼마나 근접할 수 있는지를 자연스럽게 제기합니다. 최적의 BIC 및 BB 메커니즘은 일반적으로 복잡하며 분포에 크게 의존하므로 직접적으로 특징짓기 어렵습니다. 따라서 많은 연구에서 랜덤 오퍼러(RO) 메커니즘과 같은 더 간단한 메커니즘을 분석하고 최적의 GFT에 대한 상수 배율 보장을 설정합니다. 중요한 미해결 문제는 RO 메커니즘의 최악의 성능이 최적의 효율성에 비해 어떻게 되는가입니다. 원래 가설은 근사 비율 $rac{ ext{GFT}_{ ext{FB}}}{ ext{GFT}_{ ext{RO}}}$가 $2$로 제한된다는 것이었지만, 최근 연구에서는 이 가설에 대한 반례가 제시되었습니다. Cai 등은 이 비율이 $2$보다 엄격하게 클 수 있음을 증명했고, Babaioff 등은 비율이 약 $2.02$인 명시적인 예시를 제시했습니다. 본 연구에서는 AI 기반 진화 탐색 프레임워크인 AlphaEvolve를 사용하여 값 분포 공간을 탐색합니다. 우리는 새로운 최악의 사례를 식별하여 $rac{ ext{GFT}_{ ext{FB}}}{ ext{GFT}_{ ext{RO}}} ext{가 } extbf{2.0749} ext{ 이상이라는 개선된 하한 경계를 얻습니다. 이는 랜덤 오퍼러 메커니즘의 최악의 성능에 대한 새로운 하한을 설정하며, 이전에는 알려지지 않았던 더 큰 효율성 격차를 보여줍니다.

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.