Learning and Verifying Complex Games with AI-Assisted Theorem Proving

Recent advances in AI-assisted theorem proving—e.g., search empowered by large language models, auto-formalisation, and solver-produced certificates—show that machines can spot structure that they use to propose mathematical theory, and even produce verifiable proofs or counterexamples. These hybrid workflows are particularly strong at pattern recognition and are especially useful to tackle search domains where combinatorial blow-up is a key obstacle.

This project brings those advances to computational social choice and algorithmic game theory, which deal with collective and strategic decision making. There, a lot of the theory (e.g., of preference encoding or inter-agent incentives) can be formalized in large and combinatorially complex, but finite spaces. These spaces can often fail to satisfy certain properties (like the existence of stable outcomes), but the instances where this failure happens can be rare edge cases that are hard to find. Hence, computer-aided techniques often reach their limits.

Building on prior work that used linear programming to construct specific games, we will systematise the human–machine loop and progress from semi-automated toward fully automated construction and certification of such instances. Our goals are threefold.

(1) Discovery: design a generator that searches the space of, e.g., preference profiles or games to surface combinatorially rare phenomena by aiding exploration. For example, the generator could combine LLM-guided proposal moves with exact optimisation (LP/MIP) or SAT/SMT encodings.

(2) Verification: build a modular verifier that emits machine-checkable certificates.

(3) Explanation: extract the prohibitive structural patterns in order to predict similar circumstances in a broader context.

We will explore prominent problems in coalition formation, voting, and matching, and develop learning loops between generator and verifier. The expected outcomes are: (1) proof of concept by reconstructing instances/games with similar properties as sophisticated human-created games. (2) attack open problems that seem to have rich combinatorics. (3) deduce theoretical insights to understand the frontier between typical and rare behaviour in complex social decision problems.