🤖 machine learning

How Much Due Diligence Before You Bid? Learning in Intractable Takeover Auctions

This paper uses self-play reinforcement learning on a computer model of takeover auctions to demonstrate that bidders should invest only a modest, finite amount in due diligence—especially when costs are high or competition is fierce—and shows that simple, general-purpose AI methods can effectively derive strong bidding strategies in complex, real-world scenarios where exact solutions are computationally infeasible.

Original authors: Zain Naboulsi

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zain Naboulsi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are about to buy a rare, vintage car at an auction. You don't know its true value, but you can pay a mechanic to inspect it. The more you pay the mechanic, the better you know the car's condition. But here's the catch: if you inspect it too much, you spend so much money on the inspection that you can't afford a good bid. If you inspect too little, you might overpay for a lemon.

This paper asks a simple question: How much should you pay for that inspection before you bid?

The authors, led by Zain Naboulsi, built a computer simulation of this exact scenario to find the answer. They didn't just guess; they used math and artificial intelligence to figure out the perfect balance.

Here is the breakdown of their journey, using simple analogies:

1. The Problem: The "Information Explosion"

Think of the auction as a giant maze. Every time you get a new piece of information (a "signal" from your mechanic), the maze gets exponentially bigger.

The Economic Question: "How many clues do I need to buy to win the most money?"
The Computer Problem: "How many clues can my computer handle before it gets too slow to solve the maze?"

The authors discovered that these two questions are linked. The more clues you buy, the harder it is for a computer to calculate the perfect strategy.

2. The Tools: The "Old School" vs. The "New School"

To solve these auction mazes, the team tested nine different computer programs (solvers). They fell into two camps:

The "Old School" Exact Solvers (CFR, MMD, PSRO): Imagine a librarian who reads every single book in a library to find the perfect answer. This is incredibly accurate and finds the true best strategy, but it takes a long time. If the library (the game) gets too big, the librarian gets overwhelmed and stops working.
The "New School" Learning Solvers (PPO, PPG): Imagine a student who learns by playing the game thousands of times, making mistakes, and slowly getting better. They don't read every book; they just learn patterns. They are faster and can handle huge libraries, but they might not be perfectly precise.

3. The Big Discovery: Who Wins?

The team ran a massive race on a standard laptop (no supercomputers needed).

In Small Mazes: The "Old School" librarians won every time. They were faster and more accurate. The "New School" students were good, but they couldn't beat the experts when the game was small enough to be solved exactly.
In Huge Mazes: This is where the "New School" shines. When the game got so big that the librarians couldn't even start, the students (specifically PPO and PPG) kept going. They found very good strategies where the experts simply couldn't run.

The Verdict: If the game is small, use the exact math. If the game is too big for math, use the learning AI.

4. The Answer to "How Much Due Diligence?"

Once they had the right tools, they answered the original business question: How many signals (clues) should a bidder buy?

They simulated a scenario where buying a clue costs money.

The Result: There is a "sweet spot." You should buy a finite number of clues.
The Rule: As the cost of each clue goes up, the number of clues you should buy goes down.
The Twist: If both bidders are smart and buying clues, they end up buying fewer clues than if only one was buying. Why? Because if your opponent is also well-informed, the extra value of your own extra clues drops. Competition makes everyone a little more conservative.

5. The "Toehold" Surprise

In the real world, sometimes a buyer already owns a small piece of the company they are trying to buy (a "toehold").

Common Belief: People think having a toehold makes you bid more aggressively.
The Paper's Finding: When they solved the true equilibrium (where both sides are smart and reacting to each other), the toehold didn't change the bid price much. Instead, it just increased the buyer's final profit. The "aggression" people expect disappears because the competition cancels it out.

6. The "Intractable" Frontier

Finally, the team pushed the simulation to a point where the game was so huge (with millions of possible scenarios) that no exact math could solve it.

They used the "New School" AI (PPO/PPG) to play.
They couldn't prove it was the perfect strategy (because the game was too big to check), but they proved it was much better than a naive bidder who just guesses.
They showed that even in these impossible-to-solve games, the learning AI could find a strategy that was nearly unbeatable.

Summary

This paper is a guide for deal-makers and a test for AI.

For Deal-Makers: Don't over-inspect. There is a specific, calculable point where buying more information stops paying off, especially if your competitor is also smart.
For AI: Simple learning algorithms (like PPO) are great for small games but can't beat exact math there. However, they are the only hope for solving massive, complex real-world games where exact math fails.

The authors released their code and games so anyone can try to solve these auction puzzles on their own laptops.

Technical Summary: How Much Due Diligence Before You Bid? Learning in Intractable Takeover Auctions

Problem Definition
The paper addresses a dual challenge in merger and acquisition (M&A) contexts: the economic question of how much due diligence a bidder should purchase before a takeover contest, and the computational question of when such a game becomes too large for exact solvers. In these contests, bidders act on private, noisy estimates of a target's value. Each unit of due diligence provides an additional private signal, which exponentially multiplies the strategy space. The authors posit that the economic optimum (how much diligence to buy) and the computational limit (when exact solvers fail) are governed by the same lever: the number of signals. While deal teams typically rely on judgment for the former, this work seeks to compute a defensible, model-backed number. Simultaneously, it investigates whether generic policy-gradient methods can rival specialized game-solving machinery (like Counterfactual Regret Minimization, CFR) in these economic settings, particularly as games grow beyond the reach of exact enumeration.

Methodology
The authors construct a reusable abstraction, DealGame, built on OpenSpiel, to model three types of takeover auctions:

Common-Value Takeover Auction: Two bidders compete for a target of unknown common value $W$ , receiving private noisy signals (Milgrom-Weber affiliated values). This induces a winner's curse.
Toehold Variant: A bidder holds a fraction $\theta$ of the target, altering the payoff structure.
Independent Private-Value Auction: Bidders draw independent values to isolate artifacts of the common-value structure.

The study benchmarks nine solvers across three families:

Exact/Tabular: CFR, Magnetic Mirror Descent (MMD), Policy-Space Response Oracles (PSRO) with exact oracles, and a tabular REINFORCE agent.
Deep Learning: PPO (Proximal Policy Optimization), PPG (Phasic Policy Gradient), a generic deep policy gradient (DeepPG), Deep CFR, and Neural Fictitious Self-Play (NFSP).
Evaluation Metric: For solver benchmarks, the authors use exact exploitability (NashConv halved) computed via tree traversal on zero-sum renderings of the games. For economic analysis (due diligence value, toeholds), they solve the genuine general-sum Bayes-Nash equilibrium exactly using a tensor factorization approach, avoiding the distortions of the zero-sum rendering.

Key Contributions

Economic Quantification of Diligence: The paper solves the auction's own-profit Bayes-Nash equilibrium to determine the optimal number of signals ( $k^*$ ) a bidder should acquire. It finds that the optimal amount is finite and decreases monotonically as the per-signal cost rises. Crucially, when both bidders choose diligence in a symmetric equilibrium, the optimal amount is more conservative than in one-sided calculations because the marginal value of signals diminishes as the rival becomes better informed.
Solver Benchmarking: The authors provide a like-for-like comparison of solvers on commodity hardware. They find that while exact solvers (CFR, MMD, PSRO) remain superior in accuracy and speed for any game small enough to tabulate, generic policy-gradient methods (PPO and PPG) are the strongest learning solvers, significantly outperforming Deep CFR, NFSP, and generic deep policy gradients in exploitability and sample efficiency.
Scaling and Intractability: A scaling study reveals that while exact CFR's runtime grows steeply with tree size, PPO's wall-clock cost remains roughly constant per target. However, within the enumerable range, PPO does not overtake CFR. The paper extends into a genuinely intractable regime (a multi-signal auction with $\sim 10^{14}$ histories) where exact solvers cannot run. Here, PPO and PPG drive a learned-best-response exploitability estimate to a resolution floor (below 0.04), significantly outperforming naive bidders, though the authors explicitly note this is a lower bound, not a Nash certificate.
Toehold Dynamics: The study clarifies that while zero-sum renderings suggest toeholds increase bidding aggressiveness, the genuine general-sum equilibrium shows that toeholds primarily increase bidder profit (value) rather than equilibrium bid amounts, as the aggressiveness is competed away in the symmetric equilibrium.

Results

Diligence Cutoff: The profit-maximizing amount of diligence is finite. In the base model, as the cost per signal rises, the optimal $k^*$ steps down (e.g., from 5 to 1), skipping intermediate values depending on the lumpy marginal value of information. This holds even in symmetric equilibria where both bidders optimize diligence.
Solver Performance: On tabulatable games, exact solvers achieve the lowest exploitability (e.g., CFR $\approx 0.003$ ) and fastest convergence. Among learning methods, PPO and PPG achieve exploitability around $0.013–0.016$ , roughly an order of magnitude better than Deep CFR ($0.122$) and NFSP ($0.508$).
Intractable Regime: In a game with 8 signals per bidder (too large for enumeration), PPO and PPG policies achieve an estimated exploitability of 0.000 (clamped to the resolution floor), whereas a naive unshaded bidder has an exploitability of 0.071. The learned best-response estimator was calibrated against exact values on smaller, tractable versions of the game to validate its tightness.

Significance and Claims
The paper claims to offer a "defensible, model-backed number" for the economic question of due diligence, demonstrating that the optimal investment is finite and sensitive to cost and competition. Computationally, it challenges the necessity of frontier models or specialized solvers for deal-making under imperfect information, showing that cheap self-play loops on commodity CPUs can produce strong policies.

However, the authors are modest in their claims. They explicitly state that for any game small enough to tabulate, exact solvers remain the best option; the learning methods do not "win" the overall race in the enumerable regime. The significance of PPO and PPG lies in their ability to operate in the "genuinely intractable" regime where exact methods fail. The paper does not claim to have solved the intractable games to a Nash equilibrium (certified by upper bounds) but rather provides a calibrated lower bound on exploitability that demonstrates the learned policies are far superior to naive strategies. The work serves as a foundation for richer, larger-scale economic games, bridging the gap between recreational game-solving benchmarks and real-world economic auctions.