  The k-regret query aims to return a size-k subset S of a database D such
that, for any query user that selects a data object from this size-k subset S
rather than from database D, her regret ratio is minimized. The regret ratio
here is modeled by the relative difference in the optimality between the
locally optimal object in S and the globally optimal object in D. The
optimality of a data object in turn is modeled by a utility function of the
query user. Unlike traditional top-k queries, the k-regret query does not
minimize the regret ratio for a specific utility function. Instead, it
considers a family of infinite utility functions F, and aims to find a size-k
subset that minimizes the maximum regret ratio of any utility function in F.
  Studies on k-regret queries have focused on the family of additive utility
functions, which have limitations in modeling individuals' preferences and
decision making processes, especially for a common observation called the
diminishing marginal rate of substitution (DMRS). We introduce k-regret queries
with multiplicative utility functions, which are more expressive in modeling
the DMRS, to overcome those limitations. We propose a query algorithm with
bounded regret ratios. To showcase the applicability of the algorithm, we apply
it to a special family of multiplicative utility functions, the Cobb-Douglas
family of utility functions, and a closely related family of utility functions,
the Constant Elasticity of Substitution family of utility functions, both of
which are frequently used utility functions in microeconomics. After a further
study of the query properties, we propose a heuristic algorithm that produces
even smaller regret ratios in practice. Extensive experiments on the proposed
algorithms confirm that they consistently achieve small maximum regret ratios.
