We study the parallel Minority Game, where a group of agents, each having two choices, try to independently decide on a strategy such that they stay on the minority between their own two choices. However, there are multiple such groups of agents, and some of them have common choices. This overlap brings in additional competition among the agents making the variance reduction in population fluctuation among the different choices a complex optimization problem. We study multiple stochastic strategies and find that the most efficient strategy among these is the one where the agents have just the memory of their last visit to the their alternative choice. The resulting dynamics, even though giving the lowest population variance among the strategies studied here, end up in a frozen state. However, the frozen state does not bring the variance to its lowest possible value; a situation qualitatively analogous to the spin-glass systems.