  Markov Logic Networks (MLNs) are well-suited for expressing statistics such
as "with high probability a smoker knows another smoker" but not for expressing
statements such as "there is a smoker who knows most other smokers", which is
necessary for modeling, e.g. influencers in social networks. To overcome this
shortcoming, we study quantified MLNs which generalize MLNs by introducing
statistical universal quantifiers, allowing to express also the latter type of
statistics in a principled way. Our main technical contribution is to show that
the standard reasoning tasks in quantified MLNs, maximum a posteriori and
marginal inference, can be reduced to their respective MLN counterparts in
polynomial time.
