We present a new algorithm for monotonic regression in one or more explanatory variables. Formally, our method generalises the well-known PAV (pool-adjacent-violators) algorithm from fully to partially ordered data. The computational complexity of our algorithm is O(n2). The goodness-of-fit to observed data is much closer to optimal than for simple averaging techniques.