Processes for a Colony Solving the Best-of-N Problem using a Bipartite Graph Representation

EasyChair Preprint 5525

Abstract

Agent-based simulations and differential equation models have been used to analyze distributed solutions to the best-of-N problem. This. paper shows that the best-of-N problem can be also solved using a graph-based formalism that abstractly represents (a) agents and solutions as vertices, (b) individual agent states as graph edges, and (c) agent state dynamics as edge creation (attachment) or deletion (detachment) between agent and solution. The paper identifies multiple candidate attachment and detachment processes from the literature, and then presents a comparative study of how well various processes perform on the best-of-N problem. Results not only identify promising attachment and detachment processes but also identify model parameters that provide probable convergence to the best solution. Finally, processes are identified that maybe suitable for the best-M-of-N problem.

Keyphrases: Best-M-of-N, Hub-Based Colonies, best-of-n, bipartite graph, swarms

@booklet{EasyChair:5525,
  author    = {Puneet Jain and Michael Goodrich},
  title     = {Processes for a Colony Solving the Best-of-N Problem using a Bipartite Graph Representation},
  howpublished = {EasyChair Preprint 5525},
  year      = {EasyChair, 2021}}