Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909551032270848 |
|---|---|
| author | Ellendula, Aditya Sai Pujari, Arun K Kumar, Vikas Kagita, Venkateswara Rao |
| author_facet | Ellendula, Aditya Sai Pujari, Arun K Kumar, Vikas Kagita, Venkateswara Rao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18668 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids Ellendula, Aditya Sai Pujari, Arun K Kumar, Vikas Kagita, Venkateswara Rao Machine Learning 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. |
| title | Geometric Preference Elicitation for Minimax Regret Optimization in Uncertainty Matroids |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2503.18668 |