Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids
This work addresses decision-making under uncertainty for users in optimization domains, offering incremental improvements in efficiency over prior techniques.
The paper tackles the problem of uncertain matroid optimization by developing an efficient preference elicitation framework that systematically queries user preferences to refine uncertainty regions, achieving optimality with fewer queries and faster than existing methods.
This paper presents an efficient preference elicitation framework for uncertain matroid optimization, where precise weight information is unavailable, but insights into possible weight values are accessible. The core innovation of our approach lies in its ability to systematically elicit user preferences, aligning the optimization process more closely with decision-makers' objectives. By incrementally querying preferences between pairs of elements, we iteratively refine the parametric uncertainty regions, leveraging the structural properties of matroids. Our method aims to achieve the exact optimum by reducing regret with a few elicitation rounds. Additionally, our approach avoids the computation of Minimax Regret and the use of Linear programming solvers at every iteration, unlike previous methods. Experimental results on four standard matroids demonstrate that our method reaches optimality more quickly and with fewer preference queries than existing techniques.