smooth also added the very clever point that in the case Proof-of-Stake devolves to a computation contest for computing Nothing-at-Stake game theory, then this is perhaps a Proof-of-Work system in disguise (and I add but it might still also have some of the bad traits of Proof-of-Stake as well)
Pos is weighted proof of work.
The problem with the current PoS systems is that they hand out rewards (block rewards and fees). PoS without rewards and a deterministic preference function doesn't suffer from "nothing at stake", because, well, you don't care.
If you have a PoS system where there is no need for a regulation in the speed of blocks, because there is no block reward, and if you have a preference function that is:
1) slightly more than proportional to total coin-age, and proportional to number of transactions included
-> meaning, a chain with a transaction included is always preferred over an otherwise identical chain with a transaction not included
-> meaning that replacing a transaction by an earlier transaction of the same coins ("earlier double spend") is always going to be refused
-> meaning that putting in a later double spend of coins that have already been spend afterwards, is going to eliminate so many transactions that it is going to lose too.
2) has a random order of preference between chains that have identical outcomes for (1) solves the "nothing at stake" problem because one chain is preferred over another one
3) has, at each block, a random order of preference for stake holders to sign the block
I'm pretty sure you have mostly a unique solution to the consensus problem, and those "false variants" that may be propagated have very little chance of coming into existence, because minters don't mind minting, but are not keen on minting either, and are most of the time, not motivated to making false chains: they can only harm the system in which they have a stake. As there is no rewards, there are no strategies apart from trying to double spend, and the odds that you can do it because you happen to be the preferred staker on the false chain are small.
There can be regular "multi-stake checkpoint signing" events if ever the probability of double spending is not small enough, but I don't even think it is necessary.