Skyline Queries have recently received a lot of attention due to their intuitive query capabilities. Following the concept of Pareto optimality all "best" database objects are returned to the user. However, this often results in unmanageable large result set sizes hampering the success of this innovative paradigm. As an effective remedy for this problem, trade-offs provide a natural concept for dealing with incomparable choices. Such trade-offs, however, are not reflected by the Pareto paradigm. Thus, incorporating them into the users? preference orders and adjusting skyline results accordingly needs special algorithms beyond traditional skylining. For the actual integration of trade-offs into skylines, the problem of ensuring the consistency of arbitrary trade-off sets poses a demanding challenge. Consistency is a crucial aspect when dealing with multi-dimensional trade-offs spanning over several attributes. If the consistency should be violated, cyclic preferences may occur in the result set. But such cyclic preferences cannot be resolved by information systems in a sensible way. Often, this problem is circumvented by restricting the trade-offs? expressiveness, e.g. by altogether ignoring some classes of possibly inconsistent trade-offs. In this paper, we will present a new algorithm capable of efficiently verifying the consistency of any arbitrary set of trade-offs. After motivating its basic concepts and introducing the algorithm itself, we will also show that it exhibits superior average-case performance. The benefits of our approach promise to pave the way towards personalized and cooperative information systems.