Image Credit: Wikimedia Commons

The following article was originally written by Ms. Arati Halbe and published here.

Offering limited options to choose from for a multiple choice setting recovers more accurate and truthful information than presenting the complete range of options, reveals IIT Bombay study.

One would recall, with pain and much irritation, the times when one had to travel internationally during the COVID-19 times. If you happened to be the one inside the city receiving passengers, you would be afraid; what if the incoming passengers travelled through places with higher infection? If you were the traveller, you would like to believe that you are not infected and would want to avoid reporting your travel through COVID-19-affected cities. Health officers, on the other hand, had a tough situation to deal with. They had to extract as much truth from people unwilling to disclose the whole truth. All they could do was ask questions and believe the answers were true.

If you are wondering if there is any chance of recovering the truth, you can stop worrying! In a first of its kind study, Dr Anuj Vora and Prof Ankur Kulkarni from the Indian Institute of Technology Bombay (IIT Bombay) tackle the challenge of how the receiver can design the right questions to learn as much truth as possible when the sender is not entirely cooperative, and there could be errors in communication due to noise.

Problems related to extracting information from people who are unwilling to disclose information or non-cooperative senders occur frequently, say, during negotiations. Negotiating parties may not give truthful information because they think that disclosing some facts may lead to an unfavourable deal. Extraction of information from non-cooperative senders is studied extensively in mechanism design theory. Roger Myerson laid the foundations of mechanism design theory and was awarded the 2007 Nobel Memorial Prize in Economic Sciences, along with Leonid Hurwicz and Eric Maskin.

“Mechanism design has not attempted to quantify the amount of information obtainable in settings where all information may not be obtainable,” explains Prof Ankur Kulkarni. In situations like the one faced by the health officer in COVID-19 times, it may not be possible to retrieve the complete travel history of all the travellers. However, it is important to know how much information can be obtained. “Quantification of information is the subject of information theory. We are the first to perform an information theoretic analysis of a problem that is broadly within the domain of mechanism design,” says Prof Kulkarni.

The current study shows that despite the sender being non-cooperative and the communication being noisy, the receiver can still recover a huge number of possible correct answers. At the same time, there are a huge number of correct answers that cannot be recovered, however cleverly the questionnaire is designed.

“Our results show on the one hand how a receiver may strategise to obtain information from such agents, and on the other that there will usually be blind spots in the knowledge of the receiver, regardless of how it strategises,” say the researchers.

Vora and Kulkarni quantify the amount of information that can be extracted by defining a quantity called the ‘information extraction capacity’. They established a method to calculate the range of values (the upper and lower limits) for this quantity and show that in several cases, the information extraction capacity can be exactly calculated. Their study provides strategies that the receiver can use to design the questionnaire and also a structural understanding of the kind of information that can be recovered.

The study assumes that the receiver will ask just one question and present a list of possible answers as options from which the sender chooses one correct answer. For example, a health officer may present sequences of cities visited before arriving at the current port. In a naive approach, the officer would list all possible sequences as the choices. However, it turns out that this approach gives travellers more opportunities to lie if they have information to hide. If the options are limited, travellers who wish to disclose some travel sectors but hide others will tend
to report more truthfully. The officers can recover the most truth by keeping the number of options within the optimal range, as suggested by the study.

The health officer may wish to know only a few cities visited previously. Thus, the length of the ‘sequence’ of cities may be limited to just a handful. However, in another situation, say when tax officers are trying to trace a chain of financial transactions, the sequence they wish to recover will be longer. More choices will need to be offered for the multiple-choice questions the officers ask. The number of optimal choices to be offered will grow with the increasing length of the sequence to be recovered. The researchers define the rate of growth of the number of optimal choices as the information extraction capacity. The quantity of communication resources required when communicating with a non-cooperative sender depends on the information extraction capacity.

Vora and Kulkarni bring in an aspect from information theory and model the communication when the communication itself may be noisy or not very accurate. For example, if one is trying to send a message over a communication line and say the line changes the letter B to D each time, then if the receiver gets D, they will assume it is D even when B is sent, making communication ambiguous for two letters (B and D). What it means in this case is that only 24 letters out of 26 can be sent without error. The amount of information that can be sent without errors is termed the zero-error capacity of the channel. In the current study, Vora and Kulkarni established that to utilise the information extraction capacity of the sender, the zero-error capacity of the channel needs to be more than the information extraction capacity and the receiver can extract a huge number of sequences in this case.

The study offers an insight into the basis of why certain questionnaires, such as in immigration or options offered by customer care bots, are not exhaustive. As users, we may frequently need to select an option that closely matches our case when we do not find an exact match. “Our study demonstrates that providing limited options in multiple choice questions may not be due to bad design, but it may be a strategy crafted to obtain as much truthful information as possible from a large number of users,” comments Prof Kulkarni.

This research was supported by the grant from the Science and Engineering Research Board, Department of Science and Technology, India.

The finding has applications in different fields, including finance, control systems, intelligence gathering and national security, market research and diplomatic negotiations. “Our results in this paper provide not only strategies for the receiver, but also a structural understanding of the type information that can potentially be recovered,” concludes Prof Kulkarni.

**********************************************************

The original academic article titled Shannon Meets Myerson: Information Extraction from a Strategic Sender was written by IIT Bombay’s researchers and published in the journal, Mathematical Social Sciences, Volume 131.

The original paper can be found here.