# Ehud Friedgut: Blissful ignorance and the Kahneman-Tversky paradox

Tversky, Kahneman, and Gili Bar-Hillel (WikiPedia). Taken by Maya Bar-Hillel at Stanford, summer 1979.

The following post was kindly contributed by Ehud Friedgut.

During the past week I’ve been reading, and greatly enjoying Daniel Kahneman’s brilliant book “Thinking fast and Slow”.

One of the most intriguing passages in the book is the description of an experiment designed by Kahneman and Tversky which exemplifies a judgmental flaw exhibited by many people, which supposedly indicates an irrational, or inconsistent behavior. I will describe their experiment shortly.
I still remember the first time I heard of this experiment, it was related to me over lunch in Princeton by Noga Alon. Returning to this problem, 15 years later, I still, as in my initial exposure to the problem, made the “inconsistent” choice made by the vast majority of the subjects of the study. In this post I wish to argue that, in fact, there is nothing wrong with this choice.

Before relating their experiment, let me suggest one of my own. Imagine, if you will, that you suffer from gangrene in one of your toes. The doctor informs you that there is a 20% chance that it is “type A” gangrene, in which case you can expect spontaneous healing. There is a 75% chance that it is type B, in which case you will have to amputate it, and a 5% chance that it is type C. In the last case there is a shot you can be given that will save your toe, but it will cost you 2000$. What would you do? I would probably not take the shot. My guiding principle here is that I hate feeling stupid, and that there’s a pretty good chance that if I take the shot I’ll walk around for the rest of my life, not only minus one toe and 2000$, but also feeling foolish for making a desperate shot in the dark.
Now, say I declined the shot, and I return after a week, and the doctor sees that the condition has worsened and that he will have to amputate the toe. He asks me if I wish (say for no cost) that he send the amputated toe for a biopsy, to see if it was type B or C. Here my gut reaction, and I’m sure yours too, is a resounding no. But even when thinking it over more carefully I still think I would prefer not to know. The question is which is better:
Option 1) I have a 75/80 probability of having a clean conscience, and a 5/80 chance of knowing clearly for the rest of my life that I’m lacking a toe because I’m what’s known in Yiddish as an uber-chuchem (smart aleck).
Option 2) Blissful ignorance: for the rest of my life I enjoy the benefit of doubt, and know that there’s only a 5/80 chance that the missing toe was caused by my stinginess.
I prefer option 2. I’m guessing that most people would also choose this option. I’m also guessing that Kahenman and Tversky would not label this as an irrational or even an unreasonable choice. I’m almost positive they wouldn’t claim that both options are equivalent.

Now, back to the KT experiment. You are offered to participate in a two stage game. In the first stage 75% of the participants are eliminated at random. At the second stage, if you make it, you have two choices: a 100% chance of winning 30$or an 80% chance of winning 45$. But you have to decide before stage one takes place.
What would you choose?
I’ll tell you what I, and the majority of the subjects of the study do. We choose the 30$. Here’s my reasoning: 30$ is pretty nice, I can go for a nice lunch, 45$would upgrade it, sure, but I would feel really bad if I ended up with nothing because I was greedy. Let’s stick to the sure thing. Now a different experiment: you have to choose between 20% chance of gaining 45$, or a 25% chance of gaining 30$. What do you choose? Once again, I chose what the majority chose: I would now opt for the 45$. My reasoning? 20% sounds pretty close to 25% to me, the small difference is worthwhile for a 50% gain in the prize.

O.k., I;m sure you all see the paradox. The two games are identical. In both you choose between a 20% chance of 45$and a 25% chance of 30$. My reference to “a sure thing” represented a miscomprehension, common to most subjects, who ignored the first stage in the first game. Right?

No, wrong. I think the two games are really different, just as the two options related to the gangrene biopsy were different.
It is perfectly reasonable that when imagining the first game you assume that you are told whether you proceed to the second stage or not, and only if you proceed you are then told, if you chose the 80% option, whether you were lucky.
In contrast, in the second game, it is reasonable to assume that no matter what your choice was, you are just told whether you won or not.
Of course, both games can be generated by the same random process, with the same outcome (choose a random integer between 1 and 100, and observe whether it’s in [1,75], [76,95] or [96,100] ), but that doesn’t mean that when you chose the 45$option and lose you always go home with the same feeling. In game 1 if you chose the risky route you have a 75% probability of losing and knowing that your loss has nothing to do with your choice, and a 5% chance of kicking yourself for being greedy. In game 2 you have a 80% chance of losing, but enjoying the benefit of doubt, knowing that there’s only a 5/80 chance that the loss is your fault. Of course, my imagination regarding the design of the games is my responsibility, it’s not given explicitly by the original wording, but it certainly is implicit there. I maintain that there is nothing irrational about trying to avoid feeling regret for your choices, and that I would really stick to the “paradoxical” combination of choices even in real life, after fully analyzing the probability space in question. For those of you reading this blog who don’t know me, I’m a professor of mathematics, and much of my research has to do with discrete probability. That doesn’t mean that I’m not a fool, but at least it gives me the benefit of doubt, right? ======================================================== O.k., now, here’s part two of my post – after finishing the book. # Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture This post is authored by Karim Adiprasito The past months have seen some exciting progress on diameter bounds for polytopes and polytopal complexes, both in the negative and in the positive direction. Jesus de Loera and Steve Klee described simplicial polytopes which are not weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about $\sqrt{d}$ was proved by Hähnle, Klee, and Pilaud in the paper Obstructions to weak decomposability for simplicial polytopes. In this post I want to outline a generalization of a beautiful result of Billera and Provan in support of the Hirsch conjecture. I will consider the simplicial version of the Hirsch conjecture, dual to the classic formulation of Hirsch conjecture. Furthermore, I will consider the Hirsch conjecture, and the non-revisiting path conjecture, for general simplicial complexes, as opposed to the classical formulation for polytopes. Theorem [Billera & Provan `79] The barycentric subdivision of a shellable simplicial complex satisfies the Hirsch Conjecture. The barycentric subdivision of a shellable complex is vertex decomposable. The Hirsch diameter bound for vertex decomposable complexes, in turn, can be proven easily by induction. This is particularly interesting since polytopes, the objects for which the Hirsch conjecture was originally formulated, are shellable. So while in general polytopes do not satisfy the Hirsch conjecture, their barycentric subdivisions always do! That was a great news! Shellability is a strong combinatorial property that enables us to decompose a complex nicely, so it does not come as a surprise that it can be used to give some diameter bounds on complexes. Suprisingly, however, shellability is not needed at all! And neither is the barycentric subdivision! A simplicial complex Σ is called flag if it is the clique complex of its 1-skeleton. It is called normal if it is pure and for every face F of Σ of codimension two or more, Lk(F) is connected. Theorem (Adiprasito and Benedetti): Any flag and normal simplicial complex Σ satisfies the non-revisiting path conjecture and, in particular, it satisfies the Hirsch conjecture. This generalizes the Billera–Provan result in three ways: — The barycentric subdivision of a simplicial complex is flag, but not all flag complexes are obtained by barycentric subdivisions. — Shellability imposes strong topological and combinatorial restrictions on a complex; A shellable complex is always homotopy equivalent to a wedge of spheres of the same dimension, and even if a pure complex is topologically nice (if, for example, it is a PL ball) it may not be shellable, as classic examples of Goodrick, Lickorish and Rudin show. Being normal still poses a restriction, but include a far wider class of complexes. For example, every triangulation of a (connected) manifold is normal, and so are all homology manifolds. — Instead of proving the Hirsch conjecture, we can actually obtain the stronger conclusion that the complex satisfies the non-revisiting path conjecture, which for a given complex is stronger than the Hirsch conjecture. A geometric proof of our theorem appeared in a recent paper “Metric geometry and collapsibility” with Bruno Benedetti. . I will give here a short combinatorial proof. ### Construction of a combinatorial segment Continue reading # Eyal Sulganik: Towards a Theory of “Mathematical Accounting” The following post was kindly contributed by Eyal Sulganik from IDC (Interdiciplinary Center) Herzliya. Eyal was motivated by our poll on certainty “beyond a reasonable doubt,” which is related to several issues in accounting. Mathematicians, I believe, are always looking for new areas where their models and concepts can make a difference. Physics, Economics, CS, Biology are just some examples, surely not exhausting a longer list of such areas. Although the origins of accounting emanate from mathematicians (for example: L. Pacioli, and even A. Cayley found interest in it), it is a fact, though not unexplained, that these days (almost) no mathematicians are interested in accounting and there is no field of “mathematical accounting”. In the following few paragraphs I would like to thus draw attention to accounting as a possible field for mathematicians. Surprisingly, a possibly “profitable field”. I believe that accounting can be subject, inter-alia, to use of theories of Formal Systems, Information Theory, Voting theory, Fuzzy Logic, Graph theory and even Catastrophe theory. In brief, accounting (Financial Reporting) deals with the measurement and reporting of economic events . As such, it is a measurement system interlaced with an information system. (Results such as Blackwell theorem on the comparison of information systems are of relevance). Financial reporting of firms, the lifeline of the Capital Markets, is dictated by “reporting standards”. Those reporting standards are determined by “standard boards” (according to voting rules and procedures, which are very interesting for analysis) and interpreted and evolve over time (as is the case with other languages). The reports are audited by accounting firms. Auditing theory became more sophisticated but even fairly standard tools like Benford Law are not yet routine. Moreover, a huge debate centers on whether to adopt a rule-based system where “every” possible scenario is prescribed in advance or whether to adopt a principle based system which gives” freedom” to every reporting entity in reflecting the economic substance of an event. It is well known that a rule-based systems provide greater comparability (between firms), but at the same time, as they are more rigid and make use of “bright lines”, can be more easily forced to reflect form over substance . Indeed, Bright line Accounting rules are not continuous functions and hence small changes in the description or design of an event can lead to enormous differences in the reported values. For example, given that the definition of “CONTROL” was based on a “50% legal test” ,until recently it was the case that if company A was holding 50.01% of the shares of company B (other holders being each much smaller) and sold only 1.02% it could recognize a profit, due to “loss of control”, as though it sold the whole holding and bought back 49.01%. Needless to say that although holding “only” 49.01% , A CONTROLs B (Danny Ben Shahar, Desmond Tsang and Myself are in the process of demonstrating that “accounting theory of control” is inconsistent with Shapley Value). Principle based systems, on the other hand, must make sure that its principles are common knowledge. For example, if a provision for loss regarding a claim against a firm depends on the chances of loss being “Probable” or “remote” or “reasonably possible” a question arises what the preparers and users of the financial statements think about those terms. Many years ago, me and my colleague Yossi Aharoni found out-through questionnaires- that different types of agents have different probabilistic interpretations to those terms and we explained the mis-communication it can cause. I attach two simple papers (one co-authored with Danny Ben Shahar, the other one in hebrew), that can shed some more light on the above point of view and I dare state a wish that a new field of “mathematical accounting” will be created . # Michal Linial: No Witches in Portugal ### It gives me great pride to present: ### Michal Linial: March 2012 ## No witches in Portugal Landing in LISBOA, Portugal last night. I need to get to my hotel in Cascais. The nice lady in the tourist information ordered a taxi and happily said: “Do not worry, our drivers speak excellent English. Five minutes later my driver arrived, a huge person, nicely dressed with a fancy nice black car. “To Cascais, What is the price” I asked in a fluent English. Well, it depends he replied… My huge driver, was very fluent in English as promised… Then he starts… Three years ago I had a ski accident, at that time I was much heavier… I was wondering how such information might be relevant to our trip… My driver continues: “From the time of the accident my leg is not the same. This is why I bought this car with a “gear” instead of an automatic transmission, so I can practice my left leg. Most of time I can move it, but I still do not feel it when it is cold”… “Is it cold today?” I asked. No, today it is fine. Yesterday it was cold. How long is it to Cascais? I was asking. My driver relied honestly: “it depends on the road”… Oh, I said… waiting for an explanation. It took a minute for him to explain: “You know, I always drive by my feelings. Sometime, I have a feeling that it is not good to take the freeway. Today I have this feeling. “OK, it is best that you listen to your feelings”, I relied quietly. He continues: “You know, there are no witches in Portugal, but it is better to listen to them”. Of course, I said. You know he continue, my brother in law who was a driver in our taxi company had a bad feeling 4 months ago when he took the small road instead of the highway, and indeed he died. A truck crushed him. But the passenger, a British person that was in the car was not hurt. The passenger had his seat belt fasten, like you… Do you want me to show you where he died?, it is on the way to the hotel, he insisted. Sure I replied. If it is on the way, and you feels that we should not take the highway, let’s go on the other road… We drove on a neglected road. It was not too cold… My huge driver mentioned me the spot where his brother in law died… We are now 10 min from the hotel he updated me. But I missed the entrance. You know, he continued, once I drove with my mother, I missed the entrance to the road. Then, I knew that I should not get into this road. Do you mind that I will drop you here? it is no more than 200 meters to your hotel. I happily paid the 60 Euro, another tip for 10 Euro for the good witch that was with us. While I was walking with my luggage on the hill to the hotel, a taxi was stopping behind me. It was my big driver again… He said: I forgot to give you my card. Please call me when you want to go back to the airport. it will be only 30 Euro. We can take the highway. I am still in Portugal for another 2 days. I will call him if it will not be too cold. # Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)

Scanned letter by Zadeh. (c) Günter M. Ziegler

left-to-right: David Avis, Norman Zadeh,  Oliver Friedmann, and Russ Caflish (IPAM director). Photo courtesy Eddie Kim.

Update: The slides for Friedmann’s talk are now available. The conference schedule page contains now the slides for most presentations.

This post is authoured by Günter Ziegler with some help by David Avis. A German (slightly expanded) version can be found on Günter’s blog.

Oliver Friedmann, a Computer Science graduate student at Munich University, will defend his thesis next month. It contains a proof, that “Zadeh’s rule” for linear optimization is “exponential”, that is, it may take an awfully long time on relatively small problems.

### Why is this remarkable?

“Linear Optimization” problems are extremely important computational tasks that arise in all kinds of larger planning processes. Such tasks are usually solved on a computer using a method known as the “simplex algorithm”, invented by George Dantzig in 1947. The simplex method needs a prescription for making local choices in its search, known as the “pivot rule”. And it is known about mostsuch pivot rules that they can be extremely slow and inefficient on particular optimization problems. One would like (and need) a rule that is “provably fast”.

One candidate for this was the “Zadeh rule” — until today. When Zadeh was a postdoc in the Department of Operations Research at Stanford he published a technical report on the worst case examples of the simplex method. Continue reading

# János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach.

This post is authored by János Pach

### A Festive Day: November 19

Today is a festive day. It was on this day, November 19, 1863, that Abraham Lincoln presented his famous Gettysburg Address. Seventy nine years later, on the same day (on his own birthday!), Georgy Zhukov, Marshal of the Soviet Union, launched Operation Uranus, turning the tide of the battle of Stalingrad and of World War II. Now sixty eight years later, here we stand (or sit) and experience my very first attempt to contribute to a blog, as Gil has suggested so many times during the past couple of years. But above all, this is a festive day, because earlier today Larry Guth and Nets Hawk Katz posted on arXiv
(http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf) an almost complete solution of Erdös’s Distinct Distances Problem. The story started with Erdős’s 1946 paper published in the American Mathematical Monthly. In this paper, he posed two general questions about the distribution of distances determined by a finite set of points in a metric space.

1. Unit Distance Problem: At most how many times can the same distance (say, distance 1) occur among a set of n points?

2. Distinct Distances Problem: What is the minimum number of distinct distances determined by a set of n points?

Because of the many failed attempts to give reasonable bounds on these functions even in the plane, one had to realize that these questions are not merely “gems” in recreational mathematics. They have raised deep problems, some of which can be solved using graph theoretic and combinatorial ideas. In fact, the discovery of many important combinatorial techniques and results were motivated by their expected geometric consequences. (For more about the history of this problem, read my book with Pankaj Agarwal: Combinatorial Geometry, and for many related open problems, my book with Peter Brass and Willy Moser: Research Problems in Discrete Geometry.)

Erdős conjectured that in the plane the number of unit distances determined by n points is at most $n^{1+c/loglog n}$, for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only $O(n^{4/3})$. As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is $n/\sqrt{log n}$, while the best lower bound was $n^{0.8641...}$, thanks to combined efforts by J. Solymosi – C.D. Toth (2001) and N.H. Katz – G. Tardos (2004).

This was the situation until today! The sensational new paper of Guth and Katz presents a proof of an almost tight lower bound of the order of n/log n. Let us celebrate this fantastic development! In this area of research, it is already considered a great achievement if by introducing an ingenious new idea one is able to improve a bound by a factor of $n^{\delta}$ for some positive δ. Continue reading

# Anat Lotan: Who is Gina II, My Own Shocking Revelation

### Who’s Gina? (Part 2): My Own Shocking Revelation

By: Anat Lotan

It was one of those typically hot Israeli end-of-August days; a scorching summer morning, where you have to convince yourself that the cool breezes of autumn are just around the corner.

To escape the unbearable humidity of the coastal area, I decided to treat myself to a visit to Jerusalem. My cause for excitement was twofold: not only would I enjoy the sites and atmosphere of this beautiful city, but this impromptu visit would also be the perfect opportunity to meet with dear Prof. Gil Kalai, the mastermind behind these very pages, a man who boldly followed Gina’s adventures through cyberspace, and who cleverly pieced them together into a highly entertaining book.

Little did I know, however, that this would not be just another visit to Jerusalem, or that this seemingly typical summer day would turn out to be anything but typical. Indeed, it was to be a memorable day of SHOCKING REVELATIONS!

Shortly after arriving at the Hebrew University’s scenic Givat Ram campus, I made my way to Prof. Kalai’s office. After we exchanged pleasantries and discussed our respective summers, our conversation naturally turned to Gina’s Adventures. Gil had recently added the book to his blog, and he shared with me some of the most notable and amusing comments that had been posted in reaction to the book.

Laughing, Gil told me that one of the bloggers had even “accused” him of being Gina. This comment prompted me to ask if the “real” Gina had, in fact, attempted to contact Gil – it only seemed natural that she would have something to say to the man who had so blatantly “outed” her.

I’m not sure I recall Gil’s precise response to my question. Whatever it was Continue reading

# Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I

This post is authored by Michael Schapira. (It is the first in a series of two posts.)

In this post, I’ll outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism design, game theory and distributed computation.

The Internet comprises administrative domains known as Autonomous Systems (ASes), which vary in size, from large (multi)national networks to small networks servicing schools or small businesses. The task of establishing routes between ASes, called interdomain routing, is currently handled by the Border Gateway Protocol (BGP)—the core routing protocol of the Internet. BGP is one of the most critical pieces of the Internet’s infrastructure and can be regarded as the glue that holds the Internet together.

Over the past decade, routing with BGP has been studied from engineering, computational, game theoretic and economic perspectives. Combining algorithmic and economic considerations in the study of interdomain routing is natural, because the many separate domains that make up the Internet are independent economic agents that must jointly execute a distributed algorithm in order to route traffic. In addition, interdomain routing motivates exciting new questions in computer science, game theory, and economics.

A (Simplified) Model of Interdomain Routing

The following is a simplified model of interdomain routing, based on the seminal work of Thimothy Griffin and Gordon Wilfong, and on the game-theoretic model of Hagay Levin, Michael Schapira, and Aviv Zohar   Continue reading

# Joe Malkevitch: Why Planar Graphs are so Exceptional

Not only do interesting questions arise by considering the special class of planar graphs but additional special issues arise when one considers a specific plane drawing of a planar graph. This is because when a graph is drawn in the plane it becomes possible to order or number, say for example, the edges at a particular vertex of the graph, in an organized consistent way.

One example of results which started from this reality for plane graphs is this paper of Grunbaum and Motzkin: B. Grünbaum and T. S. Motzkin , The number of hexagons and the simplicity of geodesics on certain polyhedra. Canad. J. Math. 15 (1963), pp. 744–751. In this paper the following is explored (along with results about what today are called fullerenes). Suppose one has a 3-valent plane graph. If one picks any edge and moves along that edge (in either direction), when one gets to a vertex one has the choice of going left or right and moving on to another edge. Suppose one goes left, and at the next vertex in one’s “traversal” one goes right, alternating left, and right. Grunbaum and Motzkin refer to this as left-right path, and they prove that for a plane 3-valent graph with each of its faces having a multiple of 3 for its number of sides, that these left-right paths (starting on any edge) always generate “simple circuits.”

I was able to extend this result in several directions. Continue reading

# (Eran Nevo) The g-Conjecture III: Algebraic Shifting

This is the third in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property (which is largely understood and known to hold for simplicial spheres) and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres.

## The g-conjecture and algebraic shifting

### Squeezed spheres

Back to the question from last time, Steinitz showed that

any simplicial 2-sphere is the boundary of a convex 3-polytope.

However, in higher dimension

there are many more simplicial spheres than simplicial polytopes,

on a fixed large number of vertices. Continue reading