Motivated by international energy trade between countries with profit-maximizing domestic producers, we analyze Nash games played among Stackelberg games leaders (NASP). We prove it is both $$\Sigma^p_2$$-hard to decide if the game has a pure-strategy (PNE) or a mixed-strategy Nash equilibrium (MNE). We provide a finite algorithm that computes exact MNEs for NASPs when there is at least one or returns a certificate if no MNE exists. To enhance computational speed, we introduce an inner approximation hierarchy that increasingly grows the description of each Stackelberg leader feasible region. Furthermore, we extend the algorithmic framework to retrieve a PNE if one exists specifically. Finally, we provide computational tests on a range of NASPs instances inspired by international energy trades.