  We study a stochastic variant of monotone submodular maximization problem as
follows. We are given a monotone submodular function as an objective function
and a feasible domain defined on a finite set, and our goal is to find a
feasible solution that maximizes the objective function. A special part of the
problem is that each element in the finite set has a random hidden state,
active or inactive, only the active elements contribute to the objective value,
and we can conduct a query to an element to reveal its hidden state. The goal
is to obtain a feasible solution having a large objective value by conducting a
small number of queries. This is the first attempt to consider nonlinear
objective functions in such a stochastic model. We prove that the problem
admits a good query strategy if the feasible domain has a uniform exchange
property. This result generalizes Blum et al.'s result on the unweighted
matching problem and Behnezhad and Reyhani's result on the weighted matching
problem in both objective function and feasible domain.
