Study improves understanding of why agentic theorem provers succeed.
problem Understanding which components of agentic theorem provers improve proof success.
method Statistical provability theory and finite-horizon reachability MDP model.
result Bounds provability gap and explains components' effectiveness.
New model shows hierarchical proof structure helps theorem provers.
problem How to efficiently learn proofs from teacher traces.
method Model proof search as MDP, analyze imitation learning from traces.
result Hierarchical proof structure leads to more efficient learning.
Automated theorem prover proves non-orderability of groups.
problem Proving non-orderability of groups.
method Generic automated theorem prover with tools like positive cones, torsions, generalised torsions, and cofinal elements.
result Demonstrated automated proof of non-orderability of groups.
We consider the task of automated theorem proving, a key AI task. Deep learning has shown promise for training theorem provers, but there are limited human-written theorems and proofs available for supervised learning. To address this limitation, we propose to learn a neural generator that automatically synthesizes the…
The problem-solving in automated theorem proving (ATP) can be interpreted as a search problem where the prover constructs a proof tree step by step. In this paper, we propose a deep reinforcement learning algorithm for proof search in intuitionistic propositional logic. The most significant challenge in the application…
In this paper, we demonstrate how to do automated theorem proving in the presence of a large knowledge base of potential premises without learning from human proofs. We suggest an exploration mechanism that mixes in additional premises selected by a tf-idf (term frequency-inverse document frequency) based lookup in a d…
LeanDojo removes barriers to theorem proving with open-source tools and data.
problem Difficulty in reproducing and building on existing theorem proving methods.
method Introduces LeanDojo, an open-source Lean playground with toolkits, data, models, and benchmarks.
result ReProver, an LLM-based prover augmented with retrieval, outperforms non-retrieval baselines and GPT-4.
GPT-f uses language models to find new proofs in formal math.
problem Generating original mathematical terms for automated theorem proving.
method Transformer-based language model for automated theorem proving and proof assistant.
result GPT-f contributed new proofs to the Metamath library.
Scalable verifier for recurrent neural networks using polyhedral abstractions.
problem Certifying the correctness of recurrent neural networks.
method Combining sampling, optimization, and Fermat's theorem for polyhedral abstractions; gradient descent for refinement.
result Successfully verified challenging recurrent models in various domains.
Formalizes vNM utility theorem using Lean 4, proving existence and uniqueness.
problem Formalizing and proving the von Neumann-Morgenstern utility theorem.
method Implement classical axioms in Lean 4, formalizing preference relations over lotteries.
result Machine-verified proofs of existence and uniqueness of utility representations.
Transformed geometry into algebra to prove Pick's theorem efficiently.
problem Translating geometric Pick's theorem into formal algebraic proof.
method Formalized geometric Pick's theorem into algebraic proof using Lean.
result Efficient formal proof of Pick's theorem.
Benchmark for math reasoning models from human proofs.
problem Measuring and accelerating machine learning models in high-level mathematical reasoning.
method Built a non-synthetic dataset from theorem prover proofs, defined a task for model to fill in missing propositions, used hierarchical transformer to improve performance.
result Neural models can capture non-trivial mathematical reasoning, hierarchical transformer outperforms baseline.
This paper autoformalizes Euclidean geometry using LLMs and theorem provers.
problem Challenges in formalizing Euclidean geometry due to reliance on diagrams.
method Combines neuro-symbolic framework, SMT solvers, and LLMs to fill in diagrammatic gaps.
result Demonstrates the capability and limitations of LLMs on autoformalizing geometry problems.
Protocol assesses better model among two opaque models with minimal interaction.
problem Learning from two provers, one honest, the other potentially deceptive.
method Formulated and implemented a protocol for assessing better models among two opaque models.
result Protocol achieves near-optimal performance with minimal interaction and query access.
In this article, we introduce rack invariants of oriented Legendrian knots in the 3-dimensional Euclidean space endowed with the standard contact structure, which we call Legendrian racks. These invariants form a generalization of the quandle invariants of knots. These rack invariants do not result in a complete invari…
Paper formalizes multi-dimensional FSD using geometric methods.
problem Complex measure theory and calculus barriers to formalization in proof assistants.
method Geometric framework for first-order stochastic dominance in N dimensions.
result Geometric approach bypasses complex integration theory for direct comparison of survival probabilities.
Lean Copilot uses LLMs to assist theorem proving in Lean, improving efficiency and automation.
problem Challenges in using existing neural theorem provers to prove novel theorems autonomously.
method Introduces Lean Copilot, a framework for integrating LLMs into Lean's theorem proving process.
result Lean Copilot automates 74.2% of proof steps on average, significantly improving over existing methods.
In this paper, we introduce a system called GamePad that can be used to explore the application of machine learning methods to theorem proving in the Coq proof assistant. Interactive theorem provers such as Coq enable users to construct machine-checkable proofs in a step-by-step manner. Hence, they provide an opportuni…
Formalizes integral curves on Banach manifolds in Lean.
problem Existence and uniqueness of integral curves on Banach manifolds.
method Formalized differential equations on Banach spaces, then generalized to Banach manifolds.
result Established theorems for integral curves on Banach manifolds.
This paper presents the first use of graph neural networks (GNNs) for higher-order proof search and demonstrates that GNNs can improve upon state-of-the-art results in this domain. Interactive, higher-order theorem provers allow for the formalization of most mathematical theories and have been shown to pose a significa…
Formal methods verify continuous auctions at exchanges.
problem Ensuring fairness and correctness in continuous auctions.
method Formal specification, design, and verification of continuous double auctions.
result A verified algorithm satisfies natural properties of auctions.
We explore the application of automated reasoning techniques to unknot detection, a classical problem of computational topology. We adopt a two-pronged experimental approach, using a theorem prover to try to establish a positive result (i.e. that a knot is the unknot), whilst simultaneously using a model finder to try …
This paper formalizes Q-learning and linear TD convergence using Lean 4.
problem Formalizing convergence properties of Q-learning and linear TD learning. method Formal verification using Lean 4 theorem prover and Mathlib library.
result Formalized almost sure convergence of Q-learning and linear TD learning. We introduce a formal framework for analyzing trades in financial markets. An exchange is where multiple buyers and sellers participate to trade. These days, all big exchanges use computer algorithms that implement double sided auctions to match buy and sell requests and these algorithms must abide by certain regulator…
Neural symbolic processing aims to combine the generalization of logical learning approaches and the performance of neural networks. The Neural Theorem Proving (NTP) model by Rocktaschel et al (2017) learns embeddings for concepts and performs logical unification. While NTP is promising and effective in predicting fact…
Paper formalizes Simon's satisficing through FFSD, proving its equivalence to expected utility theory.
problem Formalizing Herbert Simon's bounded rationality concept in economic decision-making.
method Developed FFSD framework using Lean 4 theorem prover, proving equivalence to expected utility theory.
result Equivalence theorem linking FFSD to expected utility maximization for approximate indicator functions.
Formally verifies fairness and uniformity in financial market trades.
problem Ensuring fairness and uniformity in automated trading systems.
method Formal definition and verification in Coq proof assistant.
result Properties of double-sided auction mechanisms verified.
INT benchmark tests theorem proving agents' ability to generalize to unseen theorems.
problem Evaluating theorem proving agents' ability to generalize to unseen theorems.
method INT benchmark based on a theorem generation and proof procedure with adjustable knobs for measuring 6 types of generalization.
result MCTS can help agents prove new theorems.
New proof shows local wealth condensation in economic models with biases.
problem Economic models with biases leading to wealth condensation.
method Elementary proof based on properties of wealth distributions.
result Local wealth condensation observed in models with wealth or poverty advantages.
The paper extends collective arbitrage concepts to multi-agent markets with cooperation.
problem Understanding collective market completeness and pricing in multi-agent systems.
method Develops new techniques and theorems to establish collective pricing-hedging duality and collective replication.
result Established a Second Fundamental Theorem of Asset Pricing in cooperative multi-agent settings.
Neuro-symbolic system tackles conversational AI's need for natural, broad-ranging dialogue.
problem Understanding unstated presumptions in conversational AI commands.
method Neuro-symbolic theorem prover for multi-hop reasoning.
result Extracts multi-hop reasoning chains from natural language commands.
This research simplifies verification of machine learning systems using reparameterization.
problem Reduce or eliminate serious bugs in machine learning systems.
method Use proof assistants to construct machine-checked proofs of correctness, leveraging reparameterization to handle probabilistic claims.
result Demonstrates broad applicability of reparameterization to verify different types of machine learning systems.
UD-SGD analysis shows efficient sampling by a few agents can outperform others.
problem Analyzing convergence speed and sampling strategies in UD-SGD.
method Asymptotic analysis of UD-SGD with various communication patterns and sampling strategies.
result Efficient sampling by a few agents can lead to better overall convergence.
New theorems show agents need specific internal structures to perform well under uncertainty.
problem How do agents need to be structured to perform well under uncertainty?
method Proved selection theorems showing strong task performance forces specific internal structures.
result Strong task performance forces world models, belief-like memory, and persistent regime-tracking variables.
This paper extends off-policy reinforcement learning to the multi-agent case in which a set of networked agents communicating with their neighbors according to a time-varying graph collaboratively evaluates and improves a target policy while following a distinct behavior policy. To this end, the paper develops a multi-…
Classical clients can verify quantum learning tasks efficiently.
problem Making quantum learning accessible to classical clients.
method Developed a framework for classical verification of quantum learning.
result Quantum learning tasks can be efficiently verified by classical verifiers.
Generalizes risk sharing models to a continuum of agents.
problem Risk sharing among a large number of heterogeneous agents.
method Modeling agents as points in a measure space, using risk measures on a probability space, and deriving dual representations.
result Explicit formulas for specific risk measures (entropic and expected shortfall) and applications to Pareto efficiency.
Study explores algorithmic collusion in repeated games using various learning dynamics.
problem Understanding algorithmic collusion in repeated games with different learning dynamics.
method Examines Q-learning, gradient learning, and other dynamics in a general repeated game setting. result Characterizes the set of payoff vectors achievable by these dynamics, revealing possibilities for collusion.
Examines optimal risk sharing with realistic risk attitudes, finding risk seeking in certain subdomains.
problem Optimal risk sharing with empirically realistic risk attitudes.
method Allows for risk-seeking agents, generalizes expected utility, and uses counter-monotonic improvement theorem.
result First empirical results on optimal risk sharing with realistic risk attitudes.
We prove the existence of optimal strategies for agents with cumulative prospect theory preferences who trade in a continuous-time illiquid market, transcending known results which pertained only to risk-averse utility maximizers. The arguments exploit an extension of Skorohod's representation theorem for tight sequenc…
Bayesian network approach for efficient cooperative MARL.
problem Leveraging inter-agent coupling information for scalable MARL algorithms.
method Modeling cooperative MARL via Bayesian networks, identifying value dependency sets, proposing P-DTDE paradigm.
result P-DTDE policy gradient estimator has lower total variance than CTDE.
We develop original models to study interacting agents in financial markets and in social networks. Within these models randomness is vital as a form of shock or news that decays with time. Agents learn from their observations and learning ability to interpret news or private information in time-varying networks. Under…
DSAC improves cooperative MARL with general utilities, converging faster than existing methods.
problem Improving cooperation in multi-agent reinforcement learning with nonlinear utilities.
method Decentralized Shadow Reward Actor-Critic (DSAC) that estimates local occupancy measures and derivatives.
result DSAC converges to ε-stationarity in O(1/ε^2.5) steps with high probability, finding globally optimal policies.
The study proves necessary conditions for robust decision-making in uncertain environments.
problem Conditions for robust decision-making in uncertain environments.
method Quantitative selection theorems and binary betting decisions.
result World models, belief-like memory, and persistent variables are necessary for strong task performance.
The paper gives picture of enrichment to economic and financial system analysis using agent-based models as a form of advanced study for financial economic data post-statistical-data analysis and micro-simulation analysis. Theoretical exploration is carried out by using comparisons of some usual financial economy syste…
Transfer learning methods for reinforcement learning (RL) domains facilitate the acquisition of new skills using previously acquired knowledge. The vast majority of existing approaches assume that the agents have the same design, e.g. same shape and action spaces. In this paper we address the problem of transferring pr…
The paper addresses how to complete incomplete risk markets by iteratively enhancing welfare.
problem How to complete incomplete risk markets to enhance welfare.
method Iterative mechanism to complete the market while monotonically enhancing welfare.
result Iterative completion of incomplete risk markets can enhance welfare.
In this communication, some economic models given by functional mappings are addressed. These are models for random markets where agents trade by pairs and exchange their money in a random and conservative way. They display the exponential wealth distribution as asymptotic equilibrium, independently of the effectivenes…