Séminaire FDD-FiME

Ankur A. Kulkarni (Indian Institute of Technology, Bombay)   Title: Extracting Information from a Strategic Sender   Abstract:  The COVID-19 pandemic has brought to the fore the need for segregating travellers, visitors and the general population based on answers given to standardized questionnaires. However, not all such answers can be relied upon to be truthful and therefore the design of such questionnaires for extracting true information becomes a strategic question. We introduce a setting where a receiver aims to perfectly recover a source known privately to a strategic sender by means of such questionnaires. The sender is endowed with a utility function and sends signals to the receiver with the aim of maximizing this utility. Due to the strategic nature of the sender not all the transmitted information is truthful, and signals sent by the sender are not codewords. This leads to the question: how much true information can be extracted by the receiver from such a sender? And how does it extract this information? This talk will study this question in an information-theoretic setting. We show that, in spite of the sender being strategic and the presence of noise in the channel, there is a strategy for the receiver by which it can perfectly recover an exponentially large number of source sequences. Our analysis leads to the notion of the information extraction capacity of the sender. Operationally, this capacity can be thought of as the (exponent of the) optimal length of a questionnaire to be provided to a strategic sender. We show that the information extraction capacity generalizes the Shannon capacity of a graph, and establish bounds on this capacity. We also identify cases where this capacity is equal to its theoretical maximum, and also when it is strictly less than maximum. In the latter case, we show that the capacity is sandwiched between the independence number and the Shannon capacity of a suitably defined graph. These results lead to an exact characterization of the information extraction capacity in a large number of cases. We show that in the presence of a noisy channel, the rate of information extraction achieved by the receiver is the minimum of the zero-error capacity of the channel and the information extraction capacity of the sender. Our analysis leads to insights into a novel regime of communication involving strategic agents. Time permitting, I will consider a dual model in which the receiver plays a passive role by letting the sender commit to a strategy first. Remarkably, we find that the receiver could even benefit from letting the sender take a lead.   Bio:Ankur A. Kulkarni is an Associate Professor with the Systems and Control Engineering group and the Centre for Machine Intelligence and Data Science at the Indian Institute of Technology Bombay (IITB). His research interests include information theory, game theory, stochastic control, combinatorial coding theory problems, optimization, and operations research. He received his B.Tech. from IITB in 2006, followed by M.S. in 2008 and Ph.D. in 2010, both from the University of Illinois at Urbana-Champaign (UIUC). From 2010-2012 he was a post-doctoral researcher at the Coordinated Science Laboratory at UIUC. He was an Associate (from 2015--2018) ...

Maxime Colomb (Inria-IGN), Nicolas Gilet (Inria) et Denis Talay (Inria et Ecole Polytechnique) Titre: ICI : un simulateur INRIA-IGN à l’échelle individuelle de propagation d’épidémie au sein d’une ville Résumé:  Les modèles mathématiques ont été de plus en plus utilisés pour modéliser la propagation de l'épidémie de COVID-19. Ils permettent d'adapter la prise de décision dans l'instauration de nouvelles mesures sanitaires. Toutefois, la plupart des modèles épidémiologiques (entre autres, les modèles macroscopiques SIR/SEIR) reposent sur une représentation très simplifiée des environnements urbains et de la population. Ainsi, les épidémiologistes se sont basés sur des modèles comportementaux (Leung et al, 2020) permettant de dégager les tendances globales de l'épidémie de COVID-19 sur de larges portions d'une population homogène. Bien que ces modèles aient des résultats convenables pour prévoir les tendances globales d'évolution d'une épidémie sur de larges portions de population, ils ne peuvent anticiper les évolutions locales de la contamination sur des populations hétérogènes du point de vue sanitaire, ni prédire les effets de mesures sanitaires ciblées. Comme la contamination par la COVID-19 a les aérosols comme vecteurs, la modélisation des contacts entre individus, et particulièrement en espace clos, est primordiale. Par conséquent, il est nécessaire de prendre en compte la complexité et l’hétérogénéité de l'espace géographique (surface disponible, taux de fréquentation, etc.) et des caractéristiques des individus (situation familiale, profession, âge, etc.). Les modèles correspondants sont appelés modèles individus-centrés et commencent à donner des résultats satisfaisants concernant la modélisation de l'épidémie de COVID-19 (Drogoul et al, 2021). Le projet ICI (INRIA - Collaboration - IGN) est un simulateur de propagation d’épidémie reposant sur une modélisation très détaillée d’un espace urbain et de la circulation des personnes à l’intérieur de cet espace. Il est le fruit d'une équipe pluridisciplinaire entre des chercheurs de l'INRIA, de l'École Polytechnique, du CNRS et de l'IGN. Il a pour but d'évaluer l'évolution de la propagation de l'épidémie au moyen de statistiques de contamination entre individus et d'indicateurs importants (R0, taux d'incidence) calculés à partir des états successifs des populations réalistes simulées. La réplication d'un grand nombre de ces simulations permet de dégager des tendances robustes.Le modèle ICI repose sur le couplage de deux modélisations distinctes. D'une part, l'espace géographique est modélisé d'une manière très précise à l'échelle de l'individu considéré comme appartenant à un ménage et un habitat et fréquentant des points d'intérêts et un lieu de travail. De plus, le modèle ICI intègre les caractéristiques démographiques des individus (type de ménage, sexe, âge) et leurs habitudes de déplacement (trajets domicile/travail, loisirs, etc.). D'autre part, la simulation de la propagation de l'épidémie doit s'adapter à cette échelle fine et détaillée de la population et de l'espace. En raison de la très forte hétérogénéité des caractéristiques de la COVID-19 (temps d’incubation, présence de super-contaminateurs,…), il est nécessaire de prendre en compte de multiples aléas. Une méthode de Monte Carlo consiste à simuler les déplacements quotidiens de la population synthétique en y ajoutant des probabilités liées à l'espace (probabilité de sortie, d’aller au travail,…) et des probabilités de contamination entre individus lors de leurs croisements. Pour la réalisation d'un grand nombre de simulations de transmissions de la maladie au sein de populations de très grande taille, le projet emploie des technologies de calcul haute performance (parallélisation sur des super-calculateurs).Download slides