In the North East Atlantic there are several straddling stocks, including herring, mackerel, and blue whiting, which are exploited both within coastal states' 200 nautical mile Exclusive Economic Zones (EEZ) and on the high seas. The pelagic fisheries of the North East Atlantic are all harvested by the same six countries/parties: the EU, Norway, Faroe Islands, Iceland, Russia, and more recently Greenland. For several years, there has been an unsolved dispute between these nations about the size of their respective quotas. Based on their importance and roles in the fisheries, we model the exploitation as consisting of three players, namely the EU, Norway, and Iceland. The optimization model takes into account biological interaction between the species and strategic interaction between the agents simultaneously. It is assumed that when the nations act as singletons, they behave myopically. When they are member of a coalition, they act in order to maximize the coalition’s long-term net revenue. The model is solved using DNLP (Nonlinear Programming with Discontinuous Derivatives), and shows that in most cases the biology (ecosystem) tends to approach a steady state without this being imposed. Internal and external stability conditions, for all possible coalition structures in steady state, are analyzed in order to find out which coalition structures are most likely to occur, with and without side-payments. This is then compared with what we find in the real world, and political implications are discussed.