Je partirai de deux “théorèmes” faux : Le premier est dû à Kapranov et Voevodsky et dit essentiellement que l'on peut représenter les types d'homotopie par des infini-catégories strictes dont toutes les flèches sont faiblement inversibles. Le deuxième est la preuve par Johnstone et Carboni (et Batanin) que la catégorie des polygraphes est une catégorie de préfaisceaux.

Les deux énoncés sont faux pour des raisons très similaires : à chaque fois l'argument clé est l'argument de Eckmann-Hilton, c'est-à-dire le fait que la composition des endomorphismes de n'importe quelle identité dans une infini-catégorie est strictement commutative. Cette commutativité est incompatible avec les deux affirmations précedentes.

Pour cette raison, il est conjecturé que si l'on travaille dans une situation où il n'y pas d'unité, ou bien où les unités sont faibles ou n'interviennent pas alors ces énoncés deviennent vrais. Dans le premier cas il s'agit de la conjecture de semi-strictification de Simpson qui affirme que les types d'homotopie peuvent être représentés par des infini-catégories strictes “sans identités” qui admettent des identités faibles et des inverses faibles. Dans le deuxième cas il s'agit d'une “conjecture” de Johnstone et Carboni qui dit que la catégorie des polygraphes tels que la source et le but de chaque générateur n'est pas une identité est une catégorie de préfaisceaux.

Dans l'exposé je présenterai une preuve de cette dernière “conjecture” et j'expliquerai en quoi cela pourrait permettre d'arriver à une preuve de la conjecture de Simpson.

In traditional “search problems”, an agent aims at exploring a graph in order to find a hidden object as fast as possible. We consider here the Bayesian repeated scenario with several iid instance of the same basic search problem. The objective is, within a given amount of time, to find as many objects as possible with the possibility to leave an instance for the next one at any moment.

We also consider the non-bayesian case with a variant of regret minimization. We provide and analyze several algorithms with fast rates of convergence and/or guaranteed efficiency.