This study implements a novel Fuzzy Cognitive Map (FCM) framework for addressing large complex socio-ecological problems. These are characterized as qualitative, dominated by uncertainty, human involvement with different and vague perceptions/expectations, and complex systems dynamics due to feedback relations. The FCM framework provides a participatory soft computing approach to develop consensus solutions. We demonstrate its implementation in a case study: a national-scale acute water scarcity crisis. The model has eight steps starting from collecting data from stakeholders in the form of FCMs (bi-directional graphs) represented by nodes and imprecise connections. All subsequent steps operate within a new fuzzy 2-tuple framework that overcomes previous FCM limitations through advanced processing methods, where large FCMs are fuzzified and analyzed, condensed, and aggregated using graph-theoretic measures. FCMs are simulated as Auto-Associative Neural Networks (AANN) to assess policy solutions to address the problem. In this study, very large cognitive maps were developed through interviews capturing perceptions of five different stakeholder groups taking into consideration the causes, consequences and challenges of the acute water scarcity problem in Jordan. The complex FCMs containing 186 variables comprehensively covered all aspects of water scarcity. FCMs were condensed into smaller maps in two levels. They were also combined into five stakeholder group FCMs and one whole system FCM (total 123 FCMs). AANN simulations of policy scenarios were conducted on the whole system FCM, first at the most condensed level and then moved top-down through the next two levels of granularity to explore potential solutions. These were ranked by a novel fuzzy Appropriateness criterion to provide a number of high level and effective strategies to mitigate the water crisis.