document: An expressive mechanism for auctions on the web Auctions are widely used on the Web . Applications range from internet advertising to platforms such as eBay . In most of these applications the auctions in use are single\/multi-item auctions with unit demand . The main drawback of standard mechanisms for this type of auctions , such as VCG and GSP , is the limited expressiveness that they offer to the bidders . The General Auction Mechanism ( GAM ) of ( 1 ) is taking a first step towards addressing the problem of limited expressiveness by computing a bidder optimal , envy free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair . We show that in many practical situations this does not suffice to adequately model the preferences of the bidders , and we overcome this problem by presenting the first mechanism for piece-wise linear utility functions with non-identical slopes and multiple discontinuities . Our mechanism runs in polynomial time . Like GAM it is incentive compatible for inputs that fulfill a certain non-degeneracy requirement , but our requirement is more general than the requirement of GAM . For discontinuous utility functions that are non-degenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium . We also show how our mechanism can be used to compute approximately bidder optimal , envy free outcomes for a general class of continuous utility functions via piece-wise linear approximation . Finally , we prove hardness results for even more expressive settings .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O B O O O O B O O O O O O O O B I I O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O