What about a queue system like with Chocobo Racing? Players queue up, and if no other players(/an uneven number of players) queue up, they fight an NPC.

This method by itself could still lead to easy win trading, since a win buyer and seller could just queue up when no one else was playing (although a third party could really ruin their day, if they saw the cheating going on).

To really put a hamper on cheating, you could set up tournament times. Say, an hour at a time, three or four times a day.

The obvious downside is that players would no longer be able to do the tournaments whenever they felt like. However, by limiting the times that tournament matches are available, you increase the number of real players available for matches, as well as decreasing (and possibly abolishing) win trading.