Judgment-free construction of a playlist

Question

Alice and Bob are planning a long car trip and need to come up with a playlist for it. For any given song, they have one of four opinions on it: "That's, like, my favorite song ever" (love), "I like that song" (like), "I'll listen to this, but you owe me" (tolerate), or "I'd rather poke my eardrums out" (hate). To best respect each other's preferences, here's the rules they agreed on for which songs make it onto the playlist:

Alice \ Bob	Love	Like	Tolerate	Hate
Love	Yes	Yes	Yes	No
Like	Yes	Yes	No	No
Tolerate	Yes	No	No	No
Hate	No	No	No	No

But here's their dilemma: they're both very self-conscious of their tastes in music. In particular, Alice is worried that Bob will judge her if he finds out that she loves a song he hates, and vice versa. Thus, neither person should learn any more than necessary about the other's opinion of songs that don't get added to the playlist. (For songs that do get added to the playlist, it doesn't matter whether or not they learn each other's exact opinions.) Given a certain song, how can they figure out whether to put it on their playlist, without needing a trusted third party or computer?

---

Clarifying what can and can't be revealed:

• If Alice hates a song, she must not learn anything at all about Bob's opinion of it.
• If Alice tolerates a song and Bob doesn't love it, she'll learn that he doesn't love it, but she must not learn anything about his opinion of it beyond that.
• If Alice likes a song and Bob either tolerates or hates it, she'll learn that his opinion is one of those two, but she must not learn which.

And ditto swapping Alice and Bob's places. If I didn't say something can't be revealed above, then it can be revealed.

---

Another clarification: Alice and Bob will both cheat if they can, as long as doing so doesn't prevent the other person from ending up with the correct answer at the end of the protocol.

Answer 1

I've tried to anticipate some nitpicks at the process I present below. Nitpicks are in parentheses and set off from the main method. The core of the method can be found outside the parentheses.

Set-up step:

Alice and Bob should construct some sort of balance. The actual form this balance takes doesn't matter, as long as it's fair and can have a container attached to either end. They'll also need to procure two identical, opaque containers, for that matter. One container (Container A) has a 7g weight placed in it.

(If it's impractical to assume that they have perfect weights, then I hope it's practical to assume that people have objects of identical weight. The method really only needs a mass of 7X - could be 7 batteries, 7 candies, 7 refrigerator magnets, etc.)

Then, they should follow these steps for each potential song:

1. Alice drops a number of 1g weights into the other container (Container B) corresponding to how much she enjoys the song. Hate = 0g, Tolerate = 2g, Like = 4g, Love = 6g. Bob follows suit. Neither looks inside the container when doing so, and let's say the containers have padded bottoms so you can't hear how many weights there are bopping around in it.
   
   (If "don't look in the container" is a rule that they can't be expected to follow, say the containers have only a small hole at the top that's just big enough to put in a weight. And the inside is dark enough that you can't see what's inside. This isn't actually that hard to construct; take a smaller cardboard-shipping-box, cover the bottom with cheap foam or a pillow, and cut a little hole in the top. But I digress)

2. Now, one of them (Alice, say) holds the balance in place so that it can't tip either way. Bob attaches Container A to one side and Container B to the other. Alice releases the balance. If Container A is heavier, then the song doesn't go on the playlist. If Container B is heavier, then the song goes on the playlist.
   
   (If Bob might be able to guess the weight of Container B when he's transporting it, then let's say we stick an extra 1kg weight in both containers. Telling, say, 1.002kg apart from 1.006kg is much harder than telling 2g apart from 6g. But perhaps the weight of the containers themselves is enough to block this.)
   
   (To address the comment-nitpick that you can tell the relative masses by watching the balance: Alice and Bob should get a big box. Or create a big box by cutting up smaller boxes and duct-taping the parts together. Or get four pole-supports and a blanket. Then they can block the balance from sight, by placing the box over it or using the supports to cover it with a blanket. They'll do this after the containers are attached. Instead of Alice holding the balance, they rejigger it so it can be held in place with a stick poked in the appropriate area - I can draw a picture, or you can just imagine it. It's possible. Anyhow, they jigger the balance steady with a stick, place the containers on either side, fit the box/blankets over (perhaps they have a small hole for the stick to poke through), and remove the stick. Now they wait a minute or so to make sure the side that would tip has tipped completely, before removing the box/blankets.)
   
   (Yes this is overkill. But they wanted secrecy!)

3. Now they repeat. Either they get a fresh Container B, or one dumps the weights out without looking into it or counting the weights as they tumble out.
   
   (For an actual procedure to prevent peeking, say that my proposed cardboard-shipping-box with foam on the bottom and a small hole on top is used. Say the hole on top has about double the radius of the weights. Simply have Alice watch Bob to ensure no cheaty-looking, and then Bob upturns the box over a container with many, many other weights already. Then the weights will tumble out properly without anyone being able to look or count)

Why does this work?

Let's look at a table of how much mass would be added to Container B for each possibility

| Alice \ Bob |       Love       |       Like       |     Tolerate    |       Hate      |
| ----------- | ---------------- | ---------------- | --------------- | --------------- |
| Love        | 12 (> 7 → tip B) | 10 (> 7 → tip B) | 8 (> 7 → tip B) | 6 (< 7 → tip A) |
| Like        | 10 (> 7 → tip B) | 8 (> 7 → tip B)  | 6 (< 7 → tip A) | 4 (< 7 → tip A) |
| Tolerate    | 8 (> 7 → tip B)  | 6 (< 7 → tip A)  | 4 (< 7 → tip A) | 2 (< 7 → tip A) |
| Hate        | 6 (< 7 → tip A)  | 4 (< 7 → tip A)  | 2 (< 7 → tip A) | 0 (< 7 → tip A) |

Or, in a wordier form:

This method provides no information to either Alice or Bob besides tip A or tip B. Seeing as "tip B" equals "song on playlist" in all cases, and visa versa for A, what they learn is perfectly equivalent to what they would learn from the song being on the playlist, and nothing more.

Answer 2

I have a proposed process, which has the downside of allowing for cheating, but works if both sides want to keep the information transfer within the outlined parameters:

For each song, Alice gets 4 index cards, each with a different one of "Love", "Like", "Tolerate", and "Hate" on them. On the other side of each card, she writes (without Bob looking over her shoulder) whether the song would be included if that card's front side is Bob's opinion (eg if Alice tolerates a song, she'd write "No" on all the cards except "Love"). Alice then leaves the room. Bob looks at the card for each song corresponding to how he feels about the song, and adds the song to the list if it says "Yes" on the back. Bob doesn't look at any card that doesn't match his opinion of the song. Once Bob is done, one of them disposes of the cards without letting him see anything else on them.

This works because:

Alice learns nothing until she sees the final playlist, so she clearly isn't learning extra. Bob, assuming he doesn't cheat, only learns if a song should be on the playlist or not, which is unavoidable anyway.

We can modify this to enforce the secrecy better:

Alice instead places cards/paper with Yes or No inside 4 envelopes per song, with each envelope labelled on one side as above. Instead of leaving when Bob comes to select, Alice simply closes her eyes while Bob shuffles the envelopes and selects the appropriate one (while Alice listens to make sure Bob isn't opening any). Once he's selected it, he holds it such that Alice cannot see the label, then opens it, notes whether it says yes or no, then the process repeats. At the end, Bob disposes of the envelopes while Alice listens to make sure he doesn't open any. This has all the same results of the method above, but Bob can't learn any additional information without Alice catching him cheating.