Say you have a multiplayer-only game in which players are randomly paired head-to-head against a random online player...
How do get such a beast off the ground?
You need enough players online at all times such that any random player game request will be paired with someone else's request.
Chicken and egg ... You need players to play but without players to play no players will play!
How do I reformulate the problem to make this work?
This happened to me a while back and I haven't come up with anything useful since. https://github.com/fictorial/Rock-Paper-Scissors-World-Masters-iOS