Martedì 15 novembre 2022 alle ore 12:00 presso il nostro dipartimento il Prof. Jean-Paul Doignon (Emeritus, Department of Mathematics, Université Libre de Bruxelles) terrà un seminario dal titolo: From probabilistic choice to flow polytopes, and back
E' possibile visionare il seminario anche on-line: link Teams
The preferences of a subject over alternatives often vary along time. In the choice setting, the experimenters record the frequency that the subject chooses alternative i when she is proposed a set S of alternatives containing i. To provide an explanation for such observed data, Block and Marschak (1960) introduced in economics the so-called "random utility model", showing that the latter is also a "random ordering model" (the orderings are linear orderings of the set of alternatives and they are latent, that is, not observable). The Multiple Choice Polytope (MCP) is the prediction range of the Block and Marschak model. A complete characterization of the MCP is a remarkable achievement of Falmagne (1978). Apart for a recognition of the facets by Suck (2002), the geometric structure of the MCP was apparently not much investigated. Recently, Chang, Narita and Saito (2022) refer to the adjacency of vertices of the MCP while Turansick (2022) uses a condition which we show to be equivalent to the non-adjacency of two vertices. We characterize the adjacency of vertices and the adjacency of facets.
To derive a more enlightening proof of Falmagne Theorem and of Suck result, Fiorini (2004) assimilates the MCP with the flow polytope of some acyclic network. Our results on adjacencies also hold for the flow polytope of any acyclic network. In particular, they apply not only to the MCP, but also to three other polytopes which Davis-Stober, Doignon, Fiorini, Glineur and Regenwetter (2018) introduced as extended formulations of the weak order polytope, interval order polytope and semiorder polytope (we shall briefly review these notions of order and explain the role of extended formulations in combinatorial optimization).
Referente DEI: Prof. Alfio Giarlotta