Stochastic diffusion search and voting methods

Abstract

This study compares known social choice rules in the context of agent based search and introduces two new variants of stochastic diffusion search algorithm. Performance comparison to match a correct ordering of 36 voting algorithms that are derived from 23 known social choice rules are made. A simple text search framework is used for the simulation where agents are given parts of a search key. Individual preferences of agents are then fed to 36 different voting algorithms. Results are compared against the known correct ordering and correct top choices. A similarity coefficient and a top choice match coefficient is used to compare the performances of the voting algorithms. Simulations are made for each length of search key part and each length of search space. A population based search algorithm, stochastic diffusion search (SDS), is improved to include different voting methods. A shared memory and an individual memory variant are developed and performances compared against original SDS. Tests are made with text and image search frameworks. The similarity and top choice match coefficients are used for the text search framework. Image test performances are measured by calculating distance of the found location to the known correct location of the image. It is found that the new algorithms developed in this study considerably outperforms the original SDS algorithm.