Hezbollah and Hamas legitimized themselves politically by providing social services to the local population. Thomas Ricks writes that the Iraqi government is unable to establish its legitimacy for the same reasons.

The central government isn't providing services, and so is disconnected from the tribes. "The lack of tethering ... of governmental structures to the most powerful socio-cultural dynamic in Iraq, the tribal system, is worrying." This lack threatens to undo the political gains of the last couple of years.

So we are left with social democracy as the mechanism to provide a stable state. This makes it difficult for increasing limited government as a political model.
John Barrdear : I tend to think of models with multiple equilibria in this situation. For the sufficiently wealthy and healthy, their current state is enough, on average, to ensure that they stay healthy and save for a rainy day (the current recession's demonstration of sub-rationality aside). For the sufficiently poor and sick, their current state renders them unable to improve their position.

The immediate implication is one of temporary government involvement to lift the poor and the sick up to the higher state. The secondary implication is to contemplate the political economy of such a scenario and how to convince the government to reduce itself once it has got (nearly) everybody up to the higher state.
cam : I suspect there is a visibility aspect to it as well. It is like the "what have the Romans ever done for us, other than ..." style of Monty Python joke. Then again the Roman system for the voting citizen was highly social democratic, grain was given out without cost, Egypt was important for that reason alone and a reason why the emperor Augustine kept it as his private pro-consulship. The Aedile position was also one of public works, building aqueducts, etc. The Greeks had a word for public works too, can't recall what it was now, but basically the wealthy classes had to give money over to works in order to keep social stability.

I recall the Islamic group that installed itself in Somalia taking a similar tack to Hamas and Hezbollah by establishing their governing legitimacy with social services. They got run out of town by violence, but Islam and its internal organization makes it a quick candidate to bring order and services to chaotic regions that suffer from poor or a lack of governance.
State Legitimacy and Social Democracy
Another data point for a state having no legitimacy unless it takes a social democratic approach. Nathanial Fink describes the counter-insurgency campaign in Afghanistan:

Consider, for example, the question of roads. When U.N. teams begin building new stretches of road in volatile Afghan provinces such as Zabul and Kandahar, insurgents inevitably attack the workers. But as the projects progress and villagers begin to see the benefits of having paved access to markets and health care, the Taliban attacks become less frequent.

Non-state actors gain their political legitimacy in the same way. Hezbollah and Hamas both have social democratic and judicial components which not only replaces a weak state but helps keep it out of those areas.

Hezbollah is the second largest employer in Lebanon. It runs hospitals, orphanages, discount pharmacies and garbage collection. All of those are services which governments in Australia provide. (more)
Felix the Cassowary : I hate to be a pedant/grammar nazi --- especcially when I'm saying nothing else --- but it was forced upon me by your mistake:

If you have one, you have an equilibrium. If you have more than one, you have lots of equilibria (or, if you prefer, lots of equilibriums). But, I'm afraid, you have "an equilibria" no more often than "an oranges".

(It's one of those times when you start looking around for the edit button before remembering this is a read-only blog and not a read-write wiki.)
Tony G : "The equilibria for a nation-state to remain an unchallenged political entity is somewhere between 30% and 50% GDP taxation, most of which goes to providing order, civil and social services. That seems to be the cost to ensure a universal approach to services that stops non-state social and collective competitors from arising."

Unfortunately, that is what seems to be happening, but what is to say that the mix of public/private services could not be changed and still be successful.

The democracies you mentioned -United States, Australia, Canada and New Zealand, for instance, ran successfully for 80% of the last century on smaller governments. Syphoning only 20% or less from their respective GDPs.

Political entities taking 30% plus of GDP, seems excessive when compared to what was commonly used between 1900 and 1980.
Nation-State Equilibria

Is social democratic organisation the only way an elected government can maintain their legitimacy against intrusion from non-state movements? (more)
Cam Riley: South Sea Republic. Freedom, liberty, equity and an Australian Republic.