In this talk I will not talk science but about science. In the current economic crisis, many voices criticize the ability of our economists to foresee the future. Indeed, despite they master sophisticated mathematical tools, they were and still are unable to anticipate the future because they stick to mathematical models which do not reflect the real world. Obviously I am not an expert in financial economy and I do not claim to be, but using my own experience in game theory, a branch of economy, I am inclined to agree with those judgments. I call "Kuhn effect" the current attitude of rigid game theorists vis-a-vis new mathematical tools, as a credit to the game theorist Harold W. Kuhn and the historian of science and epistemologist Thomas Kuhn. Actually since 1970, game theorists are aware that finite extensive game theory is not an adequate model of escalation, since their theory showed that escalation is irrational whereas human agents do escalate. They called this a "paradox". In previous talks at this workshop I have presented the coinductive model of infinite extensive games which gives a correct explanation of escalation. In this talk, I will present how those ideas were received by the traditional and rigid game theorist community and try to draw some lessons.

I explain how a recent constructive proof (due to Dimitri Pataraia) of the fact that a monotone map on a pointed dcpo has the least fixed point can be used to deduce famous fixed point theorems of Banach, Caristi and Tarski.

We consider bipartite matching in the on-line version as follows. There is a bipartite graph G=(U,V,E), in which vertices in V are given a priori and each vertex u in U arrives in the on-line fashion (with all its incident edges). An on-line algorithm matches each such vertex u to a previously unmatched adjacent vertex in V, if there is one. Decisions made by the algorithm are irrevocable. The objective is to maximize the size of the resulting matching. It is easy to observe that any greedy algorithm (never leave vertex u unmatched if a match is possible) matches at least n/2 edges where n is the size of the optimal matching with G given at once. This number is optimal and there is no better algorithm. We propose the following modification of an on-line matching. The algorithm matches each incoming vertex u in U to a set S(u) of adjacent vertices in V (instead of one vertex). In case when S(u) and S(x) for already existing x in U are not disjoint the algorithm must remove all common vertices from S(x). Additionally, the algorithm has to obey the rule: each S(x) must not become empty if only it was initialized with a nonempty set of vertices. An algorithm satisfying the above condition is called adaptive. In this approach a vertex u in U can be always matched to a vertex from S(u) (if S(u) is not empty). Therefore, the number of matched edges is equal to the number of nonempty sets S(u). We are going to present the optimal adaptive on-line algorithm which breaks n/2 barrier and matches at least
(1-pi cosh(sqrt{3}pi/2))n+o(n)=0.589n+o(n) edges.

Abstract available in pdf file here.

The Shannon effect states that “almost all” Boolean functions have a complexity close to the maximal possible for the uniform probability distribution. In this talk we will define some probability distributions on functions, induced by random expressions, and prove that this model does not exhibit the Shannon effect.

A bijection between combinatorial maps and embedded syntactic trees enables us to deduce asymptotics and random samplers for BCI an BCK.