Professor Benjamin Kwang Mong Sim is a pioneer and a leading researcher in Agent-based Fog Computing and intelligent resource management in fog and edge.
Earliest work: Aside from being the first to coin the terms "Agent-based Fog Computing" , "Fog Commerce", "intelligent fog", and "intelligent edge", Professor Sim is the first to develop a family of agent-based techniques that are both optimal and robust and computationally efficient and scalable for bolstering 1) resource discovery, 2) resource selection, and 3) resource pricing in fog computing.
Mathematical rigor: Computational complexity analyses validate that Sim's algorithms for bolstering resource discovery, resource selection, and resource pricing in fog computing have either logarithmic complexity or linear complexity. Extensive game-theoretic analyses in two journal papers in Dynamic Games and Applications and Computational Economics validate that the Sim bargaining mechanism for pricing fog computing resources is 1) incentive-compatible (i.e., it provides incentives that motivate all agents in a fog resource market to behave in a manner consistent with the optimal solution), 2) strongly group strategyproof (i.e., it is strongly resistant to collusion), and 3) shill resistant (i.e., it is not susceptible to identity faking for illicit trading). Additionally, game-theoretic analysis in another journal paper validates that the Sim bargaining solution for pricing fog computing resources posses the same set of desirable properties as the famous bargaining solution developed by Nobel Laureate John Nash.
Significance: Since fog nodes are light-weight resources (i.e., they are small-scale computer systems), computational efficiency is a critical property of fog resource allocation algorithms. Given the ease to collude for manipulating resource prices and to fake identities in Internet environments, the Sim bargaining mechanism, being both strongly group strategyproof and shill resistant, is indispensable for resource pricing in fog computing. The Sim bargaining mechanism is highly desirable because being incentive-compatible, it motivates fog agents to behave in a manner consistent with the optimal solution.
Interdisciplinarity: Agent-based fog computing is an interdisciplinary research spanning the areas of fog computing, computational complexity, multiagent systems, bargaining theory, and mechanism design, culminating in the publication of the research results in this project in both 1) journals in the field of computer science such as IEEE Transactions on Services Computing, IEEE Transactions on Computational Social Systems, and IEEE Letters of the Computer Society and 2) journals in the field of game theory and economics such as Dynamic Games and Applications and Computational Economics.
Technical Contributions
1. Economically-efficient and Computationally-efficient Fog Price Bargaining: Professor Sim is the first to introduce bargaining as an economic mechanism for pricing fog computing resources and he is the first to devise a bargaining theory and NUMEROUS NOVEL bargaining mechanisms that are specific to fog resource pricing.
In 2018, Professor Sim 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.
In 2019, 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.
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 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.
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 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.
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.
2. Computationally-efficient and Scalable Fog Resource Discovery: Professor Sim is the first to develop computationally-efficient and scalable agent-based techniques for bolstering resource discovery in fog computing.
In a preliminary work in 2018, Professor Sim devised a novel agent-based gossip algorithm for facilitating fog resource discovery. He provided mathematical proofs to validate that his gossip-based algorithm is computationally efficient because the time complexities for processing and propagating resource requests are linear and logarithmic, respectively.
In 2020, Professor Sim devised a family of cooperative and parallel agent-based fog resource discovery algorithms, called the KM-gossip algorithm. Using K broker agents to disseminate resource requests, the KM-gossip algorithm advances the state-of-the-art in many ways and have the following highly-desirable properties:
1) Computational efficiency: Mathematical evidence validates that the KM-gossip algorithm is computationally efficient since it has logarithmic time complexity and the number of cycles needed to propagate each resource request to all nodes in a fog network is logarithmic in the number of nodes in the network.
2) Scalability: The KM-gossip algorithm is scalable because with growing numbers of fog nodes and IoT devices, more broker agents can be added to facilitate larger-scale information dissemination.
3) Cooperative and parallel information dissemination: The KM-gossip algorithm is designed to enable many different broker agents to work together by relying on each other to disseminate resource request to different sets of fog nodes. At each information dissemination cycle, multiple broker agents carry out parallel dissemination of each resource request by simultaneously propagating each resource request to different groups of fog nodes.
4) Generalization: The KM-gossip algorithm is a generalization of the gossip algorithm. In the KM-gossip algorithm, at every information dissemination cycle, each agent disseminates information to a group of M agents. If M equals one, the KM-gossip algorithm reduces to the gossip algorithm. In the gossip algorithm, at every information dissemination cycle, each agent disseminates information to one agent.
5) Low overhead: Empirical results show that the family of KM-gossip algorithms generates significantly much lower overhead than closely related algorithms.
3. Computationally-efficient Fog Resource Selection: Professor Sim devised a reasoning technique for bolstering fog resource selection by enabling agents to reason about the similarities between user requirements and resource profiles. He provided mathematical proofs to validate that his similarity reasoning technique is computationally efficient because it has linear time complexity.
4. Survey and Tutorial: Professor Sim is the first to contribute an IEEE Transactions survey-tutorial paper on intelligent resource management in fog computing and edge computing. In his survey-tutorial paper, he provides readers with the foundational knowledge for devising intelligent fog and intelligent edge agents by 1) explicating the key difference between fog computing and edge computing, and between fog computing and cloud computing, 2) explaining why developing agents for fog resource management is more challenging than developing cloud agents, 3) suggesting the desirable properties of fog agents, and 4) providing clear and detailed expositions of the state-of-the-art agent-based techniques for intelligent resource management in fogs and edges.
Publications
1. K. M. Sim. A Strongly Group Strategyproof and Shill Resistant Bargaining Mechanism for Fog Resource Pricing. Dynamic Games and Applications Volume 14, issue 5, November (2024), pages 1238–1267. 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, Vol. 9, No. 4, pp. 1112 - 1121, August, 2022. Click here to download preprint.
Click here to download the supplemental material that accompanies this paper.
4. K. M. Sim. Intelligent Resource Management in Intercloud, Fog, and Edge: Tutorial and New Directions. IEEE Transactions on Services Computing, Vol.15, No. 2, pp.1157 - 1174, March-April, 2022. Click here to download preprint.
5. K. M. Sim. Agent-based Fog Computing: Gossiping, Reasoning, and Bargaining. IEEE Letters of the Computer Society. Volume: 1 , Issue: 2 , Jul.-Dec. 2018, pages 21-24. DOI: 10.1109/LOCS.2018.2886828. Click here to download preprint.
6. K. M. Sim. A Computationally Efficient Bargaining Mechanism for Fog Commerce. IEEE Letters of the Computer Society. Volume: 2 , Issue: 1 , Jan.-Mar. 2019, pages 5-8. DOI: 10.1109/LOCS.2019.2906156. Click here to download preprint.