This is feudalism. (Kinda, pop culture version)

If a town stops paying taxes the king doesn't send in the army. They go to the mayors of the 4 surrounding cities and ask them to send the hooligans on their respective payroll over to smash some stuff until taxes flow again.

And the mayors do that because a) it is socially a bit awkward and dishonerable to be a traitor and b) if they don't the king goes to the 8 surrounding towns and promises them half the taxes for themselves. Personal connections, personal profit and a general aversion to risk and danger are what holds this together.

The army is there as a loyal core the monarch can always rely on. They have to face the risk of a small revolt turning into a wildfire much less often if they can nip small stuff by themselves without calling in others. But it is also something a shortsighted miser would be perfectly fine cutting short.

PS: And regarding police since I also saw that brought up: With those numbers you do not do rule of law. If you get a cow stolen you don't go to the police, you take some mates and discuss the matter with whoever seems to have a lot of them. You are doing rule of whatever is socially acceptable enough to not get more people than you can take on to go after you.

This system seems to be similar to the latter stages of the ancient Icelandic Commonwealth, in which the Icelandic people themselves dealt with their own enforcement of laws. Pretty much every matter of law enforcement was a matter of money, with the criminal being liable to the victim (or a representative victim if the crime was against all citizens) for the cost of restitution and enforcement, and investigators could be paid from the debt incurred by conviction of the criminal, assigned by the victims of the crime. Criminals who couldn't pay the debts they had incurred on being found guilty were enslaved and made to work off their debt, or were outlawed and could thereafter be killed without penalty.

In a system like this, a centralised government would not need much of an army of their own, since there would be people who made it their jobs to enforce the laws without the need of official intervention. For the most part, the government would just make the laws known to the people and sit back and watch them take care of things for themselves. An army or police force would basically be the governors' bodyguards... and how much of a bodyguard does someone who doesn't do all that much really need? It depends mostly upon how many enemies he has made.

In time of war, even military service is a matter of duty for the people, who must either go to fight themselves, or pay others to fight for them. Again, the governors hardly need to lift a finger to muster their own army.

What I cannot figure out, is how this administration which is incredibly stingy, miserly and averse to spending, is maintaining order or even getting people to recognise their authority while still hoping to cut spending.

Sheer luck.

A triple digit figure army and a double digit figure police force against a million citizens lasts only until the first [gaseous corporal emission] is emitted in their general direction.

Nobody likes to work under budget cuts, and I have the gut feeling that those forces are equally ill equipped, maybe with equipment bought online from some shady ecommerce site with dubious customer reviews.

"If the government pretends to be paying me, I will pretend I am working for them" is what aptly describes the state of the forces of this nation.

Han Dynasty China might have some suggestions. 'Wu wei' is a central tenet of Daoist philosophy, most notably in the Dao De Jing (attributed to Laozi) and the Zhuangzi. It advocates a spontaneous and natural way of living, free from excessive desires and artificial rules. This is sometimes phrased as 'take no unnecessary action'. This does not mean the ruler should do nothing, but the best government is the one that allows things to happen of themselves. There are more modern parallels with the strategy of 'Positive non-interventionism' durning the British occupation of Hong Kong after WWII.

Your technological society will have digital banking, digital checks of identity, and other tools that may allow people to trade with confidence with someone they have never met even though the actual identity of the other person may be hidden. If someone violated the conditions of the society, their online identity might be withdrawn until reparation had been made. This would mean that someone would have difficulty trading. They could still barter, and exchange goods for services; but people might be suspicious, and charge them a premium for the additional risk of dealing with a dodgy person.

This would seem to fall in with 'wu wei'. The system re-enforces a broad 'proper way of living' by granting trusted status, and punishes anti-social behaviour by withdrawing this status. This is not the rigid laws of Confucianism, but a willingness to let anything that was working to carry on doing so. A spectacular example was the Kowloon Walled City where a separate and relatively lawless enclave within Hong Kong was allowed to thrive.

Such a system might see the existence of a large police force as a sign that it was failing its philosophy, as well as spending more money than it needed to.

Privatized Law & Order

The reason the government is able to spend so little and still maintain order is that it leans heavily on private/mercenary security and paramilitary companies to do all that for them. To avoid the government having to pay for these services, the system is set up so that communities pay for it themselves, like a form of national security insurance, and it's required by law for them to do so within the metropolitan areas. And on the fringes of society where things like bandits and brigands are more common, what are you going to do - not pay for police protection?

This of course begs the question of what's to stop these companies from simply taking over and becoming the rulers themselves, and to that, the answer is, practically speaking, nothing whatsoever. But there is also the question of why they would want to when they essentially already have all the power and are already raking in the cash without having to worry about such things as the logistics of running a nation. As long as they play nice with the central government, act as their lap dog every once in a while, and show deference to the government's army and military "elite forces" on the rare occasion the government does decide to personally step in (though everyone knows they are comically inept), they can enjoy a leisurely and highly profitable existence.

The real danger is, of course, what happens when a rival nation comes along and offers to pay them double to just stand aside...

Inertia

As Machiavelli pointed out in his influential (if often forgotten about) retrospective on Roman politics, one of the most important contributors to social and political stability—especially as relates to Roman-style societies—is civic virtue (what the Romans called virtus). It is especially important in weakly-governed societies such as yours.

When your postmodern Rome first began, it had a truly impressive military, generally seen as unbeatable. As part of this military culture, politicians made a point of leading from the front. This inspired a great deal of loyalty from their soldiers, and thence the common citizenry. More importantly, these warrior-senators set a standard: all citizens must be willing to put the good of the State above their own. Over time, Postmodern Rome™ became the major superpower in its continent/world/tri-state area. This spread a culture of pax Post-Romana: the unquestionable belief that Postmodern Rome is the font of peace and civility, albeit a peace and civility that carries a very big stick.

Of course, Postmodern Rome is no longer what it once was. While everyone still speak of pax Post-Romana and revel in the glory of the Empire's might, nobody's really willing to go out and put themselves in the line of fire to protect civil society. That's for other people, people who don't have so many important commitments at home. As a result, the Empire's military and civil service have gradually faded away into obsolescence, with only a very small number of largely-ceremonial (albeit still exceedingly well-trained and -equipped) professional soldiers remaining.

Nevertheless, the fact remains that people still pay lip service to the old virtues, even if only in a very vague and fuzzy way. As a result, it doesn't matter that the central government is barely a shadow of its former glory. All the regional governors know they can overthrow it with ease—but it isn't worth the trouble. The central government's too caught up in its decadence to care what the governors are doing, and in any event couldn't do anything even if it did. So long as the Emperor doesn't try to throw his weight around, the governors are perfectly happy to pay lip service (and the occasional small tribute) to him in exchange for the legitimacy doing so gives them.