Сервер для android игры

Если игра тетрис, а сервер только для достижений и аналитики, то сокеты не нужны, они только усложнят, достаточно HTTP, на сервере PHP и MySQL, можно на первых порах даже на бесплатном хостинге, только домен купить чтобы потом не "потерять".
Если игра клиент-серверная, то да, VPS и сокеты, но можно обойтись и HTTP Long-Polling, поскольку на TCP довольно сложный алгоритм получится если требуется надежность при "обрывах" сети и т.п., многим это тяжело дается.
UPD: еще есть специальные сервисы, правда в основном лишь для конкретных задач вроде аналитики или push-уведомлений, и не бесплатные (или с ограничениями).