Sí que se puede...
Lo que hay que tener un poco de suerte XD
Os meteis en una sala de chat (ajena al juego, o sea, del menú XMB) y os compenetrais para darle los dos a buscar rival al mismo tiempo.
Es la única forma, si hace falta intentadlo unas cuantas veces