On Puzzles, Code, and Problem Solving

My first two posts here on the OSTP blog have offered puzzles about cooperative games, first for two players, and then a harder version for any number K of players. Besides being fun, these puzzles shed some light on how computer scientists think about facilitating cooperation across a network.

In the first puzzle, there are only two players, Alice and Bob, and there are only four possible strategies a player can follow: always guess heads, always guess tails, guess the same as your own coin, and guess the opposite of your own coin. Four strategies for Alice and four for Bob gives 16 total strategy combinations. If we want to know whether a strategy is guaranteed to win the game, we can simply check all 16 strategies against all four possibilities for the coin flip results (two possibilities for Alice’s coin, times two possibilities for Bob’s). An exhaustive analysis of 64 cases (four flip outcomes for each of 16 strategy combinations) can find a strategy that solves the puzzle, with no real brainpower required.

We can even write a computer program to do the search. For readers who are programmers, here’s my Python program to do it:

===

strategies = ['heads', 'tails', 'same', 'opposite']

coinsides = ['heads', 'tails']

def right(myStrat, myCoin, theirCoin):

    if myStrat==theirCoin:    return True

    if myStrat=='same' and myCoin==theirCoin:    return True

    if myStrat=='opposite' and myCoin!=theirCoin:    return True

    return False

def guaranteesWin(aStrat, bStrat):

    for aCoin in coinsides:

        for bCoin in coinsides:

            if (not right(aStrat,aCoin,bCoin)):

                if (not right(bStrat,bCoin,aCoin)):

                    return False

    return True

for aliceStrat in strategies:

    for bobStrat in strategies:

        if guaranteesWin(aliceStrat, bobStrat):

            print 'Winning strategy: Alice ', aliceStrat, ', Bob',bobStrat

===

In the second puzzle, where there might be any number K of players, there are exponentially many strategies possible, so there’s no hope of solving the puzzle by brute force computer search. Our only hope is to be clever. And that means human cleverness, because computers aren’t yet clever enough to solve puzzles like this from scratch. In general, whenever we need a mechanism to induce cooperation among a large group of people, we’ll have to be clever about how we design that mechanism. Here’s the cleverest solution I could come up with to the hats problem. (Do you have a better one? Let me know @EdFelten44!)

Real-world problems are even more challenging than these puzzles because, unlike in the puzzles, people might not all be playing on the same team. If people are trying to maximize their own profit or outcome, then we need the system to align incentives so that when each player maximizes their own outcome, the result is an equilibrium of cooperation – that’s a class of problems that computer scientists call “mechanism design.” The most difficult case is where one or more of the players, for reasons of their own, want to cause a bad outcome – that’s the basic scenario in “information security” or “cybersecurity” problems.

Of course, these aren’t only technical challenges. They’re policy challenges and social challenges too. That’s why the Administration is working to promote a free and open Internet here at home and around the world, joining with stakeholders to enable the conditions for computer scientists, policymakers, and anyone who’s interested to cooperate online to solve these challenges and bring the benefits of the digital world to everyone. And it’s why the Administration is taking action to support computer science education and empower everyone with the skills to leverage the capacities of computers in order to benefit humans.

Puzzles aren’t only fun, they’re also miniature versions of the big, important challenges that computer scientists, policymakers, and others are working together to solve. I joined the White House because I wanted to try to solve those challenges as part of a team – a team that includes people like you.

Ed Felten is Deputy Chief Technology Officer at the White House Office of Science and Technology Policy.