# Angry Bird Skepticism

Lenore Holditch is a freelance writer. Here is what she wrote to me: “I love learning about new topics, so I am confident that I can provide valuable content for your blog on any topic you wish, else I can come up with a post most relevant to your blog theme. The content would be fully yours.” Lenore only asked for a link back to her site . She sent me also a few of her articles like this one about finding jobs after graduation and this one about video games for training.

I asked Lenore to explore the following issue and she agreed:

Stay tuned!

# The Privacy Paradox of Rann Smorodinsky

The following paradox was raised by Rann Smorodinsky:

Suppose that you have the following one-time scenario. You want to buy a sandwich where the options are a roast beef sandwich or an avocado sandwich. Choosing the sandwich of your preference (say, the avocado sandwich) adds one to your utility, but having your private preference known to the seller,  reduces by one your utility. The prior people have on your preferences is fifty-fifty.

If you choose the avocado sandwich your utility is zero, hence you can improve on this by picking each type of sandwich at random with probability 1/2. In this case your private preference remains unknown and you gain in expectation 1/2 for having the sandwich you prefer with probability 1/2.

But given this strategy, you can still improve on it by choosing the avocado sandwich.

# 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 .

# Galvin’s Proof of Dinitz’s Conjecture

## Dinitz’ conjecture

The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994:

Theorem: Consider an n by n square table such that in each cell (i,j) you have a set $A_{i,j}$ with n or more elements. Then it is possible to choose elements $a_{ij}$ from $A_{ij}$ such that the chosen elements in every row and in every colummn are distinct.

Special case: if all $A_{ij}$ are the same set, say {1,2,…,n} then this is possible. Such a choice is called a Latin square for example $a_{ij}=i+j({\rm mod} n)$.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Here are a few remarks before we go ahead with Galvin’s proof:

1) The Theorem is about graph-coloring from  lists of colors, or briefly list-coloring. Given a graph G with n vertices and a list of colors $A_i$ for vertex $i$ we ask for a proper coloring of the graph such that vertex i is colored by an element of $A_i$. (A proper coloring is a coloring such that two djacent vertices have different colors.)

The list chromatic number of a graph G is the smallest number k such that G can be colored from any lists of colors, where every $A_i$ has k elements.

2) We consider the graph G whose vertices are the pairs (i,j) and two vertices are adgacent if one of their coordinates agree. This graph is the line graph of the complete bipartite graph $K_{n,n}$. The line graph L(H) of a graph H is the graph whose vertices correspond to the edges of H and two vertices are adjacent if the corresponding edges share a vertex.

3) Vizing proved that the chromatic number of the line graph L(H) is at most one more than the maximum degree of H. He conjectured that this is also true for list coloring. A bolder version asserts that for every line-graph G the list chromatic number equals the chromatic number. Dinits’s conjecture is the special case (of the bolder version) where G is the line graph of the complete bipartite graph $K_{n,n}$. The proof demonstrates Vizing’s conjecture for the line graph of every bipartite graph.

4) Shortly before Galvin, Jeannette Janssen gave an amazing proof for a slightly weaker statement where in each square you allow n+1 colors.  (She proved the Dinitz conjecture for rectangular arrays.) Janssen applied  a theorem of Alon and Tarsi, who used the “polynomial method” to obtain a powerful necessary condition for list coloring.

5) Here are now (or when I will be able to find them later) links to Galvin’s paper, to Janssen’s paper, to Alon-Tarsi’s paper,  to expositions by Barry Cipra and by Doron Zeilberger and to a short self-contained version of the proof by Tomaž Slivnik.

## Galvin’s proof

Galvin’s ingenious proof of Dinitz’ the conjecture combines two known theorems which are quite easy themselves.

For a directed graph G an induced subgraph is a subgraph spanned by a subset of the set of vertices of G. A kernel in a directed graph is an independent and absorbant set of vertices. I.e., it is a set of vertices W such that there is no edge between any two vertices in W, and from every vertex not in W there is an edge directed from it to a vertex in W.

Lemma 1 (Bondy, Boppana, Siegal): (mentioned e.g. in the paper by Alon and Tarsi)

# Another way to Revolutionize Football

The angle of Victoria Beckham’s hat (here in a picture from a recent wedding) is closely related to our previous post on football

One of the highlights of the recent Newton Institute  conference on discrete harmonic analysis was a football game which was organized by Frank Barthe and initiated independently by Barthe and Prasad Tetali. There were two teams of 10 players (more or less), I was the oldest player on the field, and it was quite exciting. No spontaneous improvement of my football skills has occurred since my youth.

All the lectures at the conference were videotaped and can be found here. (The football game itself was not videotaped.) Let me mention an idea for a new version of football which occurred to me while playing. For an early suggested football revolution and some subsequent theoretical discussions see this post on football and the intermediate value theorem.

## The New Football Game

There are four teams. Team L (the left team), Team R (the right team), Team D (the defense team) and team O (the offense team.)  The left team protects the left goal and tries to score the right goal, the right team protects the right goal and tries to score the left goal, the defense team tries to prevent goals on both sides of the field and the offense team tries to score as much as possible goals on both sides of the field.

In formal terms,  define X to be the number of goals scored to the right and Y the number of goals scored to the left. Then the four teams try to maximize X-Y, Y-X, -X-Y and X+Y, respectively. (I do not assume teams A and B change position at halftime, but the formula can easily be adjusted.)

# Is Backgammon in P?

## The Complexity of Zero-Sum Stochastic Games with Perfect Information

Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is “no”. But if we wish to consider the complexity in terms of the number of all possible positions then it is easy to go backward over all positions and determine what is the outcome of the game when we start with each given position.

# Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form $2^{n^{\alpha}}$ for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades. Here is a link to the paper.

Update: Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

We can regard the simplex algorithm as starting from an arbitrary vertex of the feasible polytope and repeatedly moving to a neighboring vertex with a higher value of the objective function according to some pivot rule.

The pivot rules considered in the paper are

RANDOM EDGE– Choose an improving pivoting step uniformly at random.

RANDOM FACET– Choose at random a facet containing your vertex and apply the algorithm in that facet.