Leírás
Az előadásban olyan nemdeterminisztikus döntéshozási modellekről lesz szó, melyekben garantálható, hogy véges időn belül 1 valószínűséggel konszenzus alakul ki a szavazók között. Effajta modelleket több helyen alkalmaznak, pl. számítógépes hálózatok szinkronizálásában, vagy járványok terjedésének vizsgálatában.
Elemzünk egy konkrét esetet, amikor az n szavazó egy kör alakú asztal körül ül, és mindenki csak a két szomszédjával kommunikál. Az egyik szavazási protokoll alapján minden körben véletlenszerűen választunk egy olyan embert, akinek eltér valamelyik szomszédjától a véleménye, majd ez a szavazó ,,ráerőlteti´´ a döntését valamelyik tőle eltérő véleményű szomszédjára. Nemrég azt igazolták, hogy várhatóan legfeljebb $33n^2$ lépésben kialakul a konszenzus, bármilyen véleménye is volt kezdetben az n résztvevőnek; de számítógépes szimulációk alapján szinte biztosra vehető volt, hogy a valós nagyságrend a legrosszabb esetben $n^2/4$ lépés körül van. Vázlatosan bemutatom, hogyan javítható meg teljesen elemi eszközökkel a fenti korlát az aszimptotikusan helyes $n^2/4+O(n^{3/2})$ becsléssé.
Egyéb modellek várható futási idejére és az egyes, konszenzussal kapható szavazási eredmények valószínűségére adunk további aszimptotikus becsléseket a körgráf mellett pl. a csillag gráfban és az Erdős-Rényi féle véges $G(n,p)$ véletlen gráfban is.