On the Effectiveness of Modeling Uncertain Constraint-Based Utility Functions with Quadratic Polynomials
With Applications in Autonomous Negotiations
V.M. Þórsson (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Alexander Heinlein – Mentor (TU Delft - Numerical Analysis)
CM Jonker – Graduation committee member (TU Delft - Interactive Intelligence)
R.J. Fokkink – Graduation committee member (TU Delft - Applied Probability)
W.P. Brinkman – Graduation committee member (TU Delft - Interactive Intelligence)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The curse of dimensionality poses a fundamental challenge in autonomous negotiations: as the number of issues and their interdependencies increase, exhaustive evaluation of the outcome space quickly becomes infeasible. This thesis addresses this problem by introducing a surrogate-based method that approximates uncertain hypercubic constraint-based utility functions with quadratic polynomials. An autonomous negotiation agent can then search for high-utility outcomes in this surrogate model. The research objective was to investigate how efficiently an autonomous negotiation agent can identify high-utility bids with this approach, and how this approach compares to linear approximations and established benchmark agents.
The main contributions of this thesis are threefold. First, it introduces a probabilistic complexity measure for these hypercubic functions, capturing how parameters such as dimensionality, constraint width, the number of constraints, and the number of issues interact to shape the function's complexity. Second, it develops a novel agent that leverages a regression model with quadratic basis functions to construct a surrogate model of a hypercubic constraint-based utility function. Third, it evaluates the agent through extensive experiments, demonstrating how performance scales with complexity. Following the steps outlined in this thesis, the performance of surrogate models can be directly compared.
The results demonstrate that the surrogate-based method is a promising approach, as the agent constructed in this thesis outperforms the agents from the 2014 Automated Negotiating Agent Competition which used similar scenarios as those considered in this thesis. These agents all have in common that they directly search the utility function as opposed to a surrogate model of it. Furthermore, the results indicate that simple basis functions, such as quadratic ones, enable the agent to reach the global maximum of its utility function in low-complexity hypercubic cases, with performance scaling reasonably well up to medium complexity. Beyond this point, however, performance deteriorates rapidly, clearly signaling the need for more expressive surrogate models.