Header

UZH-Logo

Maintenance Infos

Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment


Weissteiner, Jakob; Heiss, Jakob; Siems, Julien; Seuken, Sven (2022). Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment. In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, Vienna, Austria, 23 July 2022 - 29 July 2022. International Joint Conferences on Artificial Intelligence Organization, 541-548.

Abstract

Many important resource allocation problems involve the combinatorial assignment of items, e.g., auctions or course allocation. Because the bundle space grows exponentially in the number of items, preference elicitation is a key challenge in these domains. Recently, researchers have proposed ML-based mechanisms that outperform traditional mechanisms while reducing preference elicitation costs for agents. However, one major shortcoming of the ML algorithms that were used is their disregard of important prior knowledge about agents' preferences. To address this, we introduce monotone-value neural networks (MVNNs), which are designed to capture combinatorial valuations, while enforcing monotonicity and normality. On a technical level, we prove that our MVNNs are universal in the class of monotone and normalized value functions, and we provide a mixed-integer linear program (MILP) formulation to make solving MVNN-based winner determination problems (WDPs) practically feasible. We evaluate our MVNNs experimentally in spectrum auction domains. Our results show that MVNNs improve the prediction performance, they yield state-of-the-art allocative efficiency in the auction, and they also reduce the run-time of the WDPs. Our code is available on GitHub: https://github.com/marketdesignresearch/MVNN.

Abstract

Many important resource allocation problems involve the combinatorial assignment of items, e.g., auctions or course allocation. Because the bundle space grows exponentially in the number of items, preference elicitation is a key challenge in these domains. Recently, researchers have proposed ML-based mechanisms that outperform traditional mechanisms while reducing preference elicitation costs for agents. However, one major shortcoming of the ML algorithms that were used is their disregard of important prior knowledge about agents' preferences. To address this, we introduce monotone-value neural networks (MVNNs), which are designed to capture combinatorial valuations, while enforcing monotonicity and normality. On a technical level, we prove that our MVNNs are universal in the class of monotone and normalized value functions, and we provide a mixed-integer linear program (MILP) formulation to make solving MVNN-based winner determination problems (WDPs) practically feasible. We evaluate our MVNNs experimentally in spectrum auction domains. Our results show that MVNNs improve the prediction performance, they yield state-of-the-art allocative efficiency in the auction, and they also reduce the run-time of the WDPs. Our code is available on GitHub: https://github.com/marketdesignresearch/MVNN.

Statistics

Citations

Dimensions.ai Metrics

Altmetrics

Downloads

1 download since deposited on 09 Mar 2023
0 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Scopus Subject Areas:Physical Sciences > Artificial Intelligence
Scope:Learning and pedagogical research
Language:English
Event End Date:29 July 2022
Deposited On:09 Mar 2023 08:46
Last Modified:06 Mar 2024 14:39
Publisher:International Joint Conferences on Artificial Intelligence Organization
OA Status:Closed
Free access at:Official URL. An embargo period may apply.
Publisher DOI:https://doi.org/10.24963/ijcai.2022/77
Official URL:https://arxiv.org/abs/2109.15117
Related URLs:https://doi.org/10.24963/ijcai.2022/77 (Publisher)
https://github.com/marketdesignresearch/MVNN (Author)
Other Identification Number:merlin-id:23343