Harmony of the Spheres 2: The Tinkering Begins

 

As soon as I saw that beautiful cornucopia of a graph that we talked about in the first Harmony of the Spheres problem, I wanted to tinker. What would the graph look like if it was only two simultaneous notes, or four? What if we split the octave into eleven or thirteen semitones?

There’s two major variables at play here: the number of different tones and the number of simultaneous voices. Let’s call them t and v; t for tones, and v for voices. Each combination of t and v should give us a different graph. Like before, each node is a possible set of notes; a sound the group could be making. Each edge is one voice moving up or down one note; if one combination of notes is being sung, and one person decides to move up one note, they’ve moved the sound from one node to the other, along an edge.

Ideally, we’d want to have a system in which we know what the graph looks like if we’re given t and v. So let’s try to find one. Let’s start way down low, at the basics, and build out this set of graphs. If t is one, it doesn’t matter what v is, because all of the voices have to sing the same pitch (the only pitch that exists). And the order of the voices doesn’t matter, so those graphs have exactly one node. Which is the most boring graph possible.

If v is one, then that voice can sing any of the tones in t. But, under our rules, the pitch doesn’t matter, either – what matters is the relationships between the tones. Therefore, these graphs will also only have one node.

Now, the first non-trivial case: 2 x 2. Two tones, two voices. Let’s start with both voices on the same tone. That’s our first node, and then… something interesting happens. Moving one voice up or down to find another node, no matter how we do it, seems to bring us to the same new node – the node in which the two voices are different.

A hard example could be helpful here. Imagine two people, Alice and Bob, taking a break from writing ciphers, and two notes, C and D. The way this musical scale works is that there’s only two notes in the octave, C and D. If you sing one note higher than D, it’s a C. One note down from C, it’s a D.

So we started with both Alice and Bob singing C. That’s our first node. Then, Bob decides to sing one higher while Alice stays on C, and by our rules, that’s an edge to another node. Now Alice is on C, and Bob is on D. New node. But now, no matter who changes their note, and in what direction, we’re going to end up back at the first node!

If Bob goes down, they’re both at C again. If Bob goes up, he goes up to C. If Alice goes up or down, she goes to D, the same note that Bob is on, and remember, we only care about the relationships between the notes, so D+D is the same as C+C! And if we try to go to a different node from the first node, we quickly find that C+D is the same as D+C!

I'll keep track of the ones we've done in a table, like so.

 

Not very interesting so far – we’ve just shown that if there’s two tones and two voices, they can sing either different notes or the same note, and that’s it. But as we add more voices and tones, things will get very complicated, fast!

Birthday Puzzle 2020!

Hello, and welcome to my birthday puzzle, 2020 edition! A big, elaborate puzzle on my birthday is one of the few traditions I've been able to keep up with, and this year I'm posting the puzzle here rather than Facebook, to make it more accessible.

My earlier puzzles have been difficult, sometimes to the point of extreme frustration. Sometimes they required the solver to notice a very small detail just to progress, or they gave the impression of being so polished that any mistake was surely something I did on purpose. As you can imagine, this was stressful for everyone, myself included!

So, I am happy to say that I’ve taken a step to de-escalate this year. My 2020 birthday puzzle is meant to be enjoyed by children and adults alike. I’ve taken a leaf from the oft-underappreciated puzzles that grace cereal boxes and restaurant coloring sheets to create my own series of simple puzzles, enjoyable by all. And if there’s a little mistake or seemingly important detail here or there, I’m not too worried about it!

The old Spandan would have cut it off there and left you with no idea where to begin, but I can’t do that in good conscience. So, I’ll give you a quick summary of the puzzles and what you need to do to succeed! The first puzzle is a fill-in-the-blank game – all you have to do is find out which letter is missing, and then use the letters to solve the tricky bonus question. The second puzzle is a search and find, because I’ve cleverly hidden coins around the puzzle sheet, and only a keen eye will be able to find all of them. Watch out, though, some coins are hiding together! The third puzzle is a maze, with a twist! Instead of just finding your way to the end, you have to collect coffee for your friend. If you want to try the bonus puzzle, pay attention to the letters you come across! And finally, the last puzzle that ties the rest together is the word search. Find the words in the word bank – you’ll notice they’re all kid-friendly words, nothing adult there. The big, empty box is for the secret phrase I’ve hidden in the word search.

And, that’s it! I hope you enjoy the fresh new aesthetic, and the kid-friendly puzzles!

Here's the puzzle!

https://drive.google.com/file/d/1yLeXVunFnrXJVZ6MP7PjoCvq7sJFlzGx/view?usp=sharing

Pig II: Disproving Pigs

Last time, we talked about the Pig problem – a hypothetical cooperative game in which players don’t have all the information, and it is a rational choice to not give all the information out to the other players, despite it being a free action. Pig stands for Purposefully Imperfect Information Game, so we’ll call a game that satisfies these rules a Pig.

So, now we have to think about what kinds of things need to happen for a Pig to exist. The main thing we need is for rational player A to decide not to give rational player B information that is exclusive to rational player A. For example, if the game involves hands of cards which are kept secret from the other players, there’s gotta be some scenario where player A doesn’t want to tell player B their cards, despite them all working towards the same goal.

On the surface level, this seems impossible to me. Bad decisions in games are made with imperfect information, and the more imperfect the information, the worse risk you run of making a bad decision. But that’s not a good enough argument – it implicitly assumes that more knowledge is better, and that’s what we’re trying to prove.

So I bounced around some ideas with a friend of mine, and we hit upon something critical. A perfect player can simulate not knowing something. If you’re playing poker and one of your opponents accidentally drops a card, you can’t erase the knowledge of what that card was from your mind, but you can play in such a way that pretends you didn’t see it. It’s difficult for humans to do it in a lot of cases, because of biases and human imperfections, but our idealized and perfectly rational player could do it.

So, a perfect player can simulate knowing some subset of what they actually know. They can calculate the best course of action for a different situation than theirs, and that’s the key point that proves that a Pig cannot exist in this form. The proof is actually pretty simple once you have this point clear.

Proof: Let’s start with a game involving n players.

Case 1: All of the information in the game is known to one player or the other – so, if they tell each other everything they know, they know everything about the game. There’s nothing that will be revealed later in the game.

Let’s define a game G as the game with the players sharing and hiding information to make the game have the best possible outcome. So, if player A thinks they should share half their information, and player B thinks they should share none of their information to get the best possible game result, they do exactly that. That’s our definition for G, the “optimal” game.

Now, let’s construct a game G’, in which all players immediately share all information. Because players have the ability to simulate playing the game as if they only know a subset of what they knew, they now have a myriad of strategies on how to play. For example, if there’s two pieces of knowledge each for two players, they can play in sixteen different ways – each player knows their own information, but there are sixteen possibilities of how much they know about each other’s information.

If there is information that players shouldn’t have shared, all players know and agree on it, because they’re all perfectly rational. So, one or more of these ways to play the game – one combination of known and unknown information – is optimal, and everyone agrees on it. By definition, this is G, the optimal game. And suddenly, we’re done. Anything the players can do by sharing and hiding information, they can also do by sharing all information, deciding what information to share and what to hide, and simulating that knowledge. Therefore, the "sharing all information" solution, G', will always be at least as good as the players’ best ideas on what to share and what to hide.

Case 2: Some information is not known to the players, and may or may not be revealed throughout the course of the game.

This case turns out to be very similar. We can again define G as the optimal game, and G’ as the construction of sharing all knowledge, deciding on the optimal strategy, and simulating knowledge. But in this case, the game isn’t solved immediately. There will be new information revealed to the players, who may have to chose to hide or show this information. But we can just repeat our process of showing all information, deciding on a strategy, and simulating knowledge each time information is revealed. Therefore, at every step, G’ has access to every possible combination of players’ knowledge and lack of knowledge, so one of those possibilities must be G.

And that’s it. Pigs cannot exist, as we’ve defined them. But that doesn’t mean we’re done here. On the contrary, I was very relieved when I nailed this proof down, because that means I can finally start tinkering! More on that next time!

Purposefully Imperfect Information (Pig I)

I don't know much about game theory (just like every other branch of mathematics with a name, haha). Game theory was always an afterthought in the classes I took – tacked on to the end of discrete math, or mentioned briefly in a problem set. But I play a lot of games, and I see interesting mathematics arise from them. 

The kinds of games I’m talking about are very idealized. You’ve got players, who are perfectly logical and rational, you’ve got some sort of win condition, which might be different for each player, and you’ve got some type of allowed actions or events set to happen which offer the players a choice. Games can have perfect information, like chess, where every player knows everything possible about the state of the game, or not, like poker, where you don’t know what cards your opponent has. There’s competitive games, where each player is self-interestedly trying to win, and cooperative games, where players have to work in teams or all together to win. Cooperative games lead to “super-rationality” and other interesting concepts, and that’s what got me thinking about this hypothetical and a strange question.

Hypothetical: Let’s say you have a cooperative game between players with some high level of rationality. Perfectly rational, super-rational, theoretical rationalities, I’m not sure yet. This game features imperfect information, so certain players will know things other players will not. Finally, communication between players is a free action. 

Can you picture the game? Here’s a quick example. You and three others divide a deck of cards into four hands of thirteen cards each, and each player can see their hand. Each player takes a turn passing or playing a card onto the table. The goal is to play all cards, in order, into four separate stacks sorted by suit (like the goal of solitaire) with as few passes as possible. And you’re free to talk to the other players about your hand whenever you feel like it.

Simple enough, right? You and your friends are rational, you don’t have all the information, talking is free, and you’re working together to sort the deck. This is the kind of game I’m talking about.

Now, the question is: Is there a game that satisfies these rules in which it’s not optimal to give out all the information you know?

In the example above, the best strategy would just be to show everyone your cards, and decide together what to do. In that game, more information means you will always make better decisions, and the players are all identically rational, so everyone would agree on a best way to play, and play. But is there a game where more information, maybe even perfect information, could make a rational player play worse than a game with limited information?

I don’t actually have an answer. I’ve got some ideas, but no answer just yet. Interesting, isn’t it? Interesting enough for a name, I think. Such a game would have players purposefully hiding information about the game from their people who are supposed to be on their team... so... Omission? Censoring? Purposefully Imperfect Information? Oooh, I like that one, because Purposefully Imperfect Information Game abbreviates to PIIG, which "abbreviates" to PIG, with some artistic license! Henceforth, this shall be known as the Pig problem! Until next time!