Functional Side Effects

You have probably heard the argument in favor of functional programming languages that functions act like functions in mathematics, and therefore have no side effects. When you call a function, you get an output, and with the exception of possibly the running time nothing matters except for the output that you get. This is in contrast with other programming languages where a function might change the value of some other global variable and have a lasting effect.

Unfortunately the truth is not that simple. All functions can have side effects. Let me illustrate this with Newcomb’s problem. In front of you are two boxes. The first box contains 1000 dollars, while the second box contains either 1,000,000 or nothing. You may choose to take either both boxes or just the second box. An Artificial Intelligence, Omega, can predict your actions with high accuracy, and has put 1,000,000 in the second box if and only if he predicts that you will take only the second box.

You, being a good reflexive decision agent take only the second box, and it contains 1,000,000.

Omega can be viewed as a single function in a functional programming language, which takes in all sorts of information about you and the universe, and outputs a single number, 1,000,000 or 0. This function has a side effect. The side effect is that you take only the second box. If Omega did not simulate you and just output 1,000,000, and you knew this, then you would take two boxes.

Perhaps you are thinking “No, I took one box because I BELIEVED I was being simulated. This was not a side effect of the function, but instead a side effect of my beliefs about the function. That doesn’t count.”

Or, perhaps you are thinking “No, I took one box because of the function from my actions to states of the box. The side effect is no way dependent on the interior workings of Omega, but only on the output of Omega’s function in counterfactual universes. Omega’s code does not matter. All that matters is the mathematical function from the input to the output.”

These are reasonable rebuttals, but they do not carry over to other situations.

Imagine two programs, Omega 1 and Omega 2. They both simulate you for an hour, then output 0. The only difference is that Omega 1 tortures the simulation of you for an hour, while Omega 2 tries its best to simulate the values of the simulation of you. Which of these functions would your rather be run.

The fact that you have a preference between these (assuming you do have a preference) shows that function has a side effect that is not just a consequence of the function application in counterfactual universes.

Further, notice that even if you never know which function is run, you still have a preference. It is possible to have preference over things that you do not know about. Therefore, this side effect is not just a function of your beliefs about Omega.

Sometimes the input-output model of computation is an over simplification.

Let’s look at an application of thinking about side effects to Wei Dai’s Updateless Decision Theory. I will not try to explain UDT if you don’t already know about it, so this post should not be viewed alone.

UDT 1.0 is an attempt at a reflexive decision theory. It views a decision agent as a machine with code S, given input X, and having to choose an output Y. It advises the agent to consider different possible outputs, Y, and consider all consequences of the fact that the code S when run on X outputs Y. It then outputs the Y which maximizes his perceived utility of all the perceived consequences.

Wei Dai noticed an error with UDT 1.0 with the following thought experiment:

“Suppose Omega appears and tells you that you have just been copied, and each copy has been assigned a different number, either 1 or 2. Your number happens to be 1. You can choose between option A or option B. If the two copies choose different options without talking to each other, then each gets $10, otherwise they get$0.”

The problem is that all the reasons that S(1)=A are the exact same reasons why S(2)=A, so the two copies will probably the same result. Wei Dai proposes a fix, UDT 1.1 which is that instead of choosing an output S(1), you instead choose a function S, from 1,2 to A,B from the 4 available functions which maximizes utility. I think this was not the correct correction, which I will probably talk about in the future. I prefer UDT 1.0 to UDT 1.1.

Instead, I would like to offer an alternative way of looking at this thought experiment. The error is in the fact that S only looked at the outputs, and ignored possible side effects. I am aware that when S looked at the outputs, he was also considering his output in simulations of himself, but those are not side effects of the function. Those are direct results of the output of the function.

We should look at this problem and think, “I want to output A or B, but in such a way that has the side effect that the other copy of me outputs B or A respectively.” S could search through functions considering their output on input 1 and the side effects of that function. S might decide to run the UDT 1.1 algorithm, which would have the desired result.

The difference between this and UDT 1.1 is that in UDT 1.1 S(1) is acting as though it had complete control over the output of S(2). In this thought experiment that seems like a fair assumption, but I do not think it is a fair assumption in general, so I am trying to construct a decision theory which does not have to make this assumption. This is because if the problem was different, then S(1) and S(2) might have had different utility functions.

Generalized Even Odds

The discussion on Less Wrong about my recent post, Even Odds, raised questions about what to do with more than two alternatives, and what to do with more than two players. Here are some generalizations.

If you have 3 or more different possibilities, then the generalization of the algorithm is simple. Both players report all of their probabilities. Find a proposition P such that the expected payoff for both players if you run the even odds algorithm on P is maximized, and run the even odds algorithm on P. (Break ties randomly) This is clearly fair. To show that this is strategy proof, assume that Alice were to lie about her probabilities. There are two cases. Either Alice’s lie changes the proposition P, or it does not. If the lie does not change P, then Alice is no worse off by the strategy proffness of the original even odds algorithm. If Alice’s lie changes the proposition from P to Q, then notice that Alice prefers telling the truth and betting on P to telling the truth and betting on Q, and Alice prefers telling the truth and betting on Q to lying and betting on Q, so Alice must prefer telling the truth and betting on P to any lie which makes her bet on Q. Therefore, this algorithm is strategy proof.

If there are 3 people, observe that the player who assigns the highest probability to the proposition and the player who assigns the lowest probability to proposition have no incentive to wager with anyone besides each other, since they get more profit for wagering with probabilities that are further apart. Therefore, it would make sense to not force these two players to bet with anyone else. However, this is not strategy proof, since now the third player might be incentivised to lie slightly about his probability in order to participate in a bet. This would not be fair or strategy proof.

Instead, we want to do all pairwise bets, with each player willing to bet half their maximum in each bet. This would clearly be strategy proof, since the component bets are strategy proof. However this is not fair. If one of the bets expects a higher profit than the others, then the player not participating in the high wager bet gets less output. This can be fixed by saying that for each bet, if both players are expected to gain x dollars, then they both also give x/3 dollars to the third player. This makes the wager also fair. It is still strategy proof, since we scaled expected payout by 2/3. However, if a player believes a statement 100%, and the other two think he is wrong 100%, an he is wrong, then he will end up paying d/2 in each bet, and an additional d/6 to each player as a tax for the bets he thought he would win. This totals 4d/3. We should therefore renormalize and have each bet be at 3d/8 instead, so that each player pays at most d total.

To generalize this to n players, run all n(n-1) bets. For each bet, both players pay every other payer 1/n times their expected profit to every other player. Each of these bets is an implementation of the even odds algorithm with maximum bet dn/(2(n-1)^2).

The algorithm for n options seems optimal to me, but I am not sure that the algorithm for n players is optimal.

Logic Puzzle: Prime Sided Dice

Imagine that you have a collection of very weird dice. For every prime between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001 inclusive.

For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.

This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?

When you know the right answer, you will probably be able to prove it. This puzzle is my own design. Solution in the comments.

On Voting for Third Parties

If your favorite candidate in an election is a third party candidate, should you vote for him?

This question has confused me. I have changed my mind many times, and I have recently changed my mind again. I would like to talk about some of the arguments in both directions and explain the reason for my most recent change.

Con 1) Voting for a third party is throwing your vote away.

We have all heard this argument before, and it is true. It is an unfortunate consequence of the plurality voting system. Plurality is horrible and there are all better alternatives, but it is what we are stuck with for now. If you vote for a third party, the same candidate would be elected as if you did not vote at all.

Pro 1) The probability that you vote changes the election is negligible. All your vote does is add one to the number of people who voted for a given candidate. Your vote for the third party candidate therefore matters more because it is changing a small number by relatively more.

This argument is actually an empirical claim, and I am not sure how well it holds up. It is easy to study the likelihood that you vote changes the election. One study finds that it roughly varies from 10^-7 to 10^-11 in America for presidential elections. However, it is not clear to me just how much your vote affects the strategies of political candidates and voters in the future.

Pro 2) The probability that your vote changes the election or future elections is negligible. The primary personal benefit for voting is the personal satisfaction of voting. This personal satisfaction is maximized by voting for the candidate you agree with the most.

I think that many people if given the choice between changing the next president between the two primary parties or being paid an amount of money equal to the product of the amount of gas they spent to drive to vote and 10^7 would take the money. I am not one of them but any of those people must agree that voting is a bad investment if you do not consider the personal satisfaction. However, I think I might get more satisfaction out of doing my best to change the election, rather than placing a vote that does not matter.

Con 2) Actually if you use a reflexive decision theory, you are much more likely to change the election, so you should vote like it matters.

Looking at the problem like a timeless decision agent, you see that your choice on voting is probably correlated with that of many other people. You voting for a primary party is logically linked with other people voting for a primary party, and those people whose votes are logically linked with yours are more likely to agree with you politically. This could bring the chance of changing the election out of the negligible zone, where you should be deciding based on political consequences.

Pro 3) Your morality should encourage you to vote honestly.

It is not clear to me that I should view a vote for my favorite candidate as an honest vote. If we used the anti-plurality system where the person with the least votes wins, then a vote for my favorite candidate would clearly not be considered an honest one. The “honest” vote should be the vote that you think will maximize your preferences which might be a vote for a primary party.

Pro 4) Strategic voting is like defecting in the prisoner’s dilemma. If we all cooperate and vote honestly, we will get the favorite candidate of the largest number of people. If not, then we could end up with someone much worse.

The problem with this is that if we all vote honestly, we get the plurality winner, and the plurality winner is probably not all that great a choice. The obvious voting strategy is not the only problem with plurality. Plurality also discourages compromise, and the results of plurality are changed drastically by honest vote splitting. The plurality candidate is not a good enough goal that I think we should all cooperate to achieve it.

I have decided that in the next election, I will vote for a primary party candidate. I changed my mind almost a year ago after reading Stop Voting for Nincompoops, but after recent further reflection, I have changed my mind back. I believe that Con 1 is valid, Con 2 and the other criticisms above adequately respond to Pro 1 and Pro 2, and I believe that Pro 3 and Pro 4 are invalid for the reasons described above. I would love to hear any opinions on any of these arguments, and would love even more to hear arguments I have not thought of yet.

Logic Puzzle: Find the Apples

Imagine the following two player game. Alice secretly fills 3 rooms with apples. She has an infinite supply of apples and infinitely large rooms, so each room can have any non-negative integer number of apples. She must put a different number of apples in each room. Bob will then open the doors to the rooms in any order he chooses. After opening each door and counting the apples, but before he opens the next door, Bob must accept or reject that room. Bob must accept exactly two rooms and reject exactly one room. Bob loves apples, but hates regret. Bob wins the game if the total number of apples in the two rooms he accepts is a large as possible. Equivalently, Bob wins if the single room he rejects has the fewest apples. Alice wins if Bob loses.

Which of the two players has the advantage in this game?

This puzzle is my own design, and it is a lot more interesting than it looks at first. I will post the solution in the comments.

Even Odds

Let’s say that you are are at your local less wrong meet up and someone makes some strong claim and seems very sure of himself, “blah blah blah resurrected blah blah alicorn princess blah blah 99 percent sure.” You think he is probably correct, you estimate a 67 percent  chance, but you think he is way over confident. “Wanna bet?” You ask.

“Sure,” he responds, and you both check your wallets and have 25 dollars each. “Okay,” he says, “now you pick some betting odds, and I’ll choose which side I want to pick.”

“That’s crazy,” you say, “I am going to pick the odds so that I cannot be taken advantage of, which means that I will be indifferent between which of the two options you pick, which means that I will expect to gain 0 dollars from this transaction. I wont take it. It is not fair!”

“Okay,” he says, annoyed with you. “We will both write down the probability we think that I am correct, average them together, and that will determine the betting odds. We’ll bet as much as we can of our 25 dollars with those odds.”

“What do you mean by ‘average’ I can think of at least four possibilities. Also, since I know your probability is high, I will just choose a high probability that is still less than it to maximize the odds in my favor regardless of my actual belief. Your proposition is not strategy proof.”

“Fine, what do you suggest?”

You take out some paper, solve some differential equations, and explain how the bet should go.

Satisfied with your math, you share your probability, he puts 13.28 on the table, and you put 2.72 on the table.

A third meet up member takes quickly takes the 16 dollars from the table and answers, “You wait.”

I will now derive a general algorithm for determining a bet from two probabilities and a maximum amount of money that people are willing to bet. This algorithm is both strategy proof and fair. The solution turns out to be simple, so if you like, you can skip to the last paragraph, and use it next time you want to make a friendly bet. If you want to try to derive the solution on your own, you might want to stop reading now.

First, we have to be clear about what we mean by strategy proof and fair. “Strategy proof” is clear. Our algorithm should ensure that neither person believes that they can increase their expected profit by lying about their probabilities. “Fair” will be a little harder to define. There is more than one way to define “fair” in this context, but there is one way which I think is probably the best. When the players make the bet, they both will expect to make some profit. They will not both be correct, but they will both believe they are expected to make profit. I claim the bet is fair if both players expect to make the same profit on average.

Now, let’s formalize the problem:

Alice believes S is true with probability p. Bob believes S is false with probability q. Both players are willing to bet up to d dollars. Without loss of generality, assume p+q>1. Our betting algorithm will output a dollar amount, f(p,q), for Alice to put on the table and a dollar amount, g(p,q) for Bob to put on the table. Then if S is true, Alice gets all the money, and if S is false, Bob gets all the money.

From Alice’s point of view, her expected profit for Alice will be $p(g(p,q))+(1-p)(-f(p,q))$.

From Bob’s point of view, his expected profit for Bob will be $q(f(p,q))+(1-q)(-g(p,q))$.

Setting these two values equal, and simplifying, we get that $(1+p-q)g(p,q)=(1+q-p)f(p,q)$, which is the condition that the betting algorithm is fair.

For convenience of notation, we will define h(p,q) by $h(p,q)=g(p,q)/(1+q-p)=f(p,q)/(1+p-q)$.

Now, we want to look at what will happen if Alice lies about her probability. If instead of saying p, Alice were to say that her probability was r, then her expected profit would be $p(g(r,q))+(1-p)(-f(r,q))$, which equals $p(1+q-r)h(r,q)+(1-p)(-(1+r-q)h(r,q))=(2p-1-r+q)h(r,q)$

We want this value as a function of r to be maximized when r=p, which means that $-h+(2p-1-r+q)\frac{dh}{dr}=0$,

which since r=p is the same as $-h+(-1+r+q)\frac{dh}{dr}=0$.

Separation of variables gives us $\int\frac{1}{h}dh=\int\frac{1}{-1+r+q}dr$,

which integrates to $ln(h)=C+ln(-1+r+q)$,

which simplifies to $h(r,q)=e^C(-1+r+q)$,

or equivalently, $h(p,q)=e^C(-1+p+q)$.

This gives the solution $f(p,q)=e^C(-1+p+q)(1+p-q)=e^C(p^2-(1-q)^2)$

and $g(p,q)=e^C(-1+p+q)(1+q-p)=e^C(q^2-(1-p)^2)$.

It is quick to verify that this solution is actually fair, and both players’ expected profit is maximized by honest reporting of beliefs.

The value of the constant multiplied out in front can be anything, and the most either player could ever have to put on the table is equal to this constant. Therefore, if both players are willing to bet up to d dollars, we should define $e^C=d$.

Alice and Bob are willing to bet up to d dollars, Alice thinks S is true with probability p, and Bob thinks S is false with probability q. Assuming p+q>1, Alice should put in $d(p^2-(1-q)^2)$, while Bob should put in $d(q^2-(1-p)^2)$. I suggest you use this algorithm next time you want to have a friendly wager (with a rational person), and I suggest you set d to 25 dollars and require both players to say an odd integer percent to ensure a whole number of cents.

The Storytelling of Science

This video is 9 months old, so you may have already seen it, but I had to share it because it is by far the most amusing thing I have seen on youtube. It is a panel including Bill Nye, Neil deGrasse Tyson, Richard Dawkins, Brian Greene, Lawrence Krauss and others. If you know who half those people are, you are probably already watching it. If not, you should.