  We consider prior-free auctions for revenue and welfare maximization when
agents have a common budget. The abstract environments we consider are ones
where there is a downward-closed and symmetric feasibility constraint on the
probabilities of service of the agents. These environments include position
auctions where slots with decreasing click-through rates are auctioned to
advertisers. We generalize and characterize the envy-free benchmark from
Hartline and Yan (2011) to settings with budgets and characterize the optimal
envy-free outcomes for both welfare and revenue. We give prior-free mechanisms
that approximate these benchmarks. A building block in our mechanism is a
clinching auction for position auction environments. This auction is a
generalization of the multi-unit clinching auction of Dobzinski et al. (2008)
and a special case of the polyhedral clinching auction of Goel et al. (2012).
For welfare maximization, we show that this clinching auction is a good
approximation to the envy-free optimal welfare for position auction
environments. For profit maximization, we generalize the random sampling profit
extraction auction from Fiat et al. (2002) for digital goods to give a
10.0-approximation to the envy-free optimal revenue in symmetric,
downward-closed environments. The profit maximization question is of interest
even without budgets and our mechanism is a 7.5-approximation which improving
on the 30.4 bound of Ha and Hartline (2012).
