Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids
Аннотация
This paper presents an efficient preference-elicitation framework for uncertain matroid optimization, in which the precise weights are unknown but their possible ranges are known. The core innovation of our approach lies in the systematic elicitation of user preferences, enabling the optimization process to align more closely with decision-makers’ objectives. By incrementally querying preferences between pairs of elements, we iteratively refine the parametric uncertainty regions while leveraging the structural properties of matroids. Our method aims to achieve the exact optimum by reducing regret with a few elicitation rounds. Unlike previous approaches, it avoids computing Minimax Regret and using linear programming solvers at every iteration. Experimental results on four standard matroids demonstrate that our method reaches optimality faster and with fewer preference queries than existing techniques.