  We describe the semantic foundations for elicitation of generalized
additively independent (GAI) utilities using the minimax regret criterion, and
propose several new query types and strategies for this purpose. Computational
feasibility is obtained by exploiting the local GAI structure in the model. Our
results provide a practical approach for implementing preference-based
constrained configuration optimization as well as effective search in
multiattribute product databases.
