The sidequest begins in the Grand Hall. A fisherman by the entrance offers you a rare Pokémon for 500, but after paying for it, a street rat nearby overhears the conversation and snatches it from you on his way out. The chase begins!
To the left of the door to the desert is the location of the thief who stole your Pokémon. Upon confronting him, he demands 500 before giving it back. Paying this amount results in him revealing that he and the fisherman that sold the Pokémon actually worked together to scam unsuspecting trainers, and dare you to defeat them to retrieve your purchase.