We Had Proven the Auction. Not What Decides Who Enters It.

Our auction scoring formula has been machine-proven with Lean 4 for months. The layer above it — who even gets a shot at a slot — was ordinary, unproven code until a few days ago. Six new theorems close that gap.

"Explainable ranking" and "auditable AI" have become cheap words in ad tech. Almost every vendor promises them. Almost none show the proof — and fewer still show exactly where the proof stops. We had a gap of that kind ourselves, found it in early November, and closed it. This is how. The gap between the score and the winner Nexbid's auction has been machine-proven with Lean 4 for months, not merely tested. The production scoring formula — score = 0.3 · bid + 0.3 · similarity + 0.2 · quality + 0.2 · context — lives in our internal auction module, and theorems like score_bounded (the score stays between 0 and 1 for every valid input) or gated_never_wins (a blocked bid can never win, however high it is) already covered it. What those proofs did not cover was the layer above the score. Our agentic ad server — the part of Nexbid that actually fills ad slots at networks and publishers — decides each slot in several steps: who is even still eligible (an advertiser or category must not take the same slot twice)? Which priority tier applies right now (tiers 1–2 are guaranteed bookings and go first; everything else competes on score)? And only then: who wins the remaining comparison? Those three steps — exclusion, priority tier, tie-break — sat, until a few days ago, as ordinary TypeScript in our ad server's selection function. Tested, yes. Proven, no. The formula had a guarantee. The question of who even gets to reach the formula did not. Worth noting: the ad server never built a second, parallel auction. Its selection function calls the scoring function in our auction module directly — the same, already-proven function. So there was never a risk of two implementations drifting apart over time. The gap sat exclusively in the layer on top. What is proven now On November 4th we added six new theorems to lean-verification/NexbidVerify/Adserver/Decide.lean, covering exactly that layer. In plain language: The winner is always a real candidate. The selection function cannot invent one — the winner was always among the offers that were actually submitted ( selectBest_mem ). The winner passed the exclusion check. Anyone who already holds a slot on this inventory (as an advertiser, or in its category) is out of the running before the comparison happens, not corrected afterwards ( winner_not_excluded ). The winner comes from the highest priority tier …

Author
Nexbid Engineering
Published
2026-11-05
Topics
Verification, Ad Tech, Agentic