Séminaire commun FDD-FiME // A. Kulkarni
- Cet évènement est passé
Séminaire commun FDD-FiME // A. Kulkarni
3 juin 2022 @ 14 h 30 min - 15 h 30 min
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.
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) of the Indian Academy of Sciences, Bangalore, a recipient of the INSPIRE Faculty Award of the Department of Science and Technology, Government of India, 2013, Best paper awards at the National Conference on Communications 2017, Indian Control Conference 2018 and International Conference on Signal Processing and Communication 2018 (runner-up), Excellence in Teaching Award 2018 at IITB and the William A. Chittenden Award, 2008 at UIUC. He has been a consultant to the Securities and Exchange Board of India, HDFC Life Insurance Company, Kotak Mahindra Bank Limited and Bank of Baroda. He presently serves on the IT-Project Advisory Board of SEBI and as Research Advisor to the Tata Consultancy Services. He has been a visitor to MIT in USA, University of Cambridge in UK, NUS in Singapore, IISc in Bangalore and KTH in Sweden.
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) of the Indian Academy of Sciences, Bangalore, a recipient of the INSPIRE Faculty Award of the Department of Science and Technology, Government of India, 2013, Best paper awards at the National Conference on Communications 2017, Indian Control Conference 2018 and International Conference on Signal Processing and Communication 2018 (runner-up), Excellence in Teaching Award 2018 at IITB and the William A. Chittenden Award, 2008 at UIUC. He has been a consultant to the Securities and Exchange Board of India, HDFC Life Insurance Company, Kotak Mahindra Bank Limited and Bank of Baroda. He presently serves on the IT-Project Advisory Board of SEBI and as Research Advisor to the Tata Consultancy Services. He has been a visitor to MIT in USA, University of Cambridge in UK, NUS in Singapore, IISc in Bangalore and KTH in Sweden.