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

A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search Yang Cai Yale University yang.cai@yale.edu Authors are alphabetically ordered. Part of this work was done while Yang Cai was visiting Google. Vineet Gupta Google DeepMind vineet@google.com Zun Li Google DeepMind lizun@google.com Aranyak Mehta Google Research aranyak@google.com 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 (B). This naturally raises the question of how closely the gains from trade (GFT) achievable by a BIC and B mechanism can approximate the first-best (fully efficient) benchmark. The optimal BIC and B 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 GFTFBGFTRO GFT_FBGFT_RO is bounded by 22, recent work provided counterexamples to this conjecture: Cai et al. (2021) proved that the ratio can be strictly larger than 22, and Babaioff et al. (2021) exhibited an explicit example with ratio approximately 2.022.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 GFTFBGFTRO≥2.0749 GFT_FBGFT_RO 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. 1 Introduction The fundamental limits of efficiency in bilateral trade are a central question in mechanism design. In the standard bilateral-trade setting with independent private values, the environment consists of a single seller and a single buyer: the seller has a private cost s for parting with the item, drawn from a distribution FsF_s, and the buyer has a private value b for acquiring the item, drawn independently from a distribution FbF_b. The goal is to design a mechanism that maximizes efficiency, measured by gains from trade (GFT): trade yields b−sb-s if it occurs and 0 otherwise (equivalently, max⁡b−s,0 \b-s,0\ under the efficient allocation). The Myerson–Satterthwaite theorem establishes that no mechanism can be simultaneously fully efficient, Bayesian incentive compatible (BIC), individually rational (IR), and budget balanced (B). Consequently, a long line of work studies how well BIC, IR, and B mechanisms can approximate the first-best (fully efficient) GFT. The optimal BIC, IR, and B 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 the first-best (FB) benchmark. The metric of interest is the approximation ratio ρ=GFTFBGFTRO.ρ\;=\; GFT_FBGFT_RO\,. (1) The goal is to determine the worst-case value of ρ, i.e., the supremum of ρ over all distribution pairs (Fs,Fb)(F_s,F_b). While it was originally hypothesized that this approximation ratio is bounded by 2, recent work provided counterexamples to this conjecture: Cai et al. (2021) proved that the ratio can be strictly larger than 22, and Babaioff et al. (2021) exhibited an explicit example with ratio approximately 2.022.02. In this work, we employ AlphaEvolve, an AI-guided evolutionary search framework, to explore the space of valuation distributions. By reformulating the search for worst-case distributions as a program synthesis problem, we utilize a Large Language Model (LLM) coding agent to evolve distribution structures that maximize the efficiency gap. We report the discovery of a new worst-case seller distribution. We identify a mixture of modulated power laws with cumulative distribution function Pr⁡[s≤m]= 0.2​zmαeff​(zm)+ 0.8​zm4, [s≤ m]\;=\;0.2\,z_m _eff(z_m)\;+\;0.8\,z_m^4, (2) where zm:=m+1H+1z_m:= m+1H+1 and the (sinusoidally) modulated exponent is αeff​(z):=0.15+0.05​sin⁡(2​π​z), _eff(z):=0.15+0.05 (2π z), (3) with H=20000H=20000. After discretizing the seller distribution (by rounding the induced probability mass function) and pairing it with the Discrete Equal Revenue distribution for the buyer, the resulting instance achieves an approximation ratio of 2.07492.0749 against the Random Offerer mechanism. Consequently, 2.07492.0749 is a new lower bound on the mechanism’s worst-case approximation ratio. As an illustration of the asymmetry between the sub-mechanisms, our worst-case instance yields an expected First-Best GFT of GFTFB≈1.2322GFT_FB≈ 1.2322. The individual sub-mechanisms yield a Seller-Offering GFT of GFTSO≈0.3312GFT_SO≈ 0.3312 and a Buyer-Offering GFT of GFTBO≈0.8565GFT_BO≈ 0.8565. This results in a combined Random Offerer GFT of GFTRO≈0.5939GFT_RO≈ 0.5939. Consequently, the approximation ratio is ρ≈2.0749ρ≈ 2.0749, while the ratio between the First-Best GFT and the maximum of the two sub-mechanisms is approximately 1.43871.4387. In contrast, the previous state-of-the-art only shows that the ratio between the First-Best GFT and max⁡GFTBO,GFTSO \GFT_BO,GFT_SO\ is at most 4/34/3 (Babaioff et al., 2021). 2 Related Work Efficiency in Bilateral Trade. Motivated by the impossibility result of Myerson and Satterthwaite (1983), there is a growing line of research on designing mechanisms that provably approximate the optimal gains-from-trade (GFT) (e.g., Blumrosen and Mizrahi, 2016; Brustle et al., 2017; Deng et al., 2022; Fei, 2022; Hartline and Wang, 2025; Deng et al., 2025) in the bilateral trade setting, as well as in more general settings such as double auctions and multi-dimensional two-sided markets (e.g., Babaioff et al., 2018; Cai et al., 2021). A complementary line of work designs mechanisms that approximate the optimal welfare, in either bilateral trade (e.g., Blumrosen and Dobzinski, 2021; Kang et al., 2022; Cai and Wu, 2023; Dobzinski and Shaulker, 2024; Dobzinski et al., 2025) or more general two-sided markets (e.g., Colini-Baldeschi et al., 2016, 2020; Dütting et al., 2014, 2026). Although exactly optimizing welfare is equivalent to optimizing GFT, approximating welfare is strictly easier than approximating GFT. Indeed, any c-approximation to GFT is automatically a c-approximation to welfare, whereas the opposite direction is generally false. In this paper, we focus on the approximability of GFT. Performance of the Random Offerer Mechanism. The Random Offerer (RO) mechanism was introduced by Brustle et al. (2017), who showed that RO achieves at least half of the second-best GFT. Since the second-best GFT is often a complicated object, researchers frequently use RO as a simple proxy. • The breakthrough of Deng et al. (2022), which shows that the first-best GFT is at most a constant factor larger than the second-best GFT in bilateral trade, builds on RO. In particular, they proved that RO guarantees at least a 1/8.231/8.23 fraction (approximately 0.1210.121) of the first-best gains from trade. • Fei (2022) subsequently tightened this bound, improving the guarantee to 1/3.151/3.15. AI guided algorithm design using AlphaEvolve The AlphaEvolve system is presented in Novikov et al. (2025). AlphaEvolve is a significant enhancement of the FunSearch system described in Romera-Paredes et al. (2024). Novikov et al. (2025) describe new algorithms discovered by AlphaEvolve across diverse domains, including faster matrix multiplication, various mathematical problems, and datacenter optimization. Subsequent work has leveraged AlphaEvolve to address problems in mathematics and theoretical computer science. For example, (Georgiev et al., 2025) matched the best known solutions for a large number of mathematical problems and improved several of them. (Nagda et al., 2025) used AlphaEvolve to discover combinatorial structures that yield new results in complexity theory for the Max-Cut and Traveling Salesman problems. 3 Problem Formulation 3.1 Bilateral Trade Setting We consider a standard bilateral trade setting with independent private values. The environment consists of a single seller with a cost s and a single buyer with a valuation b. • The seller’s cost s is drawn from a probability distribution FsF_s with support in the domain Ω . • The buyer’s valuation b is drawn from a probability distribution FbF_b with support in the domain Ω . We assume the distributions are independent and known to the mechanism, while the realizations s and b are private information. 3.2 Efficiency Benchmarks The metric of interest is the expected Gains from Trade (GFT), defined as the expected surplus generated by the transaction. 3.2.1 First-Best Efficiency (FB) The First-Best benchmark represents the maximum theoretically achievable surplus, where trade occurs if and only if b≥sb≥ s. The expected First-Best GFT is given by: GFTFB​(Fs,Fb)=s∼Fs,b∼Fb​[(b−s)+]=∬b≥s(b−s)​Fs​(s)​Fb​(b)GFT_FB(F_s,F_b)=E_s F_s,b F_b [(b-s)^+ ]= _b≥ s(b-s)\,dF_s(s)\,dF_b(b) (4) 3.2.2 The Random Offerer Mechanism (RO) The Random Offerer mechanism operates by randomizing between two sub-mechanisms with equal probability: 1. Seller-Offering (SO): With probability 0.50.5, the seller proposes a take-it-or-leave-it price psp_s. The seller chooses psp_s to maximize their expected profit given the buyer’s distribution: ps∗​(s)=arg⁡maxp⁡((p−s)⋅Prb∼Fb⁡[b≥p])p_s^*(s)= _p ((p-s)· _b F_b[b≥ p] ) Trade occurs if b≥ps∗​(s)b≥ p_s^*(s). The expected GFT for this sub-mechanism is: GFTSO=s,b​[(b−s)⋅​(b≥ps∗​(s))]GFT_SO=E_s,b [(b-s)·I(b≥ p_s^*(s)) ] 2. Buyer-Offering (BO): With probability 0.50.5, the buyer proposes a take-it-or-leave-it price pbp_b. The buyer chooses pbp_b to maximize their expected profit given the seller’s distribution: pb∗​(b)=arg⁡maxp⁡((b−p)⋅Prs∼Fs⁡[s≤p])p_b^*(b)= _p ((b-p)· _s F_s[s≤ p] ) Trade occurs if s≤pb∗​(b)s≤ p_b^*(b). The expected GFT for this sub-mechanism is: GFTBO=s,b​[(b−s)⋅​(s≤pb∗​(b))]GFT_BO=E_s,b [(b-s)·I(s≤ p_b^*(b)) ] The total expected GFT of the Random Offerer mechanism is: GFTRO​(Fs,Fb)=12​GFTSO+12​GFTBOGFT_RO(F_s,F_b)= 12GFT_SO+ 12GFT_BO (5) 3.3 Approximation Ratio and Objective We define the approximation ratio ρ as the ratio of the First-Best efficiency to the efficiency of the Random Offerer mechanism. We aim to identify the worst-case distributions that maximize this ratio. The optimization problem is defined as finding the supremum of ρ over the space of all possible distribution pairs (Fs,Fb)(F_s,F_b): ρ∗=supFs,FbGFTFB​(Fs,Fb)GFTRO​(Fs,Fb)ρ^*= _F_s,F_b GFT_FB(F_s,F_b)GFT_RO(F_s,F_b) (6) 4 Methodology: AI-Guided Discovery To explore the limits of bilateral trade efficiency, we employ AlphaEvolve, a search framework driven by a Large Language Model (LLM) coding agent. This approach reformulates the search for worst-case distributions as a program synthesis problem. Rather than optimizing numerical parameters within a pre-defined function, the agent evolves Python code to discover novel distribution structures that maximize the efficiency gap. 4.1 Search Configuration Our optimization objective is to find the lower bound of the approximation ratio ρ, defined as the ratio of First-Best (FB) efficiency to the Random Offerer (RO) efficiency. To strictly target the worst-case performance, we configure the search space as follows: Fixed Buyer Distribution Following the counterexample structure provided by Babaioff et al. (2021), we fix the buyer’s valuation to the Discrete Equal Revenue Distribution. The buyer’s survival function is held constant throughout the search: Pr(b≥m)=1mfor m∈1,…,H.Pr(b≥H+1)=0 (b≥ m)= 1m m∈\1,…,H\. (b≥ H+1)=0 (7) where H is the highest possible value. Evolving Seller Distribution The search focuses exclusively on the seller’s valuation distribution FsF_s. The evolutionary agent iteratively modifies the source code of a generator function, get_seller_distributions(), which constructs the seller’s Cumulative Distribution Function (CDF). 4.2 Evolutionary Process The search process operates as an iterative improvement loop: 1. Initialization: To avoid biasing the search toward complex pre-conceived structures, we use a uniform distribution as the initial distribution: Pr⁡(s≤m)=m+1H+1for ​m∈1,…,H (s≤ m)= m+1H+1 m∈\1,…,H\ (8) 2. Code Evolution: In each generation, the LLM agent proposes mutations to the Python code. These modifications can range from simple parameter tuning to the introduction of non-linear functional forms (e.g., power laws, sinusoidal modulation). 3. Fitness Evaluation: Each candidate program is executed to generate a discrete distribution over the domain 0,…,H\0,…,H\. The fitness of the candidate is strictly defined as the resulting approximation ratio. 4.3 Evaluation and Numerical Precision A critical challenge in identifying worst-case distributions is distinguishing genuine theoretical gains from floating-point errors, particularly when ratios differ by small margins (e.g., 10−310^-3). To ensure the validity of our results, we implemented a rigorous evaluation pipeline: • Discrete Domain: We utilize a discrete integer domain up to H=20,000H=20,000. This large support allows for fine-grained approximation of continuous structures while maintaining computational tractability. • Rounding and High-Precision Arithmetic: To avoid numerical issues, we round the probability mass functions to multiples of a small ε=10−15 =10^-15 and perform the computation using integer arithmetic rather than floating-point operations. • Exact GFT Computation: We compute the Gains from Trade (GFT) exactly. – For First-Best (FB), we sum the surplus over all disjoint pairs (s,b)(s,b) where b≥sb≥ s. – For Random Offerer (RO), we explicitly solve for the optimal reserve prices ps∗​(s)p^*_s(s) and pb∗​(b)p^*_b(b) for every possible realization of s and b, respectively. The final RO efficiency is the exact average of the Seller-Offering and Buyer-Offering sub-mechanisms. This rigorous numerical approach ensures that the reported approximation ratio of 2.0749 represents a verified lower bound on the mechanism’s efficiency. Due to rounding, however, our analysis only establishes this improved lower bound for a rounded version of the mixture of modulated power laws. Determining the exact value of ρ for the unrounded mixture of modulated power laws remains open. 4.4 Other attempts We also experimented with two other evolutionary approaches: • Starting from the solution obtained via the process above, we fix the seller’s distribution and evolve the buyer’s distribution, initialized with the equal revenue distribution. This approach led to a slight improvement (2.08), which we do not describe in detail here. One could imagine continuing this process by alternating between the two sides whenever progress stalls; we leave such explorations for future work. • We also ran experiments evolving both the seller and buyer distributions simultaneously. This produced a new lower bound as well, although it did not surpass 2.07 and progress was significantly slower. The slow progress in this setting ultimately led us to the approach adopted in this paper: fixing the buyer’s distribution and evolving only the seller’s distribution. 5 Results Our application of the AlphaEvolve framework has successfully identified a new counterexample that establishes a tighter lower bound on the worst-case approximation ratio of the Random Offerer mechanism. 5.1 Main Result We report a worst-case approximation ratio of 2.0749. This result is achieved with a discretization domain of H=20,000H=20,000. The specific expected Gains from Trade (GFT) components that yield this ratio are detailed below: • First-Best GFT (GFTFBGFT_FB): 1.2322 • Seller-Offering GFT (GFTSOGFT_SO): 0.3312 • Buyer-Offering GFT (GFTBOGFT_BO): 0.8565 • Random Offerer GFT (GFTROGFT_RO): 0.5939 • Approximation Ratio (ρ): 2.0749 This finding improves upon the previous best-known lower bound of ≈2.02≈ 2.02 established by Babaioff et al. (2021). 5.2 Discovered Distributions The configuration yielding this ratio consists of the fixed buyer distribution (Discrete Equal Revenue) paired with a novel, evolved seller distribution. 5.2.1 Seller Distribution Structure The evolutionary search converged on a Mixture of Modulated Power Laws. Unlike standard power-law distributions used in previous counterexamples, the discovered distribution FsF_s employs a sinusoidal modulation of the exponent. For a normalized domain value zm=m+1H+1z_m= m+1H+1, the Cumulative Distribution Function (CDF) is defined as: Fs​(m)=w⋅zmαeff​(zm)+(1−w)⋅zmα2F_s(m)=w· z_m _eff(z_m)+(1-w)· z_m _2 (9) where: • The mixing weight is w=0.20w=0.20. • The secondary component is a standard power law with α2=4.0 _2=4.0. • The primary component uses a modulated exponent: αeff​(zm)=0.15+0.05​sin⁡(2​π​zm) _eff(z_m)=0.15+0.05 (2π z_m) (10) The distribution is shown in Figure 1. Figure 1: Seller’s distribution as found by AlphaEvolve 5.3 Evolved Code Artifact The Python code generated by the AlphaEvolve agent that constructs this distribution is presented below. The algorithm discovered that introducing the math.sin function to modulate the power law exponent (a1) was critical for maximizing the ratio. Listing 1: Discovered Seller Distribution. ⬇ def get_seller_distributions(): # Domain size for evaluation H = 20000 # Evolved Parameters a1_base = 0.15 # Base exponent for first component a2 = 4.0 # Exponent for second component w = 0.20 # Weight for first component # Sinusoidal modulation parameters discovered by AlphaEvolve a1_amp = 0.05 # Amplitude of modulation a1_freq = 2.0 # Frequency (cycles over domain) cdf_s = norm_factor = H + 1.0 prev_cdf = 0.0 for m in range(H + 1): # Normalized support z in [0, 1] base = max(0.0, min(1.0, (m + 1.0) / norm_factor)) # Modulate the exponent a1 sinusoidally # The argument to sin scales to 2*pi over the domain a1_eff = a1_base + a1_amp * math.sin(a1_freq * math.pi * base) a1_eff = max(1e-9, a1_eff) # Safety floor # Compute mixture components cdf1_val = base ** a1_eff cdf2_val = base ** a2 # Weighted mixture current_cdf = w * cdf1_val + (1.0 - w) * cdf2_val # Enforce constraints current_cdf = max(0.0, min(current_cdf, 1.0)) current_cdf = max(current_cdf, prev_cdf) # Monotonicity cdf_s[m] = current_cdf prev_cdf = current_cdf return H, cdf_s The discovery of the sinusoidal modulation parameter a1_amp = 0.05 highlights the capability of the evolutionary search to identify non-intuitive functional forms that human theoretical analysis might overlook. 6 Conclusion In this work, we revisited the fundamental efficiency limits of the Random Offerer (RO) mechanism in bilateral trade. By deploying AlphaEvolve, an AI-guided evolutionary search framework, we successfully identified a new lower bound on the worst-case approximation ratio. Our primary contribution is the discovery of a specific valuation distribution pair that yields an approximation ratio of 2.0749. This result widens the best previous efficiency gap of ≈2.02≈ 2.02 provided by Babaioff et al. (2021). The structure of the discovered seller distribution—a mixture of power laws modulated by a sinusoidal function is significantly different from the previous worst-case distribution, and may suggest new ways that the Random Offerer mechanism can be exploited. Methodologically, this study highlights the potential of large language models as coding agents in microeconomic theory. AlphaEvolve’s ability to synthesize non-intuitive functional forms—such as the sinusoidally modulated exponent identified in our results—suggests that AI-driven search can be a powerful tool for probing the limits of mechanism design. This approach may be applicable to other open problems in auction theory and algorithmic game theory, where analytical derivations of worst-case bounds remain elusive. References M. Babaioff, Y. Cai, Y. A. Gonczarowski, and M. Zhao (2018) The best of both worlds: asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade. In Proceedings of the 2018 ACM Conference on Economics and Computation, p. 373–373. Cited by: §2. M. Babaioff, S. Dobzinski, and R. Kupfer (2021) A note on the gains from trade of the random-offerer mechanism. arXiv preprint arXiv:2111.07790. External Links: Link Cited by: §1, §1, §4.1, §5.1, §6. L. Blumrosen and S. Dobzinski (2021) (Almost) efficient mechanisms for bilateral trading. Games and Economic Behavior 130, p. 369–383. Cited by: §2. L. Blumrosen and Y. Mizrahi (2016) Approximating gains-from-trade in bilateral trading. In International Conference on Web and Internet Economics, p. 400–413. Cited by: §2. J. Brustle, Y. Cai, F. Wu, and M. Zhao (2017) Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, C. Daskalakis, M. Babaioff, and H. Moulin (Eds.), p. 589–590. Cited by: §2, §2. Y. Cai, K. Goldner, S. Ma, and M. Zhao (2021) On multi-dimensional gains from trade maximization. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 1079–1098. Cited by: §1, §2. Y. Cai and J. Wu (2023) On the optimal fixed-price mechanism in bilateral trade. arXiv preprint arXiv:2301.05167. Cited by: §2. R. Colini-Baldeschi, P. W. Goldberg, B. d. Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta (2020) Approximately efficient two-sided combinatorial auctions. ACM Transactions on Economics and Computation (TEAC) 8 (1), p. 1–29. Cited by: §2. R. Colini-Baldeschi, B. d. Keijzer, S. Leonardi, and S. Turchetta (2016) Approximately efficient double auctions with strong budget balance. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, p. 1424–1443. Cited by: §2. Y. Deng, J. Mao, B. Sivan, K. Wang, and J. Wu (2025) Approximately efficient bilateral trade with samples. In Proceedings of the 26th ACM Conference on Economics and Computation, p. 206–223. Cited by: §2. Y. Deng, J. Mao, B. Sivan, and K. Wang (2022) Approximately efficient bilateral trade. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, p. 718–721. Cited by: 1st item, §2. S. Dobzinski, A. Eden, K. Goldner, A. Shaulker, and T. Tsilivis (2025) Bilateral trade with interdependent values: information vs. approximation. In Proceedings of the 26th ACM Conference on Economics and Computation, p. 641–665. Cited by: §2. S. Dobzinski and A. Shaulker (2024) Bilateral trade with correlated values. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, p. 237–246. Cited by: §2. P. Dütting, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser (2026) Efficient two-sided markets with limited information. SIAM Journal on Computing 55 (1), p. 65–92. Cited by: §2. P. Dütting, T. Roughgarden, and I. Talgam-Cohen (2014) Modularity and greed in double auctions. In Proceedings of the fifteenth ACM conference on Economics and computation, p. 241–258. Cited by: §2. Y. Fei (2022) Improved approximation to first-best gains-from-trade. In International Conference on Web and Internet Economics, p. 204–218. Cited by: 2nd item, §2. B. Georgiev, J. Gómez-Serrano, T. Tao, and A. Z. Wagner (2025) Mathematical exploration and discovery at scale. arXiv preprint arXiv:2511.02864. Cited by: §2. J. Hartline and K. Wang (2025) A geometric analysis of gains from trade. arXiv preprint arXiv:2508.06469. Cited by: §2. Z. Y. Kang, F. Pernice, and J. Vondrák (2022) Fixed-price approximations in bilateral trade. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 2964–2985. Cited by: §2. R. B. Myerson and M. A. Satterthwaite (1983) Efficient mechanisms for bilateral trading. Journal of Economic Theory 29 (2), p. 265–281. External Links: ISSN 0022-0531 Cited by: §2. A. Nagda, P. Raghavan, and A. Thakurta (2025) Reinforced generation of combinatorial structures: hardness of approximation. arXiv preprint https://arxiv.org/pdf/2509.18057. Cited by: §2. A. Novikov, N. Vũ, M. Eisenberger, E. Dupont, P. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. Ruiz, A. Mehrabian, et al. (2025) AlphaEvolve: a coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131. Cited by: §2. B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi (2024) Mathematical discoveries from program search with large language models. Nature 625 (7995), p. 468–475. External Links: Document Cited by: §2. Appendix A Evaluation Code Listing 2: Evaluation Code. ⬇ import numpy as np try: DTYPE = np.float128 # On some systems, float128 is just an alias for float64. This checks for that. if np.finfo(DTYPE).nexp == np.finfo(np.float64).nexp: DTYPE = np.float64 except AttributeError: DTYPE = np.float64 def _derive_pmf_from_integer_cdf(cdf, H): """Helper to derive PMF from CDF using NumPy types.""" pmf = m:0 for m in range(H + 1) pmf[0] = cdf.get(0, 0) for m in range(1, H + 1): # Ensure default value is of the correct type pmf[m] = cdf.get(m, 0) - cdf.get(m - 1, 0) if pmf[m] < 0: pmf[m] = 0 return pmf def _derive_pmf_from_integer_sf(sf, H): """Helper to derive PMF from Survival Function using NumPy types.""" pmf = m: 0 for m in range(H + 1) for m in range(H): pmf[m] = sf.get(m, 0) - sf.get(m + 1, 0) if pmf[m] < 0: pmf[m] = 0 pmf[H] = sf.get(H, 0) return pmf def _round_to_integer_distribution(cdf_s, sf_b, H, rtol): if not rtol > 0: raise ValueError("Rounding tolerance ’rtol’ must be a positive number.") # Use dictionary comprehensions for a concise and efficient implementation. # For each item in the input dictionary, the key (valuation) is kept, # and the value (probability) is rounded to the nearest multiple of rtol. # The type of the result will be preserved as DTYPE. rounded_cdf_s = val: round(prob / rtol) for val, prob in cdf_s.items() rounded_sf_b = val: round(prob / rtol) for val, prob in sf_b.items() for m in range(H + 1): rounded_cdf_s[m] = rounded_cdf_s.get(m, 0) rounded_sf_b[m] = rounded_sf_b.get(m, 0) return rounded_cdf_s, rounded_sf_b def calculate_all_gains_from_trade_rounded_integer_fixed_seller(H, sf_b, cdf_s): ### Make sure support is not too large if H > 20000: return DTYPE(-1) ### The number of digits to keep after the decimal point tolerance = DTYPE("1e-15") ### Get fixed seller distribution # cdf_s = get_fixed_seller_distribution(H) ### Round the CDF for seller and SF for buyer to integer multiples of tolerance, add missing entries, and check whether the CDF/SF’s are valid cdf_s_np, sf_b_np = _round_to_integer_distribution(cdf_s, sf_b, H, tolerance) ### Check if the integer distributions have valid monotone cdf and sf. # _validate_integer_distributions(H, cdf_s_np, sf_b_np) pmf_s = _derive_pmf_from_integer_cdf(cdf_s_np, H) pmf_b = _derive_pmf_from_integer_sf(sf_b_np, H) first_best_gft = 0 for s_val in range(H + 1): if pmf_s[s_val] <= 0: continue for b_val in range(s_val, H + 1): if pmf_b[b_val] <= 0: continue gain = b_val - s_val first_best_gft += pmf_s[s_val] * pmf_b[b_val] * gain gft_seller_offering = 0 for s_val in range(H + 1): if pmf_s[s_val] <= 0: continue max_seller_profit = 0 p_s_opt = s_val for p_offer in range(s_val, H + 1): prob_buyer_accepts = sf_b_np.get(p_offer, 0) current_seller_profit = prob_buyer_accepts * (p_offer - s_val) if current_seller_profit >= max_seller_profit: max_seller_profit = current_seller_profit p_s_opt = p_offer expected_gft_for_this_s = 0 for b_val in range(p_s_opt, H + 1): if pmf_b[b_val] <= 0: continue gain = b_val - s_val expected_gft_for_this_s += pmf_b[b_val] * gain gft_seller_offering += pmf_s[s_val] * expected_gft_for_this_s gft_buyer_offering = 0 for b_val in range(H + 1): if pmf_b[b_val] <= 0: continue max_buyer_profit = 0 p_b_opt = b_val for p_offer in range(b_val + 1): prob_seller_accepts = cdf_s_np.get(p_offer, 0) current_buyer_profit = prob_seller_accepts * (b_val - p_offer) if current_buyer_profit > max_buyer_profit: max_buyer_profit = current_buyer_profit p_b_opt = p_offer expected_gft_for_this_b = 0 for s_val in range(p_b_opt + 1): if pmf_s[s_val] <= 0: continue gain = b_val - s_val expected_gft_for_this_b += pmf_s[s_val] * gain gft_buyer_offering += pmf_b[b_val] * expected_gft_for_this_b gft_random_offerer = DTYPE(0.5) * (gft_seller_offering + gft_buyer_offering) return first_best_gft/gft_random_offerer