I’m inexperienced with UE4, but I wanted to help any other newbies by presenting a basic solution to this problem which took me a while to solve.
So, you want a simple multiplayer game, but the players seem to be spawning at random Player Starts. This means that half the time some of your players are not spawning! Here’s how to fix it:
Open your game mode. Hover your cursor over the plus sign next to ‘Functions’ on the left, select ‘Override’ and then click ‘Choose Player Start’.
Now, you can add logic to select an unused Player Start. You can create an array of actors and set it to the Player Starts array when BeginPlay is called in the Event Graph, like so:
Then, you can go back to your ChoosePlayerStart function and get the first item, setting it as the currently chosen Player Start as an actor variable and removing it from the array, so that it won’t be chosen again.
Of course, it would be easy to use a random number for the index when getting a Player Start from the array:
Now that you have the basic logic for a working system, you can improve upon it and adjust it to your needs. I hope this helps somebody 
Edit: this works fine when testing with a dedicated server. However, switching to a listen server seems to cause an issue that I haven’t managed to fix.
In C++, you can override the ChoosePlayerStart function with this:
Header
virtual AActor* ChoosePlayerStart_Implementation(AController* Player) override;
And then define the function so that it returns an AActor* in the .cpp file.
