It turned out that my DE (i3 in this case) did not have polkit agent running. Manually running one (from MATE) makes things work. Maybe it is possible to detect the missing agent somehow, or add it to documentation?