Conveying the intuition behind basic differential privacy mechanisms using games? Yes please! In a previous blog post, we looked at DP VISION: it had a fairly simple optimal strategy, and was a great opportunity to do some privacy auditing.

The folks at Oblivious also developed two other games. One of them is a DP twist on the well-known Wordle, called WORDPL. The goal is to guess a 5-letter word based on successive clues, except the clues are randomized. Here's what the game looks like, with just a single round.

Here, we chose the word "magic" as our first guess, using a privacy budget of \(\varepsilon=4.2\). The clues we got are suggesting that:

• the letter "m" is part of the secret word, but not in first position;
• the letters "a", "g", and "i" are not part of the secret word;
• the secret word ends in a "c".

Except that all this information is unreliable: every clue is randomized with a randomized response mechanism! The budget is split across the five clues, there are three possible kinds of clues, so the chance that each clue is correct is \(\frac{e^{\varepsilon/5}}{2+e^{\varepsilon/5}}\). With our \(\varepsilon=4.2\), we'll get an incorrect clue almost half the time. This makes guessing a lot harder. Try it out!

Each round, the privacy budget consumption is added to a total. And the goal is to find the correct word with the smallest possible total budget.

So. How do we get on top of the leaderboard? And can we find an optimal strategy like for DP VISION?

Spoilers: we win this with some ✨ math ✨, and finding an optimal strategy seems really hard. So instead of answering that last question, I made it into a contest… and I'm hoping you can do better than I did!

Beating the high score

First off, some technical details about the game. There are two word lists, which we assume are known, and the same as the original game¹.

• One contains the list of valid guesses. These are words that the player is allowed to use.
• One contains the list of possible solutions. This is a smaller list of words that can be chosen by the game as the secret word. (This is to make sure that the solution is likely to be words known to the player, so not too obscure.)

In Wordle, when you guess the secret word, you win the game instantly. WORDPL works the same way, and (contrary to the original version) does not limit your number of guesses. This introduces a kind of vulnerability: we could just guess every possible word with \(\varepsilon=0\) and we'll eventually find the right one at no privacy cost. This is not very fun, so we're not going to do that. Instead, we're going to learn about Bayesian inference! Which is much more exciting. (I am a lot of fun at parties.)

Applying Bayesian inference

The idea is simple. We have a list of possible secret words. We will associate each one to a subjective probability of this word being the solution to the game. At the beginning of the game, we have absolutely no idea which is the right one. So we are going to assign the same probability to every word.

When we guess a word, we get five clues back: one for each letter. These clues may be incorrect, but they are still going in the right direction. Let's take the example above, where we guess "magic". The first clue is that "m" is part of the word but not in first position. So the words that match this clue are more likely to be correct that the ones that don't. We have to update the subjective probabilities in a way that looks like this.

A single word gives us five clues, so we repeat the process for each letter. The second clue tells us that the secret word is more likely to not contain the letter "a".

And so on. Now, how much should we update each probability? This is exactly the question that Bayesian inference answers. For each possible word, Bayes' theorem tells us that:

This looks scary, but has a pretty simple explanation.

• \(P(word | clue)\) is the updated probability (the posterior) of the word being the secret answer, taking the new clue into account.
• \(P(clue | word)\) is the probability of observing the clue, assuming that the word is the secret answer. The randomized response formula tells us that this is \(\frac{e^{\varepsilon/5}}{2+e^{\varepsilon/5}}\) if the clue is consistent with the word, and \(\frac{1}{2+e^{\varepsilon/5}}\) otherwise.
• \(P(word)\) is the prior probability: our previous estimate of how likely it was that this word was the answer.
• \(P(clue)\) is a constant factor which guarantees that all the updated probabilities sum to 1.

This gives us the first part of our strategy: we are going to try a few guesses, use the Bayesian update rule to figure out the most likely answer, and try that answer. The question is: how do we choose which words to guess, and how much budget do we use for each?

Choosing which words to guess

Finding good guesses is what the strategy for the original Wordle game is all about. Luckily for us, other people have already solved this problem: there are known optimal solutions. This suggests a really simple approach: just use an online solver to guess the first \(k\) words (for some arbitrary \(k\)), then pick the highest-probability solution as the next guess.

There is no reason to believe that this is also optimal for the DP version. In fact, sometimes, it doesn't work at all: for example, the first two guesses can give us incompatible clues. This can't happen in the original game, but can happen in WORDPL due to randomization. So if we pick \(k=3\), sometimes the solver won't give us a third suggestion of a guess, because we're in a situation that couldn't happen in the original game.

But this is still a somewhat reasonable approach. These solvers attempt to explore the search space as efficiently as possible. Typically, they suggest making guesses that are very different from each other, to learn as much information as possible in the first few rounds. This high-level goal still translates to the randomized setting. Probably.

OK, what about the choice of privacy budget?

Choosing the privacy budget

I decided to aim for 3 guesses and a total budget of \(\varepsilon=10\): it's nice and round, and a decent improvement over the previous best score of \(\varepsilon=12\). I gave more budget (\(\varepsilon=6\)) to the first query, in an attempt to make the solver go in the right direction to select the next guess. Then, I used \(\varepsilon=4\) to the second guess, applied the Bayesian update rule, and picked the most probable secret word (with \(\varepsilon=0\)) for the final guess.

This strategy does not have a high chance of success. But it's still pretty decent, so after a few dozen tries…

Hell yeah.

Now, this is not very principled. And it's clear that chance has a big impact on the results: if you've played the original Wordle enough, you probably got lucky once and got the right word in 1 or 2 guesses, even though there were plenty of other possibilities! If sufficiently many people start playing WORDPL, this will certainly happen at some point.

Optimal strategy contest

This got me thinking: what if there was a version of the game that evaluates and rewards good strategies, as opposed to individual runs? I thought that was a fun idea, so I built it. And I'm challenging you to submit a strategy that beats the (fairly naive) ones I've implemented there.

Silly strategies, like running a ton of guesses with very low \(\varepsilon\) until we find the right one by chance, are not very fun. To prevent this, I changed the rules a little: the game has now two phases.

• In the first phase, the player submits guesses and \(\varepsilon\) budgets, and gets back randomized clues. They can submit as many guesses as they want. If they submit the secret answer, the game does not stop! Instead, they get a randomized clue as normally; the real clue being "everything is correct".
• In the second phase, the player submits a final answer, without any budget attached. If this answer is correct, they win; their score is the total budget used in the first phase. If this answer is wrong, their score is \(+\infty\).

To evaluate results, I run the strategy on 1001 games, and compute three distinct scores: the 5th, 50th, and 95th percentile of the scores. They attempt to capture different high-level goals.

• The 5th percentile rewards strategies that aggressively try to get a correct answer on a tight budget, at the cost of failing often. This models a player that tries to have one lucky run and get on top of a public leaderboard, and is willing to play approximately 20 games for that.
• The 50th percentile (or median) rewards strategies that have a solid chance of giving the right answer, though they're still allowed to fail quite a bit.
• The 95th percentile rewards strategies that only submit an answer once they have a high level of certainty that this is the right one.

I implemented a simple variant of the strategy outlined above. I'm pretty sure someone could do better. And to encourage you to try it, I am hereby promising to ship a chocolate bar from my favorite chocolate shop in Zürich to each player who gets a 5% improvement or better on one of the three scores.

Can you do it? 👀