An immutable blockchain record would seem to be appropriate? I will let you come up with a suitable name for such a chain (and the corresponding coin).
We could also solve cheating by representing romantic interest as an NFT which can be traded from one partner to the nest, with hotels and restaurants only accepting two-person bookings from couples who are confirmed as owning each other’s tokens!
#TechnicalSolutionsToSocialProblems