Complex, interdependent multi-issue negotiations in real-world settings, are often hampered by the rigid structuring of interdependent issues. When the issue hierarchy is static, negotiations tend to yield suboptimal agreements, as parties are unable to efficiently respond to changing preferences. Automated negotiations with multiple interdependent issues face significant challenges due to dynamic preferences and the “curse of dimensionality.” We introduce a dynamic negotiation model that automatically adjusts issue hierarchies during negotiations. Unlike static models reliant on human-defined hierarchies, our approach integrates dynamic issue clustering, BATNA-based adjustments, and Multi-Attribute Utility Theory (MAUT) for preference modeling. Simulations across complex scenarios show that agents using the dynamic model achieve significantly higher utility outcomes by re-clustering issues and adapting to changing conditions, optimizing negotiation results.