I just ran across this, and though it would be perfect. For the first cruise, I remember the puzzle solving giving achievements. So we could go with the achievement and affinities ideas. To go along with the sticker idea, I give you: Polymer Clay Badges.
These could be embedded with something that would allow you to attach them to your badge lanyard, rather than the badge itself.