Automated Negotiation & Bargaining Theory

Negotiation (bargaining) denotes the process of two or more agents (with disparate interests) searching for an agreement on some issues (e.g., price and time slot), and the search process involves exchange of information, relaxation of initial goals, and mutual concessions. Automated negotiation among software agents is required in many different contexts in which conflicts and differences need to be resolved, e.g., resource allocation in Fog computing, Cloud computing, and Grid computing as well as e-commerce and supply chain management. A bargaining theory is an exploration of the relation between the outcome of bargaining and the characteristics of the bargaining situation. 

Professor Sim's research in automated negotiation involves devising optimal negotiation strategies and building software agents that can automatically resolve differences between providers (sellers) and consumers (buyers) by making concessions and reaching agreements on issues such as price and time slot. The bargaining theory that he developed provides the guiding principles for fog computing designers to implement economically-efficient fog resource pricing mechanisms. 

Awards and Accolades

1. ACM Computing Reviews’ 2013 Best of Computing: Notable Article in Computing (please see article entitled, "An augmented EDA with dynamic diversity control and local neighborhood search for coevolution of optimal negotiation strategies.")

2.  No. 1 Most Popular Paper in IEEE Transactions on Cybernetics (please see paper entitled, "Complex and Concurrent Negotiation for Multiple Interrelated e-Markets.")

3. No. 2 Most Popular Paper in IEEE Transactions on Systems, Man and Cybernetics, Part B     (Article title: "Evolving Fuzzy Rules for Relaxed-criteria Negotiation.")

4. Best Paper Award. 2013 IAENG International Conference on Internet Computing and Web Services. Paper title: "Towards a Unifying Multilateral Cloud Negotiation Strategy"

5. Certificate of Merit. 2009 IAENG International Conference on Internet Computing and Web Services. Paper title: "Coordination and Concurrent Negotiation for Multiple Web Services Procurement"

Technical Contributions

Bargaining Theory and Mechanism Design for Fog Computing: In 2020, Professor Sim developed the Sim’s Fog Bargaining Theory which validates that the bargaining solution generated by his fog bargaining mechanism satisfies the famous Nash’s axioms. Game-theoretic analysis proves that the  Sim Bargaining Solution for fog resource pricing satisfies the axioms of

1) Pareto optimality (PAR) (i.e., the solution is best for all agents)

2) Symmetry (SYM) (i.e., the solution is fair to all agents)

3) Scale invariance (INV) (i.e., different scales and different methods can be used to measure agents’ level of satisfaction without affecting the solution)

4) Independence of irrelevant alternatives (IIA) (i.e., reducing the search space by eliminating irrelevant alternatives does not affect the solution).

By showing that the Sim Bargaining Solution has exactly the same set of highly desirable properties as the Nash Bargaining Solution, the Sim’s Fog Bargaining Theory provides the guiding principles for fog computing designers to implement economically-efficient fog resource pricing mechanisms.

In 2021, Professor Sim devised an algorithmic bargaining mechanism for pricing fog computing resources and provided mathematical evidence to validate that his mechanism has highly desirable game-theoretic and algorithmic properties.

• • Incentive Compatibility & Bayesian Nash equilibrium: Game-theoretic analysis validates that the Sim bargaining mechanism is incentive-compatible because it provides incentives that motivate all agents in a fog resource market to behave in a manner consistent with the optimal solution, i.e., every participant can maximize its benefits if all agents adhere to their equilibrium strategies. More specifically, under the setting of bargaining with incomplete information involving many buyers and many sellers in a fog resource market, equilibrium analysis validates that if every agent in the market adheres to the strategy recommended by his bargaining mechanism, then the strategy profile of the agents generally forms a Bayesian Nash equilibrium.  

  • Computational efficiency: Furthermore, computational complexity analyses validate that the Sim bargaining mechanism is also computationally efficient:

• Line time complexity: The procedure for carrying out the Sim bargaining strategy has a linear time complexity.

• Dwindling search space: Using the Sim bargaining strategy, the search space dwindles with every passing round, but the solutions in the search space become progressively better.

• Rapid convergence: The number of rounds for completing bargaining is logarithmic in the number of an agent’s opponents.

• Low communication overhead: Each agent has a linear message complexity.

In 2023, Professor Sim provided new mathematical results to validate that his algorithmic bargaining mechanism for pricing fog computing resources is also strongly group strategyproof and shill resistant.

• • Strong group strategyproofness: Game-theoretic analysis validates that the Sim bargaining mechanism is strongly group strategyproof (i.e., strongly resistant to collusion) because coordinated price shading (as well as coordinated price markup) by coalitions of agents that results in the strict gain of some agent will also result in the strict loss of another agent, there is no net collusive surplus from coordinated price shading (as well as coordinated price markup), and every agent cannot benefit by joining a coalition.

  •   Shill resistance: The Sim bargaining mechanism is not susceptible to identity faking for illicit trading (i.e., it is shill resistant) because in addition to demonstrating that the design of its bargaining rules and bargaining strategy inherently prevents shills from influencing the price proposals of agents in a market, mathematical evidence shows that formation of coalitions with shills is also not feasible. In the Sim bargaining mechanism, using shills, some member of a coalition could capture the entire collusive surplus, thereby leaving all other members with no gain for joining the coalition, and this deters collusion by coalitions of agents.

Automated Negotiation: In the past three decades, Professor Sim introduced many new branches of thinking and award-winning innovations in automated negotiation, including:

1. Pareto Optimal fog bargaining mechanism: Professor Sim is the first to introduce bargaining as an economic mechanism for pricing fog computing resources. In 2018, he devised a novel agent-based fog bargaining mechanism for bolstering dynamic pricing of fog computing resources. He provided game-theoretic proofs to validate that his fog bargaining mechanism is economically efficient because it enables agents to reach Pareto optimal agreements.

2. Computationally efficient and rapidly converging bargaining: Professor Sim also devised a novel layered bargaining mechanism for bolstering fog commerce with the novel and distinguishing feature of enabling agents to conserve computational resources by selectively engaging their bargaining activities only with trading partners with price proposals that are relatively close to theirs. He provided mathematical proofs to validate that the layered fog bargaining mechanism is both computationally efficient and rapidly converging because 1) each agent has a linear message complexity and 2) the number of rounds for each agent to complete bargaining is logarithmic in the number of its trading partners. Both computational efficiency and rapid convergence are essential and desirable properties for fog commerce systems because fog nodes are light-weight resources and are more abundant than cloud data centers. Additionally, he also provided empirical evidence to demonstrate that the layered fog bargaining mechanism outperforms related bargaining mechanisms.

3. Complex and concurrent negotiation: By introducing the novel idea that negotiation activities are not restricted to only one market but concurrent negotiation activities can be carried out in multiple markets, Professor Sim's work on concurrent and complex negotiation offers an entirely new branch of thinking in automated negotiation. In conventional negotiation models, negotiation activities are carried out between two types of agents: buyer and seller agents in only one market and contracts established are irrevocable. Professor Sim is the first to introduce a complex negotiation mechanism in which there are three types of participants (consumer, broker, and provider agents) and many markets, agents can revoke contracts by paying penalties, and the negotiation outcomes in one market can potentially influence the negotiation outcomes in another market. Designed to solve complex negotiation problems involving the dynamic integration of a collection of resources, Professor Sim's work is an important milestone in introducing the next generation of advanced negotiation mechanisms for very complex resource co-allocation problems involving parallel negotiation activities among multiple groups of participants. This work led to the publication of a paper that was the No. 1 Most Popular Paper in IEEE Transactions on Cybernetics. 

4. Cloud resource negotiation: Professor Sim is the first to introduce the idea of using bargaining as a new model for allowing dynamic pricing of Cloud resources and also the first to develop an agent-based testbed for Cloud service-level agreement (SLA) negotiation (published in 2009 and received an Outstanding Paper Nomination in the IEEE International Conference on Industrial Engineering and Engineering Management 2009). Subsequently, his laboratory developed negotiation agents that enable both Cloud providers and consumers to 1) specify their preferences for price, time slot, and quality of service (QoS) and 2) search for mutually acceptable prices, time slots, and levels of QoS. By having a negotiation mechanism for flexible pricing of Cloud resources, providers can benefit from more efficient utilization of their resources, and consumers can benefit from cost saving in some situations and being able to plan the start and termination times for running their applications. Additionally, Professor Sim devised a unifying Cloud negotiation strategy that resulted in the publication of conference paper that received the Best Paper Award.

5. Relaxed-criteria negotiation: Professor Sim's work on relaxed-criteria negotiation redefines the notion of reaching a consensus in negotiation by allowing agents to overlook very small differences in their proposals. Whereas previous (conventional) works on negotiation in simpler market settings focused only on optimizing utilities, Professor Sim's work on relaxed-criteria negotiation introduced a new branch of thinking for solving much more difficult negotiation problems by devising a family of negotiation agents that uses heuristics to improve success rates and negotiation speed.

i. He devised negotiation agents that use a set of fuzzy rules for making decisions to slightly relax their trading terms in the face of (intense) negotiation pressure (e.g., stiff competition).

ii. He has also generalized the idea of relaxed-criteria negotiation by augmenting the designs of negotiation agents with additional fuzzy controllers to allow agents to both 1) raise their expectations in extremely favorable markets and 2) lower expectations in extremely unfavorable markets.

iii. More recently, he devised self-improving relaxed-criteria negotiation agents that can continously evolve their structures to enhance their performance by learning new fuzzy rules as they negotiate in more e-markets. This work led to the publication of a paper that was the No. 2 Most Popular Paper in IEEE Transactions on Systems, Man and Cybernetics, Part B. 

6. Market-driven negotiation: Whereas many e-commerce negotiation agents adopted strategies with fixed concession rates and did not explicitly model market influence, Professor Sim's work on market-driven negotiation is the earliest work to design negotiation agents that make adjustable amounts of concessions taking into account both outside options and market rivalry. Mathematical analyses and empirical studies  show that market-driven agents (MDAs) make prudent compromises in the sense that they do not make excessive concessions in favorable markets nor inadequate concessions in unfavorable markets. By modeling negotiation of MDAs as a game of incomplete information, Professor Sim provided mathematical proofs to show that the negotiation strategies of MDAs converge to a sequential equilibrium.

7. Grid resource negotiation: Professor Sim's work on Grid resource negotiation includes: i) market-driven Grid commerce negotiation, ii) relaxed-criteria Grid resource negotiation and iii) concurrent negotiation for Grid resource co-allocation. Using the GridSim toolkit, his laboratory developed a testbed consisting of market-driven Grid negotiation agents for simulating resource allocation in a computational Grid environment. In his work on relaxed-criteria Grid resource negotiation, agents representing Grid resource providers and consumers are programmed to slightly relax their bargaining criteria under intense pressure (e.g., when the Grid loading is high and few resources are available) with the hope of enhancing their chance of successfully acquiring resources. Professor Sim's laboratory developed two sets of fuzzy rules representing the relaxation criteria for providers and consumers, respectively. His concurrent Grid resource negotiation mechanism enables an agent to conduct simultaneous parallel negotiations with other agents in multiple resource markets for acquiring multiple types of resources and the agent is allowed to renege on a contract by paying a penalty fee.

Professor Sim also devised many novel approaches for finding optimal negotiation strategies, including:

1. proving mathematical theorems for determining an agent’s optimal strategy in negotiation with complete information.

2. devising a novel algorithm called BLGAN that uses  the synthesis of Bayesian learning (BL) and genetic algorithm (GA) to deal with the difficult problem of determining an agent’s optimal strategy in one-to-one negotiation (N) with incomplete information by learning an opponent’s private information. Empirical results show that agents adopting BLGAN achieved significantly better negotiation outcomes than agents adopting either GA or BL.

3. devising an estimation of distribution algorithm for finding optimal negotiation strategies in one-to-one negotiation with incomplete information. This work resulted in the publication of a journal paper that resulted in the award as ACM Computing Reviews’ 2013 Best of Computing: Notable Article in Computing.

Application: Professor Sim has demonstrated the applications of automated negotiation to Fog computing, Cloud computing, Grid computing, e-commerce, supply chain management, and Web services.

Surveys

1.  K. M. Sim. Grid Resource Negotiation: Survey and New Directions. IEEE Transactions on Systems, Man and Cybernetics, Part C*, Vol. 40, No. 3, May 2010, pp. 245-257.

2. K. M. Sim. Unconventional Negotiation: Survey and New Directions. Proceedings of the 9th International Conference on Electronic Business, 2009, pp. 901-907.

3.  K. M. Sim. A Survey of Bargaining Models for Grid ResourceAllocation. ACM SIGeCOM: E-commerce Exchanges, Vol. 5, No. 5, December, 2005.

Other Publications

Click here to view Professor Sim's selected papers on automated negotiation.

Special Issues

1. Guest Editor: K. M. Sim. Special Issue on Game-theoretic Analysis and Stochastic Simulation of Negotiation Agents. IEEE Transactions on Systems, Man, and Cybernetics, Part C, Vol. 36, No. 1, Feb., 2006.

2. Guest Editor: K. M. Sim. Special issue on Learning Approaches for Negotiation Agents and Automated Negotiation. International Journal of Intelligent Systems, Vol. 21, No. 1, Jan. 2006,Wiley, USA.

3. Lead Guest Editor: K.M. Sim. Special issue on negotiation and scheduling mechanisms for multiagent systems. Multiagent and Grid Systems Journal, vol. 4, no. 1, 2008, IOS Press, Holland.