Three interesting puzzles

September 29th, 2011 No comments

Here are three puzzles I got from 3 different people recently. The first I got from Charles, who got it from a problem set of the Brazilian Programming Competition.

Puzzle #1: Given n and a vector of in-degrees and out-degrees \text{in}_i and \text{out}_i for i=1..n, find if there is a simple directed graph on n nodes with those in and out-degrees in time O(n \log n). By a simple directed graph, I mean at most one edge between each pair (i,j), allowing self loops (i,i).

Solving this problem in time O(n^3) is easy using a max-flow computation – simply consider a bipartite graph with and edge (i,j) between each pair with capacity 1. Add a source and connect to each node in the left size with capacity \text{in}_i and add also a sink in the natural way, compute max-flow and check if it is \sum_i \text{in}_i. But it turns out we can do it in a lot more efficient way. The solution I thought works in time O(n \log n) but maybe there is a linear solution out there. If you know of one, I am curious.

The second puzzle was given to me by Hyung-Chan An:

Puzzle #2: There is grid of size n \times m formed by rigid bars. Some cells of the grid have a rigid bar in the diagonal, making that whole square rigid. The question is to decide, given a grid and the location of the diagonal bars if the entire structure is rigid or not. By rigid I mean, being able to be deformed.

We thought right away in a linear algebraic formulation: look at each node and create a variable for each of the 4 angles around it. Now, write linear equations saying that some variables sum to 360, since they are around one node. Equations saying that some variable must be 90 (because it is in a rigid cell). Now, for the variables internal to each square, write that opposite angles must be equal (since all the edges are of equal length) and then you have a linear system of type Ax = b where x are the variables (angles). Now, we need to check if this system admits more then one solution. We know a trivial solution to it, which is all variable is 90. So, we just need to check if the matrix A has full rank.

It turns out this problem has a much more beautiful and elegant solution and it is totally combinatorial – it is based on verifying that a certain bipartite graph is connected. You can read more about this solution in Bracing rectangular frameworks. I by (Bolker and Crapo 1979). A cute idea is to use the the following more general linear system (which works for rigidity in any number of dimensions). Consider a rigid bar from point p_a \in \mathbb{R}^n to point p_b \in \mathbb{R}^n. If the structure is not rigid, then there is a movement it can make: let v_a and v_b be the instantaneous velocities of points a and b. If p_a(t), p_b(t) are the movements of points a,b, then it must hold that: \Vert p_a(t) - p_b(t) \Vert = \Vert p_a(0) - p_b(0) \Vert, so taking derivatives we have:

(p_a(0) - p_b(0)) \cdot (v_a - v_b) = 0

This is a linear system in the velocities. Now, our job is to check if there are non zero velocities, which again is to check that the matrix of the linear system is or is not full-rank.  An interesting thing is that if we look at this question for the grid above, this matrix will be the matrix of a combinatorial problem! So we can simply check if it has full rank by solving the combinatorial problem. Look at the paper for more details.

The third puzzle I found in the amazing website called The Puzzle Toad, which is CMU’s puzzle website:

Puzzle #3: There is a game played between Arthur and Merlin. There is a table with n lamps disposed in a circle, initially some are on and some are off. In each timestep, Arthur writes down the position of the lamps that are off. Then Merlin (in an adversarial way) rotates the table. The Arthur’s servant goes and flips (on –> off, off –> on) the lamps whose position Arthur wrote down (notice now he won’t be flipping the correct lamps, since Merlin rotated the table. if Arthur wrote lamp 1 and Merlin rotated the table by 3 positions, the servant will actually be flipping lamp 4. The question is: given n and an initial position of the table, is there a strategy for Merlin  such that Arthur never manages to turn all the lamps on.

See here for a better description and a link to the solution. For n = 2^k no matter what Merlin does, Arthur always manages to turn on all the lamps eventually, where eventually means in O(n^2) time. The solution is a very pretty (and simple) algebraic argument. I found this problem really nice.

Categories: puzzles, theory Tags: ,

Bayesian updates and the Lake Wobegon effect

September 25th, 2011 No comments

We seem to have a good mathematical understanding of Bayesian updates, but somehow a very poor understanding of its practical implications. There are many situations in practice that we easily perceive as irrational, one of the most famous is the so called Lake Wobegon effect, named after the fictional town in Minnesota, where “all the women are strong, all the men are good looking, and all the children are above average”. It is described as a cognitive bias where individuals tend to overestimate their own capabilities. In fact, when drivers are asked to rate their own skilled compared to the average in three groups: low-skilled, medium-skilled and high-skilled, most rate themselves above the average.

In fact, the behavioral economics literate is full of examples like this where the observed data is far from what you would expect to observe if all agents were rational – and those are normally attributed to cognitive biases. I was always a bit suspicious of such arguments: it was never clear if agents were simply not being rational or whether their true objective wasn’t being captured by the model. I always thought the second was a lot more likely.

One of the main problems of the irrationality argument is that they ignore the fact that agents live in a world where its states are not completely observed. In a beautiful paper in Econometrica called “Apparent Overconfidence“, Benoit and Dubra argue that:

“But the simple truism that most people cannot be better than the median does not imply that most people cannot rationally rate themselves above the median.”

The authors show that it is possible to reverse engineer a signaling scheme such that the data is mostly consistent with the observation. Let me try to give a simple example they give in the introduction: consider that each driver has one of three types of skill: low, medium or high: \{L,M,H\} and \mathbb{P}(L) = \mathbb{P}(M) = \mathbb{P}(H) = \frac{1}{3}. However, they can’t observe this. They can only observe some sample of their driving. Let’s say for simplicity that they can observe a signal A that says if they caused an accident or not. Assume also that the larger that skill of a driver, the higher it is his probability of causing an accident, say:

\mathbb{P}(A \vert L) = \frac{47}{80}, \mathbb{P}(A \vert L) = \frac{9}{16}, \mathbb{P}(A \vert L) = \frac{1}{20}

Before observing A each driver things of himself as having probability $\frac{1}{3}$ of having each type of skill. Now, after observing A, they update their belief according to Bayes rule, i.e.,

\mathbb{P}(s \vert A) = \frac{ \mathbb{P}(A \vert s) \mathbb{P}(s) }{ \sum_{s'} \mathbb{P}(A \vert s') \mathbb{P}(s') }

doing the calculations, we have that \mathbb{P}(A) = \frac{2}{5} and for the \frac{3}{5} of the drivers that didn’t suffer an accident, they’ll evaluate \mathbb{P}(L \vert \neg A) = \frac{11}{48}, \mathbb{P}(M \vert \neg A) = \frac{35}{144}, \mathbb{P}(H \vert \neg A) = \frac{19}{36}, so:

\mathbb{P}(H \vert \neg A) > \mathbb{P}(L \cup M \vert \neg A)

and therefore will report high-skill. Notice this is totally consistent with rational Bayesian-updaters. The main question in the paper is: “when it is possible to reverse engineer a signaling scheme ?”. More formally, let \Theta be a set of types of users and let \theta \sim H \in \Delta(\Theta), i.e., H is a distribution on the types which is common knowledge. Now, if we ask agents to report their type, their report is some H' \in \Delta(\Theta), H' \neq H. Is there a signaling scheme S which can be interpreted as a random variable correlated with \theta such that H' is the distribution rational Bayesian updaters would report based on what they observed from S ? The authors give necessary and sufficient condition on when this is possible given H,H'.

—————————–

A note also related to the Lake Wobegon effect: I started reading a very nice book by Duncan Watts called “Everything Is Obvious: *Once You Know the Answer” about traps of the common-sense. The discussion is different then above, but it also talks about the dangers of applying our usual common sense, which is very useful to our daily life, to scientific results. I highly recommend reading the intro of the book, which is open in Amazon. He gives examples of social phenomena where, once you are told them, you think: “oh yeah, this is obvious”. But then if you were told the exact opposite (in fact, he begins the example by telling you the opposite from the observed in data), you’d also think “yes, yes, this is obvious” and come up with very natural explanations. His point is that common sense is very useful to explaining data observations, specially observations of social data. On the other hand, it is performs very poorly on predicting how the data will look like before actually seeing it.

Categories: theory Tags: ,

Restaurants in Jerusalem

May 31st, 2011 No comments

The Algorithmic Game Theory Semester in Jerusalem has been amazing – made a lot of good friends and learned many interesting things. Now, ready to go back to the US, I feel I should share a bit about nice places to go in Jerusalem. Together with Vasilis Syrgkanis, I decided to compile a list of good restaurants, cafes, … specially a list of places open in shabbat (which is quite useful for the visitor).

My Favourite Restaurants

  • Machne-yuda : Next to the Mahane Yehuda market, the restaurant menu changes everyday (with a couple of dishes which are always there). The food is whatever is in that day in the market. Everything was perfect both times I went. I strongly recommend the polenta and the black risotto. We took almost 1 month to make a reservation and eventually we got one. Eventually we learned a nice trick – if you arrive there very late (say aroud midnight), it is not impossible to get a table (we got one in the bar right away, arriving at 11:30pm). Elisa Celis suggested this place, and I think Omer Reingold suggested it to her.
  • Chakra : There is a tasting menu that is amazing. It is around 160 NIS, but worth every cent. It started with chicken livers, salads, calamari, ceviche, shrimp (the shrimp was awesome), fish kebab and mussels. After the fish part ended, they brought us many meat dishes, like a beef strogonoff (I am still puzzled by how soft the meat was), lamb chops and beef kebab. It ended with a simple, yet perfect, chocolate dessert and ice-cream with tahina. Thanks to Shahar Dobzinski and Sigal Oren for the suggestion.
  • Carousella: It is a small restaurant in the corner of the street I used to live in Jerusalem (it is located in the corner of Azza and Metudela in Rehavia). It is a vegetarian French/Israeli restaurant and has my favorite shakshouka in town – it is actually a mix o shakshouka and ratatouille. I also like very much their risotto. We used to have breakfast/brunch there quite a lot – usually getting either the shakshouka or the musli. The house cake is definitely recommended too… It is my favourite place to work (they have wifi and a nice record player and a huge collection of records). Thanks to Omer Tamuz for this suggestion.

Hummus Places

  • Lina: It is known as the best hummus in the city (some claim the best hummus in the world). It is located in the Via Dolorosa and not hard to find. Arriving in the Via Dolorosa, you can just ask directions and everyone knows. Everything is recommended.
  • From Gaza to Berlin: is a small and super cheap restaurant in Rehavia – their hummus is very tasty (specially the hummus with meat), the kubbeh soup is very nice and their falafel is famous around here.
  • Marvad Haksamim (The Magic Carpet): a very nice arabic place – great bread, hummus, …  The soups are very good (I tried the lentil and the kubeh soup) and the meat is usually good as well. I tried the chopped livers and the kebab. The Mixed Jerusalem Grill is a famous plate, I guess.

Places to eat/work on shabbat: on Saturday and Friday night most of the things in the city are closed, so it is good to know some places to go:

  • Restobar: good food and generally open
  • Zuni: very nice and open 24 hours a day, 7 days a week. Has every type of meal (brunch, lunch, coffee, drinks), served all the time. Good for working too…
  • Mona: a very cool American/Israeli restaurant inside a former art school. Food is very good and has also a very nice bar.
  • Spaguettim: nice location, wifi, good coffee and snacks. I never tried the food, though.
  • many places on Hillel Street: for example the Iwo Meat Burger (a pretty good non-kosher burger place), the pizza place next to it and a couple of bars nearby

In the old city

  • Cheese pie: I don’t know how to give an exact location, but this should help you: very near to the Church of the Holy Sepulcher in the Old City, you can find the Coptic Patriarchate. Try to locate the stairs leading to the Patriarchate and before going up, there is a place that sells only one thing: a cheese pie. There is a big marble table and a man with a bowl of dough, some cheese and syrup. He prepares everything in front of you and then puts it in the oven. It takes around 20 minutes. It is very impressive.
  • Armenian Tavern: a very beautiful place hidden in the old city. Food is nice  (the lemonade is very refreshing and tastes great) but the better thing is the feeling that you are dining inside a museum.

Hotel Bars and Cafes

  • Mamilla Terrace: the restaurant in the terrace of Mamilla Hotel is pretty nice and has a good view of the old city. It is a good place to go for drinks as well. It is closed (I think) on shabbat.
  • Notre Dame Terrace: the Notre Dame hotel has also a great view to the Temple Mount and pretty nice food. It is very relaxing to sit there and look the old city. There is another restaurant in the hotel called La Rotisserie, which I very much appreciated. It is also open on shabbat.

In Tel Aviv

  • Raphael: inside the Dan Hotel and overlooking the sea. Most of the times I went to Tel Aviv I ended up eating there.
  • Boya: Thanks to Lior Seeman for this suggestion. We had many small dishes (something like tapas) and all were amazing. I think it was my favourite place in Tel Aviv.
Categories: Uncategorized Tags: