We consider the problem of learning utility functions and rankings with paired inputs and tensor-based kernel functions defined on such inputs. With paired inputs, we refer to the ones consisting of a condition and an object part. The condition being, for example, a query object given at prediction time, the learned model assigns scores for a set of target objects also given at prediction time, that indicate the conditional utility of the targets for the query. We present a new learning algorithm for the considered setting whose computational efficiency is improved with tensor-algebraic optimization.