Game Theory and Algorithmic Mechanism Design

Game theory is an appropriate mathematical tool for analyzing interactions of agents. Professor Sim's recent work in game theory involves 1) devising a  robust bargaining mechanism that is incentive compatible, strongly group strategyproof, shill resistant, and computationally efficient (extensive mathematical results developed in two stages were published in two journal papers in Dynamic Games and Applications and Computational Economics), and 2) developing a bargaining theory for fog computing, and 3) formulating a coalition game for cloud computing.

1) Incentive-compatible, strongly group strategyproof, and shill resistant bargaining mechanism: Professor Sim is the first to devise an algorithmic bargaining mechanism and to provide mathematical evidence to validate that his mechanism has highly desirable game-theoretic and algorithmic properties. In the Sim bargaining mechanism, the bargaining process is modeled as a multi-period simultaneous-move dynamic game where incompletely informed players (represented by software agents) repeatedly interact over a number of discrete time periods and all players make their moves simultaneously in each period.

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

• Strong group strategyproofness: Game-theoretic analysis validates that the Sim bargaining mechanism is strongly group strategyproof because it satisfies the commonly adopted condition of group strategyproofness (i.e., 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) and two additional stronger collusion-resistant conditions that: 1) there is no net collusive surplus from coordinated price shading (as well as coordinated price markup) and 2) every agent cannot increase his/her utility 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.

Furthermore, computational complexity analyses validate that his 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.

   Significance: The collective results in both Professor Sim’s journal papers in Dynamic Games and Applications and Computational Economics provide recommendations on how to best set the bargaining rules and bargaining strategy such that all agents have incentives to behave in a manner consistent with the optimal solution and bargaining activities can be carried out with low computational and communication overheads, while individual price shading (as well as individual price shading), collusion, and identity faking for illicit trading become unprofitable or unfeasible. Given the ease to collude for manipulating resource prices and to fake identities in Internet environments, such a robust bargaining mechanism is indispensable for resource pricing in fog computing. Since agents’ strategies are in equilibrium, no agent has any incentive to diverge from the bargaining strategy recommended by the Sim bargaining mechanism. Such a stable bargaining mechanism is highly desirable because fewer computational resources need to be spent on outguessing an agent’s opponent or discovering the opponent’s optimal choice.

2) Fog Bargaining Theory: 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. This preliminary work resulted in the publication of the No. 1 Most Popular Paper in the IEEE Letters of the Computer Society.  In 2019, he devised a computationally efficient fog bargaining mechanism. In 2020, Professor Sim developed the Sim’s Fog Bargaining Theory which validates that the bargaining solution generated by his computationally efficient fog bargaining mechanism satisfies the famous Nash’s axioms. Game-theoretic analysis prove 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.

3) Intercloud coalition game: Professor Sim defined a new class of game called InterCloud coalition game that characterizes the formation of coalition of clouds (a federation of clouds that cooperate with one another by drawing upon each other’s resources to satisfy consumers’ demands), devised coalition formation protocols and strategies, and provided mathematical proofs to show that the coalition formation strategies 1) converge to a subgame perfect equilibrium, i.e., a steady state in which each agent's action results in its best outcome and 2) enable the profit of an InterCloud coalition to be fairly divided among all members, i.e., each Cloud provider obtaining a fair share of the profit that is equal to its Shapley value. Professor Sim's paper reporting these novel and significant contributions was the No. 1 Most Popular Paper in the IEEE Transactions on Cloud Computing in February 2017.

Professor Sim’s previous contributions focus on

4) proving both the sequential equilibrium and market equilibrium of the strategies of market-driven negotiation agents

5) proving the Nash equilibrium of the strategies of partially cooperative agents

6) analysis of an agent-based coalition formation mechanism in e-markets

7) devising a distributed algorithm for coalition formation in resource co-allocation

8) analyzing the impact of selfish behaviors of Internet users and operators

Representative Publications

1. K. M. Sim. A Strongly Group Strategyproof and Shill Resistant Bargaining Mechanism for Fog Resource Pricing.  Dynamic Games and Applications (2024), Springer. https://doi.org/10.1007/s13235-023-00550-7  Click here for a view-only version of this paper provided by Springer Nature SharedIT link.    

2. K. M. Sim.  An Incentive-Compatible and Computationally Efficient Fog Bargaining Mechanism. Computational Economics Volume 62, issue 4, December (2023), pages 1883 - 1918. https://doi.org/10.1007/s10614-022-10324-9   Click here for a view-only version of this paper provided by Springer Nature SharedIT link.   

3. K. M. Sim. Cooperative and Parallel Fog Discovery and Pareto Optimal Fog Commerce Bargaining. IEEE Transactions on Computational Social Systems, DOI: 10.1109/TCSS.2021.3129253.  Click here to download preprint.

• Click here to download the supplemental material that accompanies this paper.

4. K. M. Sim.  Agent-based Interactions and Economic Encounters in an Intelligent InterCloud. IEEE Transactions on Cloud Computing (Impact factor: 7.928), Vol. 3, No. 3, pp. 358-371, July-September, 2015. Download the supplemental materials here or at http://ieeexplore.ieee.org/xpl/abstractMultimedia.jsp?arnumber=7005451&punumber%3D6245519 Click here to download preprint

• was the No. 1 Most Popular Paper in IEEE Transactions on Cloud Computing in February 2017.

Other Publications

Click here to view Professor Sim's selected papers on game-theoretic analyses of multiagent systems.

Special Issue

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.