Ferroelectric Compute-in-Memory Framework for Solving Pure and Mixed Strategy Nash Equilibrium

Nash equilibrium (NE) is a key concept in game theory, but verifying its existence is NP-complete. Recent advancements proposed quantum NE solvers that identify pure strategy NE solutions (binary solutions) by integrating slack terms into the objective function, known as slack-quadratic unconstrained binary optimization (S-QUBO). However, S-QUBO alters the objective function and can lead to incorrect solutions. Additionally, current solvers only find a limited number of pure strategy NE solutions and cannot address mixed strategy NE (decimal solutions), leaving many solutions unexplored. In this work, we propose C-Nash, a novel ferroelectric compute-in-memory (CiM) framework capable of efficiently addressing both pure and mixed strategy NE solutions. C-Nash consists of 1) a transformation method that transforms quadratic optimization into a MAX-QUBO form without incorporating additional slack variables, thus avoiding objective function changes; 2) A ferroelectric FET (FeFET) based CiM bi-crossbar structure and winner-takes-all (WTA) tree for accelerating the MAX-QUBO form in a single iteration; 3) An efficient operation flow including a rank-based QUBO reformulation algorithm that simplifies the QUBO matrices to reduce hardware overhead, and a two-phase based simulated annealing (SA) logic for finding NE solutions; 4) A FeFET-based crossbar macro for experimental demonstration. Experimental results show that C-Nash increases the success rate for identifying NE solutions by 68.6% while saving <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3\times $ </tex-math></inline-formula> in chip size. Furthermore, C-Nash can find all pure and mixed NE solutions, unlike D-Wave based quantum approaches which only find some pure strategy NE solutions. Additionally, C-Nash significantly reduces the time-to-solution by up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$157.9\times $ </tex-math></inline-formula>/<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$79.0\times $ </tex-math></inline-formula> compared to D-Wave 2000 Q6 and D-Wave Advantage 4.1, respectively.