A Greedy Coordinate Descent Algorithm for High-Dimensional Nonlinear Negotiation

摘要

Automated negotiation is a rapidly growing topic in the field of artificial intelligence. Most of the research has been dedicated to linear preferences. Approaching real life negotiations requires more realistic preference profiles to be taken into account. To address this need, nonlinear high-dimensional domains with interdependent issues were introduced. They have however posed a struggle for automated negotiation agents. The difficulty is that fast, linear models can no longer be used in such domains, and there is no time to consider all possible bids in huge spaces. This paper proposes Group2Agent (G2A), an agent that copes with these complex domains and tries to find high Social Welfare outcomes. G2A uses a variant of the Greedy Coordinate Descent (GCD) algorithm, which can scale linearly with the number of issues and is shown to be effective in locating a meaningful middle ground between negotiating parties. Our results show that G2A reaches an average Social Welfare of 1.79, being only 0.03 below the optimal Social Welfare solution and found the optimal solution itself 3 out of 25 times on pre-competition domains. In conclusion, G2A performs among the top ranking agents when it comes to Social Welfare. Furthermore its search algorithm, GCD, scales better than algorithms such as Simulated Annealing used in other agents.