Publications of Pierre Lescanne 

Game and decision processes

Logic and computation

Counting lambda terms



You may also be interested by the page where I collected not easily accessible publications by several authors in the domain of term rewriting and type theory.

See also the support of talks I gave.

The following list is not exhaustive. For more complete lists see the list of my publications (2007) or DBLP which is more up-to-date list, but less complete for old publications. See also my ArXiV publications.

Resource control

CP games and applications to biology

A newer presentation of CP games taking account of Feasibility/Desirability concept to draw connection.

This paper has been rejected by Theoretical Economics.  The report is interesting as it shows that the editor does not comment the paper itself (did he read it?) and does not dare discuss the three aspects presented in the abstract, instead he argues on a specific example which was made up like the examples in textbooks to show a point.  What is clear is that he did not catch the ideas behind FD-games (or CP-games).

On infinite extensive games and escalation

We present infinite extensive strategy profiles with perfect information and we show that replacing finite by infinite changes the notions and the reasoning tools. The presentation uses a formalism recently developed by logicians and computer science theoreticians, called coinduction. This builds a bridge between economic game theory and the most recent advance in theoretical computer science and logic. The key result is that rational agents may have strategy leading to divergence .

Escalation is the fact that in a game (for instance an auction), the agents play forever. It is not necessary to consider complex examples to establish its rationality. In particular, the 0,1-game is an extremely simple infinite game in which escalation arises naturally and rationally. In some sense, it can be considered as the paradigm of escalation. Through an example of economic games, we show the benefit economics can take of coinduction. CALCO 2013: 191-204

        This is an extended and modified version of the previous paper.

As we show using the notion of equilibrium in the theory of infinite sequential games, bubbles and escalations are rational for economic and environmental agents, who believe in an infinite world. This goes against a vision of a self regulating, wise and pacific economy in equilibrium. In other words, in this context, equilibrium is not a synonymous of stability. We attempt to draw from this statement methodological consequences and a new approach to economics. To the mindware of economic agents (a concept due to cognitive psychology) we propose to add coinduction to properly reason on infinite games. This way we refine the notion of rationality.

Finite objects and more specifically finite games are formalized using induction, whereas infinite objects are formalized using coinduction. In this article, after an introduction to the concept of coinduction, we revisit on infinite (discrete) extensive games the basic notions of game theory.  Among others, we introduce a definition of Nash equilibrium and a notion of subgame perfect equilibrium for infinite games.  We use those concepts to analyze well known infinite games, like the dollar auction game and the centipede game and we show that human behaviors that are often considered as illogic are perfectly rational, if one admits that human agents reason coinductively.

This paper has been rejected by the International Journal of Game Theory  and the report is worth reading.

 In this paper we study carefully and formally the dollar auction game using coinduction and we show that unlike what is commonly admitted the behavior which consists in bidding forever and which is called escalation is rational. Escalation is typical of an infinite game and tools conceived for studying infiniteness are mandatory and they are what coinduction provides.

This paper has been rejected by the journal Games and Economic Behavior and the report is a piece of anthology of what can be written by somone who knows nothing about coinduction and computability.  Here is my answer.

Epistemic and common knowledge logic

Computational interpretation of classical logic

Explicit substitutions

Counting lambda terms

Lambda calculus is the basis of functional programming and higher order proof assistants. However, little is known about combinatorial properties of lambda terms, in particular, about their asymptotic distribution and random generation. This paper tries to answer questions like: How many terms of a given size are there? What is a "typical" structure of a simply typable term? Despite their ostensible simplicity, these questions still remain unanswered, whereas solutions to such problems are essential for testing compilers and optimizing programs whose expected efficiency depends on the size of terms. Our approach toward the afore-mentioned problems may be later extended to any language with bound variables, i.e., with scopes and declarations. This paper presents two complementary approaches: one, theoretical, uses complex analysis and generating functions, the other, experimental, is based on a generator of lambda-terms. Thanks to de Bruijn indices, we provide three families of formulas for the number of closed lambda terms of a given size and we give four relations between these numbers which have interesting combinatorial interpretations. As a by-product of the counting formulas, we design an algorithm for generating lambda terms. Performed tests provide us with experimental data, like the average depth of bound variables and the average number of head lambdas. We also create random generators for various sorts of terms. Thereafter, we conduct experiments that answer questions like: What is the ratio of simply typable terms among all terms? (Very small!) How are simply typable lambda terms distributed among all lambda terms? (A typable term almost always starts with an abstraction.) In this paper, abstractions and applications have size 1 and variables have size 0.

        A simple way of counting lambda terms.

On counting environments

Object calculus

Termination of first order term rewriting systems

An rpo like ordering: the Decomposition ordering

The presentation of the recursive decomposition ordering.

Polynomial orderings

Other topics related to orderings


Rewriting environments

A description of the completion of a set of identities by a set of inference rules has allowed recent progresses in proving its completeness.  But there existed no attempt to use this description in an actual implementation.  This paper shows that this is feasible using a functional programming language namely CAML.  The implementation uses a toolkit, a set of transition rules and a short procedure for describing the control.  A major role is played by the data structure on which both the transition rules and the control operate. Three versions of the classical Knuth-Bendix completion and two versions of the unfailing completion are proposed.

Old publications

For Fun

Pierre Lescanne