Probabilistic Matrix Inspection and Group Scheduling

Abstract

Consider an event organizer who is trying to schedule a group meeting. Availability of agents is unknown to the organizer a priori, but the organizer may have probability estimates on availability of each agent for each date/time option. The organizer can ask an agent to reveal her availability, but it causes inconvenience for the agent, and thus the organizer wishes to find an agreeable outcome at a minimum number of such queries. Motivated by this example, we study the Probabilistic Matrix Inspection problem in which we are given a matrix of Bernoulli random variables that are mutually independent, and the objective is to determine whether the matrix contains a column consisting only of 1's. We are allowed to inspect an arbitrary entry at unit cost, which reveals the realization of the entry, and we wish to find an inspection policy whose expected number of inspections is minimum. We first show that an intuitive greedy algorithm exists for 1-row and 1-column matrices, and we generalize this to design an algorithm that finds an optimal policy in polynomial time for the general case.