The Magic Tournament Rules specifically state 'For the first game of a match, the winner of a random method (such as a die roll or coin toss) chooses either to play first or play second'. My method of choice has often been Rock-Paper-Scissors, but it never occurred to me until recently that this might not be considered a valid method under the rules. Obviously this question is more hypothetical than not; if my opponent disagrees with my method of randomization then a different option, or a judge, would be called for. But at least in theory, spectators or judges watching our match could complain, so the question holds: is RPS (likely to be) considered a 'random method' for determining play/draw under the tournament rules?
My understanding is that it's really up to the judge.
The tournament rules just say this:
They don't really specify a more detailed criterion for "random." (For example, cutting to a random card of each other's decks and then comparing their mana costs is a method players use some times. It's random, but it's not actually fair: the CMC of various cards in your deck skews the results.)
My first assumption was no rock-paper-scissors, since RPS is a game that permits some level of psychological skill. However, here's a quote from an old tournament report:
Note that it was the opponent who decided RPS was insufficient, not a judge. This implies that RPS might've been acceptable if both players were fine with it.
In practice, I would expect low-level events not to care about the exact quality of the method you use as long as it's mutually agreeable to both parties (which is all the comp rules really call for), unless they've had to set up a specific system due to previous issues with cheating.