Paper is the best choice for the first "shoot". Everyone picks rock because they forget what they're supposed to do, so pre-empt their stupidity and use paper (be cautious of "scissors" type people).
If someone is actually using paper against you and winning, give up, they're too spontaneous and unpredictable.
What is "Paper"?
If you are unaware of what paper is, it's most likely because you were born after the year 2008. Paper is what people used to use instead of tablets, it was flamable and flimsy.