This was discussed briefly in #bitcoin-dev. It's actually possible using game theory.

Use infinite prisonners dilemma of evildoers vs collaborators (basically you need to guess the others strategy mid-game). Whoever is ultimate winner in a round (everyone can replay the game to verify the "proof of game"), mines the block. Generalized poker.

Some notes:

* You need chips to play with - for the sake of simplicity no PoS for now, still use SHA256 pow as base currency. Big miners will have lots of chips to play in the round. However being rich is useless, if you don't know the intricacies of playing poker ... basically even small group of sha256 miners has a chance, if their game algo is much more sophisticated.

* Spiking NNs need massively shared memory, such computing clusters are forced to cooperate, (T=4 will beat all T=2 powerful brains, one by one).

* The fact anyone can be double (to N) agent is part of the game

* There might be problem that you might end-up with megacorp vs secondary megacorp (think Dems vs Reps and the rivalship is just theater), but i doubt it.