Вы когда подключаете любого игрока к серверу, на сервере отмечайте, что он онлайн. Далее при необходимости ищете в своем списке онлайн-игроков и высылаете ему приглашение.
Упрощенно подключение:
1) Подключить игрока к серверу.
2) Внести его id в список онлайн.
3) Установить ему статус "вне боя"
Упрощенно поиск соперника:
1) Посмотреть в список онлайн, найти первого у кого статус "вне боя"
2) Создать комнату для боя, поместить в нее обоих участников
3) Обоим участникам выставить статус "ожидает боя".
4) Отправить приглашение обоим участникам.
5) После согласия обоих участников - выставить обоим статус "в бою" и начать бой.
Детали реализации и выбор технологий подключения к серверу, хранения сессии, вопросы обновления информации сессии и ее актуальности (до сих пор ли игрок онлайн) - оставляю за рамками этого ответа. Вероятно у vk-api есть какие-либо способы узнать о том, онлайн пользователь или нет. Но скорее всего придется реализовать самому.