The choice of a bidding language is crucial in auction design in order to correctly capture bidder utilities. We propose a
new bidding model for the Adwords auctions of search engine advertisement –
decreasing valuation bids. This provides a richer language than the current model for advertisers to convey their preferences. Besides providing more
expressivity, our bidding model has two additional advantages: It is an
add-on to the standard model, and retains its simplicity of expression. Furthermore, it allows efficient algorithms – we show that
the greedy (highest bid) algorithm retains its factor of 1/2 from the standard bidding model, and also provide an optimal
allocation algorithm with a factor of 1-1/e (as is case in the standard bidding model).
We also show how these bidding languages achieve a good trade-off between expressivity and complexity – we demonstrate a slight
generalization of these models for which the greedy allocation algorithm has an arbitrarily bad competitive ratio.