Hélène Thiollet

Immigration rentier states

Keywords: migration, state, rentier theory, brokerage, GCC states

Building upon the notion of migration state, this article introduces the concepts of "migration rent" and "immigration rentier states" to describe how states that are heavily reliant upon immigration for their wealth derive unearned income from immigration. Both concepts contribute to better understanding the role of migration in the historical transformation of states, the evolution of political regimes and the relationships between state, market and society both within rentier monarchies and in non-rentier states. Using qualitative and quantitative data, I show that Gulf states and the Saudi Arabian state in particular have progressively governmentalized direct and indirect forms of migration rent through increased migration control and taxation of migrants, both of which were initially brokered by private actors notably through the kafala or sponsorship system. By doing so, states institutionalise labour market segmentation and differential exclusion of immigrants that intersect with class with race, nationality, gender, and age, bringing about what I call a "skill-based order of things". Beyond empirical findings, this article demonstrates the potential for theoretical innovation based in non-Western polities in the social sciences. Rather than outliers or exceptions, the Gulf monarchies offer a magnifying glass that reveals global dynamics of state-led migration control and class-based differential exclusion. Furthermore, this article calls for testing the notions of "migration rent" and "immigration rentier states" across contexts.

Introduction

As sociologist Abdelmalek [START_REF] Sayad | Immigration et "pensée d'État[END_REF] noted decades ago, this article argues that migration politics matter not only to understand migration but also to understand the state since migration politics bear this "secret virtue" of serving as an introduction to the sociology of the state across contexts. Migration politics certainly matter to explain the volume and geographies and outcome of migration flows, as the necessary conditions for migration to occur may be social and economic, the sufficient conditions are political (Hollifield and Faruk 2017, 124;Hollifield 2004, 885). But migration politics are not solely made up of contingent policies: migration is also a central yet over-looked component to understand the role of migration in the historical transformation of states, the evolution of political regimes and of the relationships between state, market, and society. Sayad's call to "re-historicise" the state, finds an echo in this article, in line with subsequent calls to think migration politics beyond western centric perspectives (Thiollet 2020;[START_REF] Natter | Theorising Migration Politics: Do Political Regimes Matter?[END_REF][START_REF] Kathiravelu | Conceptualizing Migration beyond the "West": A View from Asia[END_REF], and disaggregate and decolonise researches on the relationship between states and migration (Adamson, Chung, and Hollifield 2023). I build upon the idea that migration control is a core state function -as Hollifield (2004) theorises for European and Northern American states. I argue that the politics of migration control in the rentier monarchies of the Arab-Persian Gulf also offer a unique vantage point to observe political (trans)formations across time and disaggregate the political economy of the migration state. I argue that migration is central in the socio-political fabric of Gulf states in which resources extracted from oil and foreign labour are channelled through a "broader" social contract (Weiner 1990, 142) 2 between the state, migrants, and citizens. However, rather than considering fixed features of the society-market-state relations which would reify and orientalise Gulf states, I adopt a dynamic approach and historicize these relations. As Charles [START_REF] Tilly | War Making and State Making as Organized Crime[END_REF] argued that Western states progressively turned the fragmented and diffused control over violence and taxation into a state monopoly, I trace the shift from a diffuse societal oversight on foreigners connected to the extraction of a migration rent by nationals at the expenses of migrants to a governmentalized control of migration and of the migration rent. This process of socio-political change entails a profound change in statesociety relations leading to reframe Gulf rentier states as immigration rentier states.

While anchored in a specific context, this research aims to speak to the political sociology of states and the evolution of migration governance more generally, both in the Global North and the Global South. My main contributions to these debates are the following:

First, I introduce the concepts of "migration rent" and "immigration rentier states" to describe rentier states that are heavily reliant upon immigration for their wealth and political stability. In Gulf rentier states, migration control is historically channelled through a combination of private brokerage and direct control by public authorities and citizens extract an income from immigration and immigrants (the migration rent) through the kafala. Overall, I build upon early studies on the rentier social order and migration in the Arab world [START_REF] Saadeddin | Oil, Migration and the New Arab Social Order[END_REF] and more recent research in international relations [START_REF] Freier | Refugee Commodification: The Diffusion of Refugee Rent-Seeking in the Global South[END_REF] to bring the concept of rentier states3 into conversation with debates on the varieties of migration states.

Second, I show that, Gulf states have taken a "sovereign turn" in the management of migration since the 1990s, thus becoming full-fledge migration states. Whereas migration rentierism like oil rentierism use to compensate for the relative weakness of state bureaucracies, the emergence of immigration states in the GCC on the contrary attest to the consolidation of rentier monarchies at the expenses of markets' autonomy and migrants' rights. States increasingly curtail the power and role of informal and formal private intermediaries and governmentalize the migration rent, directly extracting revenue from migrants to feed in the distribution of resource to locals. By doing so they create various direct and indirect forms of migration tax. They also entrench labour market segmentation by legal means and institutionalise the exclusion of foreigners based on class and skills.

Thirdly, I discuss the content and substance of state-led migration politics which increasingly legitimises and institutionalises class-based differential exclusion of foreigners. I introduce the notion of "skill-based order of things" referring to the objective distribution of resources, privileges, and rights as well as the normative preferences and hierarchies between individuals and groups, embedded into subjective representations of the self and others. I focus here on the state-led dynamics while opening future avenues of research on the connection between policies and subjectivities.

Fourthly, these findings may contribute to emerging epistemological debates on comparative research and theorising from non-Western contexts. While migration politics in western democracies attract intense scholarly attention, immigration policies elsewhere are largely under-researched empirically and often side-lined in theory building. This article therefore invites to further research migration politics across political regimes and contexts as democratic states have also increased their control over markets and migrants [START_REF] Hollifield | Immigrants, Markets, and States: The Political Economy of Postwar Europe[END_REF][START_REF] Guiraudon | A Reappraisal of the State Sovereignty Debate: The Case of Migration Control[END_REF] and enforce and legitimise class-based discriminations in mobility and residence rights [START_REF] Shachar | The Race for Talent: Highly Skilled Migrants and Competitive Immigration Regimes[END_REF]. Finally, this research hopes to open venues for exploring the heuristics of the notions of "migration rent" and "immigration rentier states" across contexts.

Case selection and method

This research focuses on the countries that host the world's highest proportion of immigrants in their population; the Gulf, representing only 0.76% of the world's population, contains 11% of the world's migrants (UNDESA 2019). Despite these numbers, proportions, and continuous trends of mass migration, the six oil-rich monarchies of the Gulf Cooperation Council (GCC), 4 are overlooked or side-lined although migrants represent the majority of inhabitants in the region. One of the reasons for neglecting or exceptionalising migration politics in Gulf states is that demography and labour demand are overdetermining flows. Overall, scholars refer to "open door" policies [START_REF] Fasano | GCC Countries: From Oil Dependence to Diversification[END_REF]de Bel-Air 2018), "liberal and nonselective" policies (Winckler 1997, 484), or "laissez-faire" [START_REF] Richards | The Laissez-Faire Approach to International Labor Migration: The Case of the Arab Middle East[END_REF]. Scholars and policy-makers alike notably emphasise demographic determinism [START_REF] Fargues | Migration to the Gulf States: The Political Economy of Exceptionalism[END_REF] and the role played by private actors -transnational recruitment companies, migration brokers, and the kafala or sponsorship system (ILO 2014, 15)-at the expenses of states. A second reason is the fact that immigrants are presented as "temporary workers" rather than full-fledge immigrants: they are maintained in situations of "precarious non-citizenship" (Goldring and Landolt 2013) even when they settle for decades with their families [START_REF] Thiollet | Nationalisme d'Etat et nationalisme ordinaire en Arabie Saoudite : la nation saoudienne et ses immigrés [State nationalism and banal nationalism in Saudi Arabia: the Saudi nation and its immigrants[END_REF][START_REF] Rahman | Emigration and the Family Economy: Bangladeshi Labor Migration to Saudi Arabia[END_REF][START_REF] Lori | Temporary Workers or Permanent Migrants? The Kafala System and Contestations over Residency in the Arab Gulf States[END_REF]Vora 2013;Assaf 2017). A third reason to exoticise migration politics and the role of the state in the Gulf contexts, is the supposed exceptional nature of Gulf rentier state and Gulf polities which I discuss at length below. Contrary to such depoliticised or exoticised accounts, I build upon the political sociology of rentier states and bring the Gulf (back) in comparative discussions on the migration state in Asia [START_REF] Chung | The Developmental Migration State[END_REF], Canada [START_REF] Triadafilopoulos | The Domestic Politics of Selective Permeability: Disaggregating the Canadian Migration State[END_REF], across imperial and (post)colonial divides (Adamson 2023;[START_REF] Klotz | Imperial Migration States[END_REF][START_REF] Sadiq | Labor Coercion and Commodification: From the British Empire to Postcolonial Migration States[END_REF] and across regime types [START_REF] Natter | The Il/Liberal Paradox: Conceptualizing Trade-Offs in Immigration Reform across the Democracy/Autocracy Divide[END_REF]. I therefore contend that rather than being peripheral or marginal, Gulf monarchies can play a central role in theorising of migration politics and understanding of the political sociology of migration states.

Immigration to the Gulf region is in fact, not recent and builds upon a long history of migration politics which builds upon pre-colonial, colonial, and post-colonial histories as well as regional and inter-regional dynamics. 5 This article however focuses on the early twenty-first century and offers a recent historicisation of the evolution of migration politics. In the 2000s and 2010s, high oil prices and diversifying economies produced another "oil boom" and another "migration boom", thus echoing the events of 1973. Coincidentally, more foreigners arrived than ever before, with greater numbers from South Asia, whereas Arab migrants had previously been more numerous.

Although official statistical information is not always publicly available, the proportions of non-nationals in Gulf societies today range from 38% in Saudi Arabia and Oman to 88% or 89% in Qatar and the UAE (Table 1). Overall, 51% of residents in the region are non-nationals. Situations across Gulf countries vary from high (Bahrain, Oman, Saudi Arabia) to very high proportions of immigrants (Kuwait, Qatar, the UAE). We thus distinguish two groups of immigration states using the proportion of immigrants in their population (and therefore their dependence upon immigration): Kuwait, Qatar, and the UAE as extreme immigration rentier states (white in in Table 1), and Bahrain, Oman, and Saudi Arabia as middling immigration rentier states (light grey in Table 1). 6 Yet we note that the overall proportion of immigrants in the GCC has increased steadily. During the "boom", the UAE experienced a substantial increase in immigration flows relative to its population, with an overwhelming majority of South Asian immigrants. Oman, Saudi Arabia, and Bahrain received fewer immigrants relative to their population, and from more diverse origins. Some countries organised mass deportations of immigrants from selected nationalities: in Saudi Arabia, Yemenis were deported en masse from 2013 onwards. Considering the commonalities and differences between Gulf monarchies, this article offers an empirical focus on Saudi Arabia -the largest country in the region, with the largest absolute number of immigrants -where ten years of ethnographic fieldwork were conducted. This research proceeds inductively, relying upon primary and secondary sources in English and Arabic for all six GCC countries. I use demographic data, media, and policy sources, alongside interviews with Saudi officials. To complement the picture given by governmental sources, and to explore the relations between public policies and private actors, I also use semistructured interviews with migrants' employers and recruiters, as well as with immigrants in Saudi Arabia from various origins between 2006 and 2017. This catch-all approach is adapted to the research challenges encountered.

In the following sections of the article, I first describe the political sociology of migration politics in the Gulf and introduce the concept of the "immigration rentier state." I then analyse the political changes undertaken by the Saudi monarchy to better control immigration flows and immigrants, notably through reforms to the labour market and systems of migration intermediation, kafala. The last section discusses the substance of migration politics adopted and zooms in on the institutionalisation of class-based differential exclusion against migrants.

From rentier states to immigration rentier states

The "rentier state", coined in 1970 and developed in the 1980s, refers to how states developed in contexts of economic dependence upon natural resources. Overall, rentierism is often presented as a pathology of developing states (a "resource curse" or "Dutch disease")7 plagued by clientelism or patrimonialism, bureaucratic inefficiency, structural weakness, and corruption. Yet recent analysis of GCC states suggests in a more value-neutral way that they may be "defying" the resource curse, proving economically successful (Hertog 2010a) and politically resilient. However, scholarship revisiting rentier theories has so far focused on rent distribution from monarchs to their subjects, assuming that foreigners are excluded from the rentier social contract and overlooking the centrality of migration in Gulf rentier states. 8Rentier states distribute to their population a national income determined abroad on oil markets [START_REF] Mahdavy | Migration Diplomacy in the Gulf -Non-State Actors, Cross-Border Mobility, and the United Arab Emirates[END_REF]Beblawi 1987). They are welfare states of a specific kind since they distribute externally priced revenue through public employment and public services without taxing their population creating a form of "wage of oil" for nationals [START_REF] Herb | The Wages of Oil: Parliaments and Economic Development in Kuwait and the UAE: Michael Herb[END_REF]. Welfare distribution in rentier states is mediated through kinship (tribes and extended family, or 'a'ila) or trading elites, creating "multilayers of rentiers" (Beblawi 1987, 386). Welfare brokerage is generally seen as reserved to locals but in fact brokers who "hold privileged positions […] can make resources available to nationals and foreigners [emphasis by the author] who are not as well connected" (Hertog 2010b, 283). Both nationals and migrants are dependent upon the wasta (dialectal pronunciation of wasita

و ا ﺳ ِ ط ﺔ
, meaning mediation, intercession, and recommendation, with a colloquial undertone) of someone in a position to help them. Their access depends upon their nationality, as well as other intersectional characteristics among which most notably class, gender, ethnicity, and religion. Access also depends upon sociological trajectories, duration of stay and social connections across migrants' and locals' social networks. However, while foreigners are embedded in a hierarchical rentier brokerage system, the political sociology of immigration rentier state is a compound of both rentier brokerage and migration brokerage which leads me to introduce the notion of migration rent.

States, brokers, and migrants

The concept of "migration rent" (Thiollet 2022a;2022b) to describe how migration brokers extract an income from immigration as a process (flows), from immigrants' residence and labour. Gulf Migration brokers are part of multiple layers of intermediaries who mediate access to resources, both material and symbolic, which are ultimately controlled by autocrats and ruling families. Although the notion could be tested in other contexts, in the Gulf context is formally connected to citizenship and linked to the oil rent which drives Gulf economies despite their diversification. The migration rent is extracted by intermediaries or migration brokers (recruitment companies, employers, individual sponsors) who are generally nationals or subjects of local monarchs but who also may be other well-connected foreigners. The migration rent thus concerns all forms of resources extracted specifically from peddling citizenship privileges to migrants.

Migration rent extraction has historically relied upon the kafala9 which turns locals into "migration rentiers" (Thiollet 2022b(Thiollet , 1649) ) or "citizen sponsors" (Lori 2019). The kafala is in fact a loosely regulated institution that obliges every foreigner wishing to work, reside, or invest in the host country to be sponsored by a local sponsor (kafil, plural kufala'), in exchange for a fee. The kafil is implicated in all administrative processes between the state and migrants. A kafil can be a person or a company, he can be the same person or company as the migrant's employer or a different one (a recruitment company or an individual). Although having a work permit is legally mandatory to enter GCC countries, the kafala adds an extra fee and condition to all state-issued documents (visa, residence or exit permit etc.), to employer-provided work contracts and work permits, and "no-objection letters" needed by workers to leave their employers and get a new job than the one they entered the Gulf for. 10Formally, the kafala therefore delegate state-led migration control to private actors (see Figure 1). Both inherited from colonial rules (Al-Shehabi 2019; Adamson, Tsourapas, and Thiollet 2018) and embedded in religious and civil law in the GCC [START_REF] Hassan | Al-kafala: dirasa muqarana bayn al-qanun almadanı wa al-fiqh al-islami [The kafala: comparative study between civil and Islamic law[END_REF]), it is central element in migration policy-making [START_REF] Lori | Temporary Workers or Permanent Migrants? The Kafala System and Contestations over Residency in the Arab Gulf States[END_REF]Beaugrand 2018;Malit and Tsourapas 2021) and a structural component of the social contract in the immigration rentier state. In practice, the kafala generates a variety of informal practices and operates in grey zones vis-à-vis the states, and in between states and markets. Kufala' open letterbox companies to allow migrants to open businesses. A citizen and his firm are recorded as the owner of a small business (restaurant, small grocery or telephone shop, beauty salon, etc.) that is in fact owned and run by a migrant. They also serve as a legal ground for "shadow employment" when a migrant is then employed to "do the job" of a local in public administration.

The most visible and controversial role of the kafala in informal migration management is the direct sell entrance and exit so-called "free visas" (entry visas without an actual work permit/employment connected to them). Brokers acquire visas to bring in foreign workerssometimes in large numbers through so-called block visas -who do not have an actual job in the destination country. The "free visa" market is semi-formal, and its degree of illegality depends upon local legislation and the status of the broker-sponsor, but it by-passes the legal requirement to have an actual work contract before entering the Gulf. Sponsors may also illegally extort additional rents from migrants (a practice condemned by rights activists and academics alike) by extracting a share of workers' salaries, demanding exceptional sums for trivial administrative processes such as registering a child on their parents' residence permit (iqama), or withholding a worker's passport [START_REF] Gardner | A Portrait of Low-Income Migrants in Contemporary Qatar[END_REF]. At the peak of the second migration boom, Hertog (2010b, 299) estimated that "free visa" workers represented one third of the entire GCC labour force, and that the free visa business alone generated an income of $1.5 billion annually for the GCC.

Formal and (mostly) semi-informal migration brokerage generate an extremely large income from in the Gulf is considered to be unmatched across the world (Hertog 2010b, 297, 300). Investigations aimed at identifying the sale of "free visas" or use of "letterbox" companies in Bahrain (2008) and Saudi Arabia (2013[START_REF] Rizvi | Will UAE Apply VAT on Expat Remittances?[END_REF] revealed that half of local companies were in fact just fronts channelling imported labour, and that a half of workers in the UAE were on "free visas" in the 2000s.

The case of free visas illustrate that changing policies may change the meaning of brokerage and power relations between actors as Gulf governments seek to modernise and consolidate their authority over the population -nationals and immigrants alike. Referring again to state-making and extraction processes observed by Tilly (1985, 80), it contributes to "produc[ing] durable instruments of surveillance and control within the territory […] [and] br[inging] the fiscal and accounting structures into being."

The following sections explore the empirical manifestations of the sovereign turn that has re-shaped Gulf immigration rentier states from the 2000s onwards.

Migration Control as State (Trans)Formation

Since the 1990s, migration issues have become increasingly politicised worldwide. In the 1990s, immigration came to be constructed and framed in public discourses and policies, not as a resource, but as a problem, as a cultural and demographic threat for destination countries (Castles 2010;Weiner 1995) and as a "crisis" [START_REF] Cantat | Migration as Crisis[END_REF]). In the Gulf as well, migration was progressively politicised through the 1990s and 2000s.

In 2004, a Gulf-based think tank mentioned the population problem/imbalance -"alkhalal a-l-sukanî" (

ا ﻟ ﺨ ﻠ ﻞ ا ﻟ ﺴ ﻜ ﺎ ﻧ ﻲ
) -as one of the main challenges for radical reforms in the GCC (Al-Kuwari 2004). In 2013 the think tank devoted the entire report to the population problem (Al-Shehabi and Gulf Development Forum 2014). Scholars and Gulf governments alike highlight the policy challenge arising from the "demographic imbalance" (Fargues and de Bel-Air 2015; Mansour 2016). Thiollet (2022bThiollet ( , 1649-53) -53) has shown, for Saudi Arabia, how political elites and state-controlled media conjointly contributed to this politicisation, leading to the rise of a public issue and constitution of a domain of public policy. Remittances have also started to become a subject of state concern and public discourse. In 2019, lawmakers in Kuwait called for taxation of migrants' remittances (Kuwait Times 2019), whereas Oman rejected the idea in 2016 (Times of Oman 2016).

The politicisation of immigration and its financial corollaries has its roots in the Gulf war of 1991, when large number of foreigners left Kuwait under threat of the Iraqi invasion, and other GCC countries in fear of a regional security crisis. These departures exposed the dependence of Gulf labour markets and economies. Structural dynamics also drove migration to the forefront of public discourse and policies. A regional demographic youth bulge and rising levels of education have put a growing number of educated young people on the labour market with little chance of finding a job matching their income expectations. Youth and female unemployment -although underreported -is a topic of public concern (Forstenlechner and Rutledge 2011, 28).

In this context, migration has become a structural concern for policymakers. They increasingly sought to control labour market segmentation between nationals and migrants, and between migrants of different classes and origins. They have also targeted migration intermediation in transnational recruitment and domestic sponsorship. More generally, the series of reforms initiated in the 1990s and consolidated in the 2000s and 2010s have governmentalised the collection and distribution of migration rent creating indirect forms of taxation of immigration for businesses and direct "expat levy". This sovereign turn, partly cloaked in neoliberal modernisation discourses (Thiollet 2022b(Thiollet , 1655)), has bolstered the direct intervention of immigration states in migration control.

Policing migration brokerage at home and abroad

International recruitment of migrant workers reached large proportions in the 1980s across sectors as Gulf economies diversified. Configurations of migration brokerage changed and, as noted above, informal practices proliferated (Baldwin-Edwards 2011): in the booming construction sector, low-paid construction workers were mostly contracted by "labour supply" or "manpower" companies, which became their kufala' across GCC states and "sold" them to construction projects or the service industry to fill short-term labour demands (The Five Corridors Project 2021, 7). Changing standards of living also generated massive demand for domestic workers. Domestic workers were either recruited by small-scale occasional sponsors or through "mass" sponsors -either members of influential families or letterbox companies trading in "free visas" and "re-selling" workers to employers upon arrival. In all cases, sponsors used their national privilege to extract a rent from domestic workers, either as an initial payment or a debt reimbursed from their income.

While intermediation in the oil and service sectors was rather formal, new sectors of the economy were loosely regulated, creating new informal revenues for new brokers. Migration rent increased in the 1980s and 1990s, with the cost of informal brokerage practices mainly being borne by migrants. It also created possibilities for mass exploitation of low-skilled workers, and became a source of abuse and quasi-slave labour conditions for migrant workers [START_REF] Longva | Keeping Migrant Workers in Check: The Kafala System in the Gulf[END_REF]Human Rights Watch 2010;[START_REF] Herb | The Wages of Oil: Parliaments and Economic Development in Kuwait and the UAE: Michael Herb[END_REF][START_REF] Parreñas | The Governance of the Kafala System and the Punitive Control of Migrant Domestic Workers[END_REF]. However, the kafala also allowed for migrants' mobility and some interstitial agency pending the granting of approval and remuneration by their kafil: for example, workers could play off their kafil against their bosses, or use their kafil to circumvent legal restrictions against family reunions [START_REF] Thiollet | Nationalisme d'Etat et nationalisme ordinaire en Arabie Saoudite : la nation saoudienne et ses immigrés [State nationalism and banal nationalism in Saudi Arabia: the Saudi nation and its immigrants[END_REF]Assaf 2017;[START_REF] Thiollet | Cosmopolitanism in Exclusionary Contexts[END_REF]). An Eritrean woman who had arrived in Riyadh in the 1990s to work as a maid explained that her employer-kafil obtained visas for her children and relatives. After leaving her first job, she became a nurse on a "free visa" and her former employer-kafil continued to support her iqama and that of her now adult children and relatives. 11In the 2000s, labour market reforms and policies formally aimed to bring the kafala under state control and regulate the recruitment of foreign workers, reducing and even eradicating "free visas" and other semi-informal practices. Governments were incentivised by international pressure in favour of migrants' rights, but mostly sought to redress power relations between states and brokers. They curbed sponsors' prerogatives over "visa trading" and migrants' professional mobility. Yet a question remained as to who would pay the costs of brokerage and where would migration rent would come from.

In Bahrain, kafala prerogatives were transferred to a state agency. King Hamad bin Issa al-Khalifa created the Labour Market Regulatory Authority (LMRA) in 2006 to strengthen government control over labour migration and replace sponsors; the kafala was "formally" dismantled in 2009. The LMRA reintroduced control over labour mobility and residence rights in 2011, and imposed fees on job changes and work permits (Labour Market Regulatory Authority 2016). It became the sponsor of all immigrants, assuming the functions previously performed by individuals, recruiters, or employers. Constraints on job changes were loosened in Kuwait in 2009 and 2011. In Qatar, several attempts to abolish the system were unsuccessful, only textually replacing "sponsors" with "recruiters" in 2016, then finally lifting the need for employer authorisation to leave the country (exit visas) in 2018, and extending the measure to domestic workers in 2019. 12 Yet the Qatari monarchy failed to entirely abolish the kafala owing to high resistance from locals [START_REF] Diop | Reform of the Kafāla System: A Survey Experiment from Qatar[END_REF]. In Saudi Arabia, multiple attempts to reduce the prerogatives of kufala' and criminalise "letterbox companies" were introduced (Thiollet 2022b). In 2021, a "landmark" reform set out to "revamp" the kafala (moving most administrative procedures online) rather than abolishing it (Saudi Gazette 2021). This echoes a broader trend across the GCC: most processes of visa registration and labour permits are now electronically operated, 13 which modernises state control and surveillance over both migrants and brokers, without enhancing the protection or emancipation of migrants.

Representatives of Saudi chambers of commerce involved in policy dialogues with the Ministry of Labour about labour market reforms through the 2010s insisted that the on-going reforms had actually de facto abolished the kafala since 2014: They referred to Cabinet Decision No. 166 (9 October 2000), which grants migrant workers a right to geographical mobility within the country, through the right to retain their passport and the passports of their family, and to move freely within the Kingdom if they hold a valid iqama. But one added:

Reforming the kafala was used to get rid of practices that allow migrants to escape its direct control and to better regulate the private sector. 14 Paradoxically, policymakers and businessmen alike note that, in practice, labour market reforms, anti-kafala reforms, and nationalisation constraints led to higher recruitment costs and less labour market flexibility. Such rigidity increased illegal practices, which were in turn repressed by public campaigns targeting migrants in irregular situations and firms operating in grey zones and trading visas. Employers continued to hire sponsored workers without work contracts, especially unskilled workers in SMEs. Consequently, nationalisation and anti-kafala reforms generated more "free visas" than before. In Bahrain, as the government realised this 12 Workers still had to ask their employer to "leave". Non-payment of wages as well as abuses remain numerous, despite increased fines and penalties for employers. 13 The Absher and Qiwa online platforms in Saudi Arabia are used to register expatriate workers in private sector establishments. These exclude domestic workers. 14 Interview, Jeddah, 2015. unexpected outcome, the LRMA introduced the "Flexi Permit" between 2017 and 2022. It allowed migrants who terminated their initial work contract to regularise their status by sponsoring themselves without leaving and to work legally for multiple employers. Such framework offered legal "free visas". 15 Flexi Permit fees increased massively in 2019 16 because of the opposition of Bahrain Chamber of Commerce.

Beyond the kafala itself, the entire recruitment sector came under stronger control by Gulf states and the entire sector was restructured. Reforms sought to regulate recruitment and visa issuance, control firms, evict "letterbox companies" from the migration industry, and potentially transfer the cost of recruitment fees from migrants to employers, as advocated by international organisations.

In the early 2000s, Qatar banned "recruitment fees" imposed on migrants, 17 but subsequent studies showed that recruitment costs continued to be extracted from migrants though various informal means and wage cuts. In 2013, the Saudi government issued a new law regulating high volume recruitment activities: ten prominent "mega-firms" received a state license. A similar state control over recruitment agencies and licensing also occurred in countries of origin, including India and the Philippines (POEA 2018). According to public officials with the Ministry of Labour, the licensing system aimed to "clean up" the recruitment sector, 18 and make the industry formally state-dependent. The CEO of a large recruitment firm interviewed in 2013 and 2015 19 explained that his business was among the first recipients of licenses because he was well-connected (wasta) within both business and political circles. His company specialises in "importing" low-skilled migrants, including domestic and construction workers, yet his ambition was to open new business ventures in high-skilled sectors. He emphasised the ever-growing government control over the transnational recruitment business, through structural changes and licensing, but also through new regulations and administrative processes that frame recruitment activities. Yet he explained that the reforms also allowed his firm to legally import migrant workers, and notably domestic workers, in large numbers before finding them actual employers. The novelty was the ability of the recruitment company to become the direct employer of domestic workers and subcontract them to employers on an hourly basis. He argued that moving away from the model of home-based domestic workers tied to their individual employer, towards a model in which hourly-paid workers are recruited and employed through his company in a legal way, is part of a larger modernisation process in the Saudi economy and society. Yet when asked about the kafala and its place in this modernisation, he said:

Kafala is good for the worker. Otherwise, you need to go to immigration [the offices of the Ministry of Interior], do everything by yourself: find a house, apply for your iqama, buy your taxi if you are a taxi driver […]. If you are a 15 Source: https://lmra.bh/portal/en/page/show/325 16 Source : https://www.migrant-rights.org/2020/02/a-closer-look-at-the-flexi-permit-two-years-on/ 17 Source: ILO https://www.ilo.org/wcmsp5/groups/public/---ed_protect/---protrav/---ilo_aids/documents/legaldocument/wcms_125871.pdf 18 Interviews, Ministry of Labour, Riyadh, 2015. 19 Interview, Riyadh, 2015. kafil, you must do all this. We do all this for them [the migrant workers recruited by the company] and now it's well organised, legal and transparent. 20The number of licensed recruitment companies rapidly grew, becoming the official channel of a previously informal visa-trading industry. Rather than abolishing migration rent, reforms seem to have channelled it through state bureaucracies and agencies, empowering the state in the public-private governance of migration.

Governmentalising migration rent: labour market segmentation and the expat levy

Labour market segmentation and wage discrimination, both between nationals and migrants and between migrants of different categories, is common across contexts [START_REF] Portes | The New Second Generation: Segmented Assimilation and Its Variants[END_REF]). Yet, in the GGC, levels of segmentation between foreigners and nationals are exceptionally high, and political interventions in the labour market and wages have become institutionalised.

Since the colonial era, rentier states have distributed the dividends of oil wealth and bought their subjects' loyalty through large public spending on public infrastructure, social and welfare benefits, and direct cash transfers (which exclude non-nationals from the trickling down of the rent through the welfare state). Labour policies are also central to rent redistribution, as they institutionalise a dual labour market. Historically, local rulers secured employment for locals in the nascent oil industry through "nationality clauses" in oil and gas concession agreements with foreign firms. Quotas of local workers were imposed, but mostly related to subaltern positions. As state apparatuses were consolidated, public employment became the primary form of rent distribution in state bureaucracies, which consequently became known for low productivity and over-staffing. Rentier states became, and remain, the "major and ultimate employer" of nationals "matched only by socialist-oriented states" (Beblawi 1987, 388).

As a result, Gulf labour markets today are segmented along nationality and public/private lines,21 as shown in Table 2. The public sector (including state-owned oil companies) massively employs nationals, while the private sector is overwhelmingly staffed by foreign workers. Nationals work in the public sector with better salaries, benefits, and incentives than those received by immigrants working in the private sector [START_REF] Schubert | Wage Subsidies Offer Key to Nationalisation[END_REF]. Extreme immigration rentier states are even more dependent on foreign labour in the private sector, while they too primarily employ nationals in the public sectors (Kuwait and the UAE). In Qatar, however, only 1% of nationals work in the private sector, and the small number of nationals does not suffice to staff the public sector. Countries with a larger population, such as Saudi Arabia, have almost entirely evicted foreigners from public jobs. Since the 1990s, concerns about the saturation of the public sector have increased, alongside concerns about rising unemployment among young Saudis, Kuwaitis, Emiratis etc. (Al-Kuwari 2004;'Arishi 2015). Unemployment benefits, exclusively for nationals, were introduced in most GCC countries in the 2000s. They notably profited Gulf women, who are mostly outside the labour force, thereby creating a new vector of rent distribution. In this context, as in Western advanced economies, labour market and immigration reforms tend to link nationals' employment to immigration control. In the Gulf, however, demand for migrant workers remains high and immigration increased in the 2000s, but governments balanced an increase in rentier benefits for working nationals with an increased "expat levy".

"Nationalisation" policies across the six monarchies have sought to increase the number of locals in the private sector. While nationalisation policies based on never-attained quotas largely failed (Hertog 2014), new programs -such as the Nitaqat program launched in Saudi Arabia in 2011 -combined penalties with incentives. These notably increased wages for nationals through discriminatory minimum wage law and introduced wage subsidies, while trying to increase the cost of migrant labour for firms.

Kuwait started subsidising nationals in the private sector in 2001 and increased subsidies until the Covid-19 economic downturn. In 2014, Saudi Arabia's "Payroll Rebate" policy paid employers to supplement wages for nationals for firms that hired enough Saudis according to Nitaqat requirements. In the UAE, the Nafis program was launched in 2021 to boost private sector employment of nationals with wage subsidies. It was extended in 2022 with top-ups transferred directly to highly-skilled nationals [START_REF] Salim | New Emiratisation Rule in UAE: Fines, Discounts, Benefits Explained[END_REF]. In most contexts, however, wage subsidies created new forms of "shadow" or "ghost" employment involving migrant workers. Subsidies have become almost a structural feature of private sector employment, and wage subsidies effectively institutionalised the extension of the rentier state into the private sector. While such policies are costly and ineffective economically, their political rationale is clear: in the context of the Arab spring, governments feared the risk of having large groups of young, educated, idle subjects ready to take part in protest, and sought ways to reinforce their authority.

In the past decades, states also gradually increased the cost of migration thus increased the direct and indirect taxation on migrant workers and their families (Thiollet 2022b). Penalties for firms and employers failing to comply with nationalisation policies started to be more strictly implemented. Saudi Arabia introduced such penalties for non-compliance with Nitaqat requirements in 2013, and again in 2018. Similarly, fines were introduced in the UAE in August 2022, to be implemented in 2023.

The taxation of migrants' remittances provides a new fiscal resource and means of extracting migrants' income. After intense parliamentary debates, Kuwait introduced a tax on migrants' remittances in 2018 (Kuwait Times 2018). The UAE introduced a value-added tax in 2018 targeting remittance services and fees charged by money transfer companies [START_REF] Rizvi | Will UAE Apply VAT on Expat Remittances?[END_REF]. In 2018, Bahrain proposed to impose fees on remittances alongside a special car-owning tax rate for migrants (twice the rate charged to nationals), but the Bahraini government eventually rejected it.

GCC states raised the fees for residence permits (iqama) and changes to work permits or sponsors. In December 2019, Kuwait introduced fees ranging from KD1 to 10 (€3 to 32) for seven migration-related services, such as renewing a residence permit, cancelling a work permit or status certificate, etc. In Saudi Arabia, the fees for issuing iqama and other administrative procedures were increased within the Nitaqat, with work permits costing SR800 (€212)22 per month in 2022.Shifting from annual to monthly payment created a new direct relation between migrants and state administrations, even if it remained virtual.

In 2017, Saudi Arabia introduced the "family tax", or "dependent tax", through the Ministry of Interior. This flat tax starts at 100 riyals (€26) per month for every minor or unemployed relative of a private sector foreign worker and increases every year. Kuwait followed in 2019 with a tax on immigrants' dependents who are family members, depending upon a migrant worker's residence permit. The Saudi tax became known as the "expat levy" across the region and became symbolic of the new state-managed migration rent. While the actual resources extracted directly by state agencies remain limited, they signal the formal grip of states over both migrants and businesses.

States and migrants: class-based differential exclusion and the skillbased order of things

This final section discusses the emergence of regimes of class-based "differential inclusion" [START_REF] Castles | How Nation-states Respond to Immigration and Ethnic Diversity[END_REF][START_REF] Könönen | Differential Inclusion of Non-Citizens in a Universalistic Welfare State[END_REF]) in the Gulf. It shows the growing role of states in crafting these regimes in contexts where formal inclusion and naturalisation is very limited.

Goldring and Landolt (2013) identify three factors shaping the trajectories leading to formal "inclusion" for migrants of precarious legal status: institutionalised social hierarchies, everyday social dynamics, and policies. On the first factor, past research has emphasised the role of non-state factors, including the kafala, in shaping migrants' lives through institutionalised social hierarchies based on class, ethnicity and gender (Alloul 2021a;[START_REF] Walsh | A Globalising Gulf Region and the British in Dubai[END_REF][START_REF] Longuenesse | Rapports de Classe, Solidarités Communautaires et Identité Nationale Dans Les Pays Du Golfe' [Class Relations, Communal Solidarities and National Identity in the Gulf States. The Case of Migrant Workers[END_REF][START_REF] Hanieh | Capitalism and Class in the Gulf Arab States[END_REF]Vora 2013), and imposing the "structural dependence" [START_REF] Longva | Keeping Migrant Workers in Check: The Kafala System in the Gulf[END_REF]) of migrants upon their local sponsors through generalised brokerage between migrants and non-migrants, between migrants of different categories, and between nationals [START_REF] Jaber | Mondes En Mouvement. Migrants Au Moyen-Orient Au Tournant Du XXIe Siècle[END_REF][START_REF] Thiollet | Nationalisme d'Etat et nationalisme ordinaire en Arabie Saoudite : la nation saoudienne et ses immigrés [State nationalism and banal nationalism in Saudi Arabia: the Saudi nation and its immigrants[END_REF][START_REF] Vora | Everyday Inclusions: Rethinking Ethnocracy, Kafala, and Belonging in the Arabian Peninsula[END_REF]Lori 2019). Regarding the second factor, everyday social dynamics also determine segregation or inclusion: everyday xenophobia reinforces discrimination in public places (Bristol-Rhys 2012) and creates the conditions for abuses [START_REF] Jureidini | Migrant Workers and Xenophobia in the Middle East'. 2. UNRISD Programme Papers on Identities, Conflict and Cohesion[END_REF]. Recruiters, employers, real estate agents, and other social gate keepers -who may themselves be migrants -enforce a hierarchical and sometimes discriminatory social order. Conversely, cosmopolitan dynamics in everyday experiences in Gulf cities allow for some degree of informal integration for foreigners [START_REF] Thiollet | Cosmopolitanism in Exclusionary Contexts[END_REF], and particularly second generation immigrants [START_REF] Thiollet | Nationalisme d'Etat et nationalisme ordinaire en Arabie Saoudite : la nation saoudienne et ses immigrés [State nationalism and banal nationalism in Saudi Arabia: the Saudi nation and its immigrants[END_REF][START_REF] Vora | Everyday Inclusions: Rethinking Ethnocracy, Kafala, and Belonging in the Arabian Peninsula[END_REF]. Migrants navigate constraints and opportunities, drawing on their social capital and connections.

Yet in past decades, policies, the third and last facto identified by Goldring and Landolt have become more important in shaping migrants' lives. Immigration rentier states have increasingly formalised regimes of differential exclusion based on social classes in two domains: residence and labour. These two domains are emblematic of a broader framework of class-based migration policies that peg rights to skill-level.

I call these logics the "skill-based order of things", echoing Liisa Malkki's (1995) "national order of things." The notion of skill-based order of things describes how skills function as a proxy for class, or even castes in state-institutionalised discriminations. Such order both refers to the objective distribution of resources, privileges, and rights but also to the normative preferences and hierarchies between individuals and groups, embedded into subjective representations of the self and others. The skill-based order of things produces local hierarchal social orders across Gulf states as Natasha Iskander (2021) explores these logics through the case of construction workers in Qatar. It is also global, in the form of class-based discrimination enforced through the global quest for in-demand skills which is often marketed under seemingly value-neutral labels like the "race for talents" [START_REF] Shachar | The Race for Talent: Highly Skilled Migrants and Competitive Immigration Regimes[END_REF]. While Assaf (2017) and Alloul (2021b) have explored migrants' and non-migrants subjectivities, I focus here on the role of states in formalising and legitimising the allocation of labour rights, residence, and citizenship rights according to wealth and capital.

▪ Residence rights and family reunion

In the 2000s, Gulf states shifted from a regime of formal exclusion of all migrants to a formal regime of class-based access to residence rights and family reunion, which strictly limits the duration of stay of unskilled foreigners while granting long term residence to the wealthiest. While some had previously been able to access long-term residence and, in exceptional cases, naturalisation thanks to wasta, new laws institutionalised the allocation of visa privileges and residence rights, supposedly based on workers' "skills", but essentially based on economic wealth. Such laws gradually emerged from debates around the demographic imbalance and the presence of long-term foreign residents and second generations of migrants [START_REF] Thiollet | Nationalisme d'Etat et nationalisme ordinaire en Arabie Saoudite : la nation saoudienne et ses immigrés [State nationalism and banal nationalism in Saudi Arabia: the Saudi nation and its immigrants[END_REF]Vora 2013;Assaf 2017). They institutionalised existing social and economic inequalities, and the tiering of citizenship and residency [START_REF] Jamal | The "Tiering" of Citizenship and Residency and the "Hierarchization" of Migrant Communities: The United Arab Emirates in Historical Context[END_REF].

Kuwait has limited family reunion based on workers' income since 1992 (Government of Kuwait 1992) and has discussed limiting the duration of stay of immigrants since the 1980s.

The UAE imposed a six-year limit on duration of stay for all migrants, which exempts wealthy expatriates who own real estate or invest in the Emirates. Long-term visas and residence rights (five or ten years) became accessible in February 2019 for specific categories of highly-skilled professionals and their families without sponsors (GDRFA 2019). Family reunion is only open to wealthy immigrants: men earning more than 4,000 dirhams per month (or 3,000 dirhams plus accommodation) and women earning more than 10,000 dirhams per month (or 8,000 dirhams plus accommodation), and, in Abu Dhabi, those working as an engineer, teacher, doctor, or in the medical sector.

In 2022 Bahrain introduced a "Golden Residency Visa," a permanent residency visa for migrants who have resided in Bahrain for at least five years and earned an average salary of at least BHD 2000 ($5,306) per month, those who own properties above a certain value, retirees, and "highly talented" individuals.

In 2015 Saudi Arabia introduced legal class-based discrimination in residence rights through a royal decree that specified an eight-year residence cap for unskilled workers. Adding to the effect of the decree, the flat fee charged for the residence of dependents, introduced in 2017, directly affected low-skilled workers, while for high-skilled workers its effect was mitigated by employers. The fee disincentives or directly impedes family reunion for low-paid workers and led to the departure of dependents in the autumn of 2017 among low-income families. 23 ▪ Labour rights Labour reforms have introduced protective measures that also cover migrant workers, such as maximum work hours, mandatory insurance, a cap in recruitment fees, and, in some GCC countries (Kuwait in 2016, Qatar in 2020), non-discriminatory minimum wages. Reforms have also criminalised extortionary practices, such as extortionate recruitment fees, non-payment, under-payment, or delay in payment of wages, the withholding of passports for coercive purposes, and failure to pay for social insurance and health coverage [START_REF] Gardner | A Portrait of Low-Income Migrants in Contemporary Qatar[END_REF]Jureidini 2016). However, enforcement remains elusive (Migrants-rights.org 2019).

While introducing new rights, governments have also institutionalised inequality in access to them, notably by continuously exempting domestic workers from the protections provided by mainstream labour law. A population of around 3.5 million domestic workers remains formally excluded from labour laws in Kuwait (Government of Kuwait 2010; 2015, article 5), Oman (Ministry of Manpower Sultanate of Oman 2003, article 2), Qatar (State of Qatar 2004, section 3. art. 28), and Bahrain, despite recent reforms (Kingdom of Bahrain 2013;[START_REF] Herb | The Wages of Oil: Parliaments and Economic Development in Kuwait and the UAE: Michael Herb[END_REF].

The potential for exploitation and abuses created by this legal discrimination is exacerbated by the nature of relations with employers or kufala' and the material conditions of domestic work: maids, drivers, cooks, and nannies mostly live and work in employers' homes, while [START_REF] Bruslé | What Kind of Place Is This?. Daily Life, Privacy and the Inmate Metaphor in a Nepalese Workers' Labour Camp (Qatar)[END_REF] has documented the conditions of construction workers housed in remote "camps" away from the city of Doha, with no public transportation available apart from the employing companies' buses. These buses only operate travel between work sites, creating carceral feelings for migrant workers who describe themselves metaphorically as "inmates".

Conclusion

23 Interviews with migrants, Riyadh, 2017.

Overall, this article seeks to bring the Gulf into broader conversations on migration politics and build new frameworks to analyse the political sociology of migration states. Gulf states have long been treated as outliers in migration politics with research highlighting exceptionally illiberal policies and highly discriminatory and exploitative practices.

This research on the contrary highlights how state control over societal and private actors may be brought into comparison with other contexts. It resonates with the complementary trends of privatisation of migration control and the extension of migration policy domains in Western democracies [START_REF] Guiraudon | A Reappraisal of the State Sovereignty Debate: The Case of Migration Control[END_REF][START_REF] Guiraudon | The Constitution of a European Immigration Policy Domain: A Political Sociology Approach[END_REF]. It also speaks to state control of the migration industry in Asia [START_REF] Koh | Drivers of Migration Policy Reform: The Day off Policy for Migrant Domestic Workers in Singapore[END_REF]. It does not only open new comparative perspectives on the transformations at work within migration states and in statesociety relations but also invite to test the notion of "migration rent" and "immigration rentier states" to other states that are heavily reliant upon immigration for their wealth (labour market) derive unearned income from immigration.

In terms of substance of migration policies, Gulf states also offer a magnifying lens to observe how labour market segmentation are formalised by state policies. Gulf state fit in increasing discriminatory policies across contexts (de [START_REF] Haas | Growing Restrictiveness or Changing Selection? The Nature and Evolution of Migration Policies[END_REF]. Far from being a pathology of illiberal contexts, the skill-based order of things operates within countries and across countries, organising class-based differentiated exclusion of unskilled "helots" [START_REF] Cohen | The New Helots : Migrants in the International Division of Labour[END_REF]) and inclusion of highly skilled "expatriates" and regulating mobility and residence rights along class lines. Although this skill-based order of things is largely presented as value-neutral and mechanically driven by the globalisation of labour markets, this research emphasize the need for further exploration of how the politics of class-based migration governance emerges across contexts.

Figure 1 :

 1 Figure 1: Kafil, State, Market, Migrant: socio-economic functions.

Kafala

  does not exist anymore in fact. […] We do not use the word. […] It sort of ended up symbolising the evil of illegal practices.

Table 1 : Migrants as proportion (%) of GCC populations (UNDESA 2020)

 1

		1990	1995	2000	2005	2010	2015	2020
	Bahrain	34.9	36.5	36.0	45.4	53.7	52.7	55.0
	Kuwait	51.3	57.4	55.1	58.7	62.7	74.7	72.8
	Oman	16.8	24.5	27.5	26.5	26.8	43.5	46.5
	Qatar	65.0	70.4	60.7	74.6	78.5	65.8	77.3
	Saudi Arabia	30.8	27.5	25.5	27.3	30.7	34.0	38.6
	UAE	71.5	75.5	78.1	71.5	85.6	86.3	88.1

Table 2 : Proportion (%) of nationals and immigrants employed in public and private sectors.

 2 Sources: Most recent data published by official sources.

		% of nationals in the	% of migrants in the	% of national in the	% of migrants in the
		private sector	private sector	public sector	public sector
	Bahrain (2018)	17.3	82.7	84.5	15.5
	Kuwait (2015)	4.1	95.9	70.5	29.5
	Oman (2014)	10.9	89.1	85.8	14.2
	Saudi Arabia (2017)	18.7	81.3	94.9	5.1
	Qatar (2016)	1.1	99.4	31.2	63.8
	UAE (2017)	9.1	87.6	83.7	8.0

The term "social contract" has been debated in the context of the Gulf (POMEPS 2019), and I use it metaphorically in a non-democratic context where citizens do not formally agree to the state's rule[START_REF] Jones | Seeking a "Social Contract" for Saudi Arabia[END_REF].

The "rentier state", as manifested in the Middle East region, represents a significant, yet contentious contribution to political science(Anderson (1987, 9).

Bahrain, Kuwait, Saudi Arabia, the United Arab Emirates, Qatar, and Oman.

See Thiollet (2022a) for a comprehensive historical account. Adamson,Thiollet and Tsourapas (2018) have also shown the commonalities between colonial migration states across the Middle East before under direct and indirect imperial rule.

We here borrow the terms adopted byHerb (2014, 10) to characterise extreme and middling oil rentiers.

Referring to the negative socio-economic impacts of the discoveries of gas reserves in the Netherlands in 1964, inducing economic and labour market distortions.

[START_REF] Yamada | Introduction: Revisiting Rentierism-with a Short Note by Giacomo Luciani[END_REF] published a special issue on rentier states with no mention of migration.

Sponsorship exists across the world, both formally and informally, brokering both geographical and social mobility, integration, or exclusion and exploitation. SeeBosma et al. (2012) for a historical survey, Linquist (2015) for general discussion on brokerage in anthropology.

No-objection letters are mandatory in KSA, Qatar, and Oman, and restricted to limited cases in Kuwait, the UAE, and Bahrain.

Interviews, Riyadh, 2006, 2015, and 2017.

Interview, Riyadh, 2015.

Segmentation also depends upon gender and age. While working-age immigrants represent "only" 55% of adults, foreign workers represent around 70% of the total GCC labour force(ILO 2022). This discrepancy is caused by two factors: a majority of female GCC nationals are outside the labour force, and unemployment has been relatively high among GCC youth since the 1990s.

Source: https://saudigazette.com.sa/article/618349/SAUDI-ARABIA/Final-year-to-exempt-small-firms-fromexpat-levy-begins

sincere gratitude to Laurence Louër for fruitful conversations. Fieldwork conducted in Saudi Arabia in 2013, 2014, 2015, and 2017 was financed by the French National Agency for Research through two research programs (ANR-12-GLOB-0004 and ANR-10-PDOC-0018) and with the institutional support of the Faisal Centre for Research and Islamic Studies (Riyadh).

Biographical note: Hélène Thiollet is a CNRS researcher based at the Centre for International Research (CERI) at Sciences Po. She works on migration and asylum in the Global South, with a focus on the Middle East and Sub-Saharan Africa. Her research also deals with the politics of migration


Andreas Plank

Sibylle Möhle

Martina Seidl

Enumerative Level-2 Solution Counting for Quantified Boolean Formulas

Keywords: 2012 ACM Subject Classification Theory of computation → Automated reasoning QBF, Second-Level Model Counting Digital Object Identifier 10, 4230/LIPIcs, CP, 2023, 49

We lift the problem of enumerative solution counting to quantified Boolean formulas (QBFs) at the second level. In contrast to the well-explored model counting problem for SAT (#SAT), where models are simply assignments to the Boolean variables of a formula, we are now dealing with tree (counter-)models reflecting the dependencies between the variables of the first and the second quantifier block. It turns out that enumerative counting on the second level does not give the complete model count. We present the -to the best of our knowledge -first approach of counting tree (counter-)models together with a counting tool that exploits state-of-the-art QBF technology. We provide several kinds of benchmarks for testing our implementation and illustrate in several case studies that solution counting provides valuable insights into QBF encodings.

Introduction

Over the last decade, solvers for quantified Boolean formulas (QBFs) have become appealing tools to handle PSPACE-hard problems as found in many applications from, for example, artificial intelligence and formal verification (see [START_REF] Shukla | A survey on applications of quantified Boolean formulas[END_REF] for a survey). Much progress has been made in the theory and practice of solving [START_REF] Beyersdorff | Quantified Boolean Formulas[END_REF][START_REF] Pulina | The 2016 and 2017 QBF solvers evaluations (QBFEVAL'16 and QBFEVAL'17)[END_REF], partly relying on generalizations of techniques from SAT, but partly being enabled by new genuine QBF techniques. However, some aspects of QBFs are hardly explored yet. One of these is counting the number of solutions of a formula. The problem of counting the number of solutions of a given QBF is also known as #QBF [START_REF] Ladner | Polynomial space counting problems[END_REF]. In contrast to #SAT [START_REF] Gomes | Model counting[END_REF], the counting problem of propositional logic, which is used in many application domains including probabilistic reasoning [START_REF] Chakraborty | Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls[END_REF][START_REF] Sang | Performing Bayesian inference by weighted model counting[END_REF], verification of neural networks [START_REF] Baluta | Quantitative verification of neural networks and its security applications[END_REF][START_REF] Narodytska | Assessing heuristic machine learning explanations with model counting[END_REF] and the analysis of software vulnerability [START_REF] Biondi | Scalable approximation of quantitative information flow in programs[END_REF][START_REF] Zhou | Static evaluation of noninterference using approximate model counting[END_REF], #QBF has mainly been studied theoretically [START_REF] Ladner | Polynomial space counting problems[END_REF][START_REF] Hemaspaandra | The satanic notations: counting classes beyond #P and other definitional adventures[END_REF][START_REF] Bauland | Quantified constraints: The complexity of decision and counting for bounded alternation[END_REF].

Only recently, some work has been presented dealing with counting the solutions of a QBF at the outer-level [START_REF] Shukla | Outercount: A first-level solution-counter for quantified boolean formulas[END_REF]. Given a true QBF with first quantifier block ∃X, this work is concerned with the problem of counting the number of assignments to the variables in X leading to a QBF that is true. The authors also consider the dual problem, i.e., given a false QBF starting with quantifier block ∀Y , how many assignments of the variables Y result in a false QBF? In order to answer these questions, they presented an enumerative approach that directly resulted from enumerative propositional model counting [START_REF] Birnbaum | The good old Davis-Putnam procedure helps counting models[END_REF][START_REF] Dubois | Counting the number of solutions for instances of satisfiability[END_REF]. Therefore, a solver is used to obtain one solution, which is then excluded from the formula to obtain a different solution. This process is repeated until no further solution is found.

In this work, we go one step further by dealing with solutions of true QBFs that start with quantifier prefix ∀X∃Y and false QBFs that start with quantifier prefix ∃X∀Y , i.e., in the first case, we count models and in the second case, we count counter-models. For both cases, the solutions are not simply propositional assignments as in outer-level counting, but tree models and counter-models capturing the dependencies between the variables of the first and second quantifier block. While tree (counter-)models are a very convenient way to describe QBF solutions, in practice, QBF solvers represent solutions by Boolean functions. We will use both views on QBF solutions to investigate to what extend enumeration-based counting can be lifted to the second level. Therefore, solutions are excluded by conjunctively/disjunctively adding (negated) functions to the formula until no further solutions are found. It turns out, that enumeration-based solution counting at the second level does not lead to the full model count, but still gives valuable insights about the solutions of a formula. We implemented the approach in a first prototype to evaluate how it works in practice. To this end, we build on state-of-the-art QBF solving technology like incremental solving and function extraction.

This paper is structured as follows. First, we introduce the necessary preliminaries in the next section. Then we present the level-2 counting problem by an example in Section 3 before we discuss enumeration-based solution counting in Section 4. In Section 5, evaluate our implementation on three different types of benchmarks, before we conclude in Section 6.

Preliminaries

We consider quantified Boolean formulas of the form Π.ϕ, where

Π = Q 1 X 1 . . . Q n is called quantifier prefix (with Q i ∈ {∀, ∃}, Q i ̸ = Q i+1 for i ∈ {1, .
.., n -1} and X 1 , . . . , X n are pairwise disjoint, non-empty sets of Boolean variables). The matrix ϕ is a propositional formula over variables X i with standard Boolean connectives ¬, ∨, ∧, →, ↔ and ⊕ (XOR). The prefix Π induces an ordering on the variables:

x i < Π x j if x i ∈ X i , x j ∈ X j and i < j.
If prefix Π is clear from the context, we just write x i < x j . In this paper, we consider only closed formulas, i.e., every variable that occurs in matrix ϕ also occurs in the prefix Π.

A QBF Π.ϕ is in prenex conjunctive normal form (PCNF), if ϕ is a conjunction of clauses. A clause is a disjunction of literals and a literal is a variable or a negated variable. If l is a literal, then var(l) = x if l = x or l = ¬x. As usual, l = x if l = ¬x and l = ¬x otherwise.

For a QBF φ = Q 1 X 1 . . . Q n X n .ϕ, var(φ) = X 1 ∪ . . . ∪ X n .
An assignment σ of φ is a set of literals over (a subset of) var(φ) such that there is no l ∈ σ with l ∈ σ. For an assignment σ, var(σ) = {var(l) | l ∈ σ}. If var(σ) = var(φ), then σ is a full assignment, else it is a partial assignment. A (partial) X-assignment is an assignment over a (sub-)set of variables X.

Given a propositional formula ϕ and an assignment σ, then ϕ σ denotes the formula obtained when setting all variables x ∈ var(σ) to true if x ∈ σ and to false if ¬x ∈ σ, respectively. Based on this notation, the semantics of a QBF is defined as follows: ∀xΠ.ϕ is true iff Π.ϕ {x} and Π.ϕ {¬x} are true. A QBF ∃xΠ.ϕ is true iff Π.ϕ {x} or Π.ϕ {¬x} is true. For example, the QBF ∀x∃y.(x ↔ y) is true, while the QBF ∃y∀x.(x ↔ y) is false. A model for a QBF φ = Π.ϕ with |var(φ)| = m is a tree of height m + 1 such that every node at level k ∈ {1, . . . , m} is labeled with a variable x k in the order of the prefix, i.e., if variable x j is at level j and variable x k is at level k with j < k then x j ≤ Π x k . A node at level k has one child if x k ∈ X i and Q i = ∃, and two children if Q i = ∀. In the graphical representation, a dashed edge indicates that the parent variable is set to false and a solid edge indicates that it is set to true. Examples are shown in Figure 1. The path from the root to the leaves gives a full assignment under which ϕ evaluates to true.

49:3

x: y: a: b:

ϕ: ⊤ ⊤ ⊤ ⊤ ⊥ ⊤ ⊥ ⊤ ⊥ ⊥ ⊤ ⊤ ⊥ ⊥ ⊥ ⊤
ϕ: ⊤ ⊤ ⊤ ⊤ Figure 1
The left tree shows the full assignment tree for the given QBF. Tree models (16 in total) are subtrees of the assignment tree such that universal nodes have two children, existential nodes have one child and all leaves are ⊤. An example of a tree model is shown on the right.

A counter-model is defined dually, with the difference that universal nodes have one child node, existential nodes have two child nodes, and the matrix evaluates to false under the respective assignments. An alternative representation of tree models that is practically more relevant are sets of Skolem functions, so-called Skolem sets. A Skolem set F of a true QBF Φ is a set of Boolean functions such that for each each existential variable y of Φ, there is a function f y (x 1 , . . . , x n ) ∈ F where x 1 , . . . , x n are the universal variables of Φ with x i < y. The elements of a Skolem set are called Skolem functions. If we take the matrix of Φ and replace all the existential variables by their Skolem functions, we obtain a valid propositional formula over the universal variables of Φ. A Skolem set for the true QBF ∀x∃y.(x ↔ y) is {f y = x}. If we replace y by f y , we obtain the valid formula (x ↔ x). If σ X is an assignment to a set of universal variables X, then f y (σ X ) denotes the value of y w.r.t. the assignment of the variables in X. For false QBFs and their tree counter-models, functions for the universal variables are defined dually. Such functions are called Herbrand functions and are collected in Herbrand sets. If we replace all universal variables by their Herbrand functions of a Herbrand set, we obtain an unsatisfiable formula.

Counting at Level Two

In the following, we introduce the QBF level-2 counting problem by an example. Consider the true QBF

Φ = ∀x, y∃a, b.(¬x ∨ a) ∧ (¬y ∨ b).
On the left of Figure 1 we see the full assignment tree of φ = Π.ϕ. Each complete path from the root to a leaf node represents a full assignment to the variables in φ. A tree model of φ is a subtree of this assignment tree such that nodes x and y have two children, nodes a and b have one child each, and the leaves are labeled by ⊤. An example of a tree model is shown on the right of Figure 1. We are concerned with the question of counting the number of tree models of a given true QBF. Alternatively, we could also ask the question how many different Skolem sets a true QBF has. Here it is important that syntactically different, but semantically equivalent Skolem sets are not counted multiple times. For example the Skolem functions f a = ⊤ and f a = (x ∨ ¬x) of our example are semantically equivalent even though they are syntactically different.

A direct approach to count tree models is to iterate over all assignments σ of the universal variables in the first quantifier block of a true QBF φ = Π.ϕ. With a propositional model counter we can determine the number of satisfying assignments of ϕ σ . If S is the set of all assignments of the universal variables in the first quantifier block, then the total number

T 1 T 2 T 3 T 4 x: y: a: b: c: ϕ: ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ variable is set to ⊥ variable is set to ⊤ Figure 2 Tree models of ∀x∀y∃a∃b∃c.(¬x ∨ a ∨ c) ∧ (¬y ∨ b ∨ ¬c).
of tree models is Π σ∈S #SAT (ϕ σ ). Counting counter-models is defined dually, with the difference that the role of existential and universal quantifiers is exchanged, i.e., the formulas need to have a prefix starting with ∃X∀Y . While this direct approach results in a complete solution counter, it is very inefficient to iterate over all assignments of the variables in the outermost quantifier block and solve a propositional counting problem for each assignment.

In the following section, we therefore investigate if an enumeration-based approach relying on recent QBF solving technology is possible.

Enumerative Model Counting for 2QBF

In this section, we formalize enumeration-based solution counting for the second level. For technical simplicity, we focus on true 2QBFs (formulas with quantifier prefix ∀X∃Y ). To this end, we lift the idea of blocking clauses to blocking functions. Recall that a blocking clause in SAT is the negation of a model σ of a formula ϕ. If ϕ is enriched with ¬σ, then σ is excluded from the solution space. For QBFs, we introduce the notion of blocking Skolem set as follows.

▶ Definition 1. Let Φ = ∀X∃Y.ϕ be a true QBF and let F be a Skolem set of Φ. Then ¬ϕ F is a blocking Skolem set of Φ where ϕ F = fy∈F (y ↔ f y ).

In the following example, we now use blocking Skolem sets to exclude solutions.

▶ Example 2. Consider the true QBF Φ = ∀x∀y∃a∃b∃c.(¬x ∨ a ∨ c) ∧ (¬y ∨ b ∨ ¬c). We now incrementally add blocking Skolem sets ¬ψ Fi until the formula becomes false. The resulting models are shown in Figure 2.

1. One solution of this formula is tree T 1 , which is represented by Skolem set

F 1 = {f a (x, y) = ⊤, f b (x, y) = ⊤, f c (x, y) = ¬y}. To exclude F 1 , we add ¬ψ F1 to Φ and obtain Φ 1 = ∀x∀y∃a∃b∃c.(¬x ∨ a ∨ c) ∧ (¬y ∨ b ∨ ¬c) ∧ ¬ψ F1 . Now T 1 is no solution of Φ 1 . 2. A solution of Φ 1 is T 2 with Skolem set F 2 = {f a (x, y) = ⊥, f b (x, y) = (x ↔ y), f c (x, y) = x}.
To exclude F 2 as well, we get Φ 2 = ∀x∀y∃a∃b∃c.(¬x∨a∨c)∧(¬y∨b∨¬c)∧¬ψ F1 ∧¬ψ F2 .

Next, we get tree model

T 3 with Skolem set F 3 = {f a (x, y) = ⊤, f b (x, y) = (x ⊕ y), f c (x, y) = ¬x}.
We exclude F 3 from Φ 2 as before and obtain Φ 3 .

4.

The next tree model we find is T 4 with Skolem set

F 4 = {f a (x, y) = x, f b (x, y) = y, f c (x, y) = y}. 5. Finally, the QBF Φ 4 = ∀x∀y∃a∃b∃c.ϕ ∧ ¬ψ F1 ∧ ¬ψ F2 ∧ ¬ψ F3 ∧ ¬ψ F4 is false.
We found four different tree models, each with four branches. Hereby Tseitin transformation is used to add the blocking function to the PCNF formula before each solver call. From these four models, we can assemble more models by combining the red branches of Figure 2. To calculate the full model count, all possible combinations of the paths need to be considered, resulting in 4 4 models in total (there are four choices for the branch {x, ȳ}, four choices for the branch {x, ȳ} and so on). When we take a closer look, however, the count is not correct, as also {x, ȳ, a, b, c} is a model of the matrix of Φ, but it has not been considered.

As the example above shows, blocking Skolem sets can indeed be used to exclude solutions, but they are sometimes too restrictive. To describe what is happening when adding blocking Skolem sets to a formula, we need to introduce the following definitions.

▶ Definition 3. Let Φ = ∀X∃Y.ϕ be a true QBF and let T 1 and T 2 be tree models of Φ. Then T 1 and T 2 are disjoint if there are no complete paths σ 1 of T 1 and σ 2 of T 2 with σ 1 = σ 2 .

A complete path describes a full assignment (i.e., an assignment of all variables), such that the according branch of the tree model evaluates to true. The trees of Figure 2 are disjoint, because all their paths are different. If we want to characterize the models of a QBF in terms of Skolem sets, we get the following definition.

▶ Definition 4. Let Φ = ∀X∃Y.ϕ be a true QBF and let F and G be Skolem sets of Φ. Then F and G are called disjoint if for each full assignment σ X of the universal variables X there exists an existential variable y ∈ Y such that f y (σ X ) ̸ = g y (σ X ) with f y ∈ F and g y ∈ G.

The notion of disjoint models is rather strong as it forbids to have to have common paths in the tree model representation. We therefore also introduce the notion of different models requiring that at least one path of two tree models is different. This notion is transferred to Skolem sets as follows.

▶ Definition 5. Let Φ = ∀X∃Y.ϕ be a true QBF. Furthermore, let F and G be Skolem sets of Φ. Then F and G are called different if there exists a full assignment σ X of the universal variables X such that there is an existential variable y ∈ Y with f y (σ X ) ̸ = g y (σ X ), f y ∈ F , and g y ∈ G.

Obviously, any two disjoint models are different. The other direction does not hold. To count all models of a QBF, we need to count the different models. As the following lemma shows, using blocking Skolem sets excludes disjoint models only.

▶ Lemma 6. Let Φ = ∀X∃Y.ϕ be a QBF and F be a Skolem set of Φ. If G is a Skolem set of Φ ′ = ∀X∃Y.ϕ ∧ ¬ϕ F , where ¬ϕ F is a blocking Skolem set as defined above, then F and G are disjoint.

Proof. Assume that F and G are not disjoint. Then there is an assignment σ X such that for all y ∈ Y it holds that f y (σ X ) = g y (σ X ) for f y ∈ F, g y ∈ G. Now we extend the assignment σ X to an assignment over X ∪ Y as follows:

σ = σ X ∪ {y | f y (σ X ) = ⊤, f y ∈ F } ∪ {¬y | f y (σ X ) = ⊥, f y ∈ F } = σ X ∪ {y | g y (σ X ) = ⊤, g y ∈ G} ∪ {¬y | g y (σ X ) = ⊥, g y ∈ G}.
As G is a Skolem set of Φ ′ , σ has to satisfy ¬ϕ F . But by its construction, σ also satisfies ϕ F , leading to a contradiction. Hence, F and G have to be disjoint. ◀

As the following lemma shows, we can use the enumerative approach to calculate the maximum number of pairwise disjoint Skolem sets. Enumerative Solution Counting for QBFs Proof. Since Φ ′ is false, there is at least one assignment σ X such that ϕ ′ is unsatisfiable under σ X . Assume there is a Skolem set

F m+1 that is pairwise disjoint with F 1 , . . . , F m . Let σ = σ X ∪ {x | f x (σ X ) = ⊤, f x ∈ F } ∪ {¬x | f x (σ X ) = ⊥, f x ∈ F }.
Since F m+1 is a Skolem set of Φ, ϕ is satisfied by σ. Further, σ satisfies ¬ϕ Fi with 1 ≤ i ≤ m, because F i and F m+1 are disjoint. Hence, ϕ ′ is satisfied by σ. This contradicts the assumption that ϕ ′ is unsatisfiable under σ X . ◀

The maximum number of pairwise disjoint models is determined by the assignments of the variables in the outermost universal quantifier block that, when the universal variables are assigned accordingly, lead to the fewest propositional models.

▶ Lemma 8. Let Φ = ∀X∃Y.ϕ be a true QBF and let S be the set of all full assignments of universal variables X. Then the maximum number of pairwise disjoint models of

Φ is min({#SAT (ϕ σ ) | σ ∈ S}).
The proof of the lemma above follows directly from the construction of disjoint models. For example, the QBF ∀x, y∃a, b.(¬x ∨ a) ∧ (¬y ∨ b) with the assignment tree shown in Figure 1 has only one disjoint model, because for the assignment σ = {x, y}, there is only one assignment to {a, b} that satisfies the matrix under σ. In contrast, the QBF ∀x∀y∃a∃b∃c.(¬x ∨ a ∨ c) ∧ (¬y ∨ b ∨ ¬c) from Example 2 has four disjoint models, because of the assignment {x, y}. In practical encodings, those assignments of the universal variables determine the number of disjoint models for which the assignment of the outermost variables not immediately falsifies the formula. The number of disjoint models gives us a lower bound for the full model count.

▶ Proposition 9. Given a true QBF Φ = ∀X∃Y.ϕ with |X| = n and m pairwise disjoint tree models. Then Φ has at least m 2 n different tree models.

If we know that a true QBF Φ = ∀X∃Y.ϕ with |X| = n has m pairwise disjoint models, we can calculate the full model count as follows. Let Φ ′ = ∀X∃Y.ϕ ′ with ϕ ′ = ϕ∧¬ϕ F1 ∧. . .∧¬ϕ Fm be the false QBF obtained by enriching Φ with the m blocking Skolem sets. Furthermore, let S be the set of assignments of variables X such that ϕ ′ σ is true ∀σ ∈ S. Then the full model count is

σ∈S #SAT (ϕ ′ σ ) * m 2 n -|S|
While the enumerative approach also works for true QBFs with prefix ∀X∃Y ∀ZΠ.ϕ for counting disjoint partial Skolem sets that consider only functions of the set Y , it is not possible to obtain a full model count of partial Skolem sets in the Y variables by using a propositional model counter. Here, the approach needs to be applied recursively.

The enumerative approach for counting disjoint models also directly transfers to an enumerative approach for counting disjoint counter-models of false QBFs starting with the prefix ∃X∀Y ∃Z.1 ▶ Proposition 10. Let Φ = ∃X∀Y ∃Z.ϕ be a false QBF and let H 1 , . . . , H m be disjoint Herbrand sets such that

Φ ′ = ∀X∃Y.(ϕ ∨ ϕ H1 ∨ . . . ∨ ϕ Hm )
is true with ϕ H = hy∈H (y ↔ h y ). Then m is the maximum number of pairwise disjoint Herbrand sets over the variables from Y .

Evaluation

We implemented the previously described approach in the tool qCounter. 2 As backend solver our tool relies on the QBF solver DepQBF 6.03 [START_REF] Lonsing | DepQBF 6.0: A search-based QBF solver beyond traditional QCDCL[END_REF] which is able to produce Q-resolution proofs for true and false formulas from which Skolem and Herbrand functions can be extracted. We used the QBF certification framework QBFCert [START_REF] Niemetz | Resolution-based certificate extraction for QBF -(tool presentation)[END_REF] to obtain the functions in the Aiger format. 3 We implemented a small tool to convert the blocking functions of the variables from the second quantifier block. Therefore, the Skolem functions needed to be negated and appended conjunctively to the current QBF by using the incremental interface of DepQBF.

To disjunctively add the Herbrand functions, an extra Tseitin transformation step is necessary to obtain a formula in PCNF. While this transformation introduces auxiliary variables we can avoid an exponential increase of the formula using this technique [START_REF] Tseitin | On the Complexity of Derivation in Propositional Calculus[END_REF][START_REF] Kuiter | Tseitin or Not Tseitin? The Impact of CNF Transformations on Feature-Model Analyses[END_REF]. For this we also used the incremental interface of DepQBF with its ability to add temporary clauses.

To calculate the full model count as described above, we employed the propositional model counter Ganak [START_REF] Sharma | Ganak: A scalable probabilistic exact model counter[END_REF] together with the SAT solver Lingeling [START_REF] Biere | Treengeling and YalSAT Entering the SAT Competition[END_REF].

Currently, there exist no standard benchmark sets which we could use to evaluate the correctness and performance of our implementation. To this end, we propose three different benchmark sets: (1) randomly generated formulas, (2) QBF encodings of the unique-SAT problem (does a given propositional formula have exactly one solution?) and (3) benchmarks from past QBF Evaluations with a suitable quantifier structure. Whereas the benchmarks from ( 1) and ( 2) are constructed in such a way that the number of models is known, this is not the case for the benchmarks from (3). Details follow below. All experiments were performed on a cluster of dual-socket AMD EPYC 7313 @ 16 × 3.7GHz machines with 4GB memory limit and 1800 seconds as timeout.

Randomly Generated Formulas

We provide a generator that returns true 2-QBFs in PCNF with quantifier structure ∀X∃Y such that the number of (disjoint) models is known. The parameters n (size of X), m (size of Y ) have to be provided. For producing the clauses of the matrix, the generator iterates over all possible assignments of the universal variables X and excludes propositional models by randomly assigning the existential variables Y and building blocking clauses. For example, for a prefix ∀x 1 , x 2 ∃y 1 , y 1 the clause (x 1 ∨ x2 ∨ y 1 ∨ y 2 ) prohibits in any QBF model that in the branch where x 1 is set to false and x 2 is set to true, both y 1 and y 2 are both set to false. The number of disjoint models is determined by the branch with the smallest number of propositional models (see also Lemma 8).

We generated 3950 formulas with 2 ≤ |X|, |Y | ≤ 11 having up to 100 disjoint models each. For 2608 of these formulas, the number of disjoint models could be determined. The results are shown in the left plot of Figure 3. We cluster the results according to the size of X, indicating that not only the number of disjoint models impacts the runtime, but also the size of the first quantifier block.

Unique-SAT Encodings

The question whether a given propositional formula ϕ has exactly one model can be encoded by a QBF ∃X∀.ψ as shown in [START_REF] Kleine | Propositional logic -deduction and algorithms[END_REF]. In this QBF, X contains the variables of ϕ, Y is a copy of the variables of ϕ, and ψ is constructed in such a way that the QBF is true iff ϕ has exactly one model. The prefix fits for counting the counter-models at level-2 in case the QBF is false. The number of QBF counter-models can be determined based on the number of the models of ϕ. If ϕ is unsatisfiable and has n variables, then the number of disjoint counter-models equals the number of different counter-models and is 2 2 n . If ϕ has m models, then it has (m -1) disjoint models and (2 n ) 2 n -m (m -1) m different models.

We generated 497 Unique-SAT formulas based on true propositional formulas with 26 to 240 variables and 61 and 643 clauses by using the random generator from [START_REF] Lauria | CNFgen: A Generator of Crafted Benchmarks[END_REF]. We considered only propositional formulas with more than one model in order to count disjoint counter-models of the resulting false QBFs. The performance of our tool is shown in the right plot of Figure 3. The number of disjoint counter-models enumerated by our tool could be quickly validated with a propositional model counter. In this way, we could check the results of our tool for false formulas.

Benchmarks from QBF Evaluations

As a final set of benchmarks, we considered formulas from the main tracks of QBFEval 2022 and QBFEval 2008. 4 From the QBFEval 2022 set, we identified 18 true formulas and 102 false formulas with a suitable prefix structure that could be solved by plain DepQBF within a time limit of 1800 seconds. In a similar way, we selected two true formulas and 683 false formulas from the QBFEval 2008 set. For the 2022 formulas, we could determine the number of disjoint models of 3 formulas and the number of disjoint counter-models of 53 formulas. For the 2008 formulas, we could determine the number of disjoint models for both formulas and the number of disjoint counter-models of 285 formulas. Interestingly, many of the formulas have only one disjoint model indicating that the search space is strongly restricted for certain assignments of the variables in the outermost quantifier block. On the other hand, for some of the formulas we could find up to 82 disjoint (counter-)models. Details are shown in the right plot of Figure 3.

Conclusion

We considered the problem of counting level-2 (counter-)models for QBFs. It turned out that enumerating Skolem/Herbrand functions does not provide the full count of solutions as it is the case for propositional model counting and counting QBF models at the outer level. We characterized the subset of solutions which can be counted in an enumerative manner. This subset often connects to interesting solutions of a QBF encoding. We also provided the first practical implementation of an enumerative method for level-2 solution counting. Our approach cannot only be used for counting, but also for explicitly enumerating solutions which might also have some applications in better understanding and debugging QBF encodings. We provided several sets of benchmarks of true and false instances to evaluate our implementation. We consider this work as an important first step to full solution counting, i.e., for QBFs with an arbitrary number of quantifier blocks. While a recursive application of our approach seems possible, it has to be expected that this approach will be inefficient. Hence, alternative ways need to be explored like a tight integration of solving and counting or exploiting approaches that process the prefix in a reverse order as it is for example done in certain preprocessing techniques.

▶ Proposition 7 .

 7 Let Φ = ∀X∃Y.ϕ be a true QBF and let F 1 , . . . , F m be pairwise disjoint Skolem sets of Φ such thatΦ ′ = ∀X∃Y.ϕ ′ = ∀X∃Y.(ϕ ∧ ¬ϕ F1 ∧ . . . ∧ ¬ϕ Fm )is false. Then m is the maximum number of pairwise disjoint Skolem sets.

Figure 3

 3 Figure 3 Runtime related to number of disjoint models for randomly generated formulas (left) and Unique-SAT/QBFEval benchmarks (right).

Note that we include the last quantifier block to deal with formulas in PCNF. Otherwise, the universal variables could be immediately removed.

The tool, the benchmarks and the log-files are publicly available at https://qcount.pages.sai.jku.at/l2count

http://fmv.jku.at/aiger/

http://www.qbflib.org

Funding This work has been supported by the LIT AI Lab funded by the State of Upper Austria.