Editing Random ballot (section)

=== Computation ===
It is easy to implement both the RD and the RSD mechanisms in practice: just pick a random voter, or a random permutation, and let each dictator in turn pick the best option. However, sometimes one wants to compute in advance, what is the probability that a certain alternative would be chosen. With RD (when the preferences are strict), this is easy too: the probability that alternative ''x'' is chosen equals the number of voters who rank ''x'' first, divided by the total number of voters. But the situation is different with RSD (when there are indifferences):

* Computing the probabilities is [[♯P|#P]]-hard;<ref name=":1">{{Cite journal |last1=Aziz |first1=Haris |last2=Brandt |first2=Felix |last3=Brill |first3=Markus |date=2013-12-01 |title=The computational complexity of random serial dictatorship |url=https://www.sciencedirect.com/science/article/abs/pii/S0165176513004138 |journal=Economics Letters |language=en |volume=121 |issue=3 |pages=341–345 |arxiv=1304.3169 |doi=10.1016/j.econlet.2013.09.006 |issn=0165-1765 |s2cid=14384249}}</ref>
* There is an efficient algorithm for computing the support (the alternatives chosen with a positive probability);<ref name=":1" />
* There are algorithms with tractable [[parameterized complexity]], where the parameters are: number of objects, number of alternatives, and number of voter types.<ref>{{Cite journal |last1=Aziz |first1=Haris |last2=Mestre |first2=Julián |date=2014-11-01 |title=Parametrized algorithms for random serial dictatorship |url=https://www.sciencedirect.com/science/article/abs/pii/S0165489614000584 |journal=Mathematical Social Sciences |language=en |volume=72 |pages=1–6 |arxiv=1403.0974 |doi=10.1016/j.mathsocsci.2014.07.002 |issn=0165-4896 |s2cid=6719832}}</ref>
* There is an exponential-time algorithm for computing the probabilities in the context of [[fractional approval voting]].<ref name=":02">{{Cite journal |last1=Bogomolnaia |first1=Anna |last2=Moulin |first2=Hervé |last3=Stong |first3=Richard |date=2005-06-01 |title=Collective choice under dichotomous preferences |url=https://www.sciencedirect.com/science/article/abs/pii/S0022053104001322 |journal=Journal of Economic Theory |language=en |volume=122 |issue=2 |pages=165–184 |doi=10.1016/j.jet.2004.05.005 |issn=0022-0531}}</ref>{{Rp|Appendix}}