Composition, atomic structure, and electronic properties of TM$_x$Mg$_y$O$_z$ clusters (TM = Cr, Ni, Fe, Co, $x+y leq 3$) at realistic temperature $T$ and partial oxygen pressure $p_{textrm{O}_2}$ conditions are explored using the {em ab initio} atomistic thermodynamics approach. The low-energy isomers of the different clusters are identified using a massively parallel cascade genetic algorithm at the hybrid density-functional level of theory. On analyzing a large set of data, we find that the fundamental gap E$_textrm{g}$ of the thermodynamically stable clusters are strongly affected by the presence of Mg-coordinated O$_2$ moieties. In contrast, the nature of the transition metal does not play a significant role in determining E$_textrm{g}$. Using E$_textrm{g}$ of a cluster as a descriptor of its redox properties, our finding is against the conventional belief that the transition metal plays the key role in determining the electronic and therefore chemical properties of the clusters. High reactivity may be correlated more strongly with oxygen content in the cluster than with any specific TM type.