In this paper, we derive bounds for profit maximizing prior-free procurement auctions where a buyer wishes to procure multiple units of a homogeneous item from n sellers who are strategic about their per unit valuation. The buyer earns the profit by reselling these units in an external consumer market. The paper looks at three scenarios of increasing complexity. First, we look at unit capacity sellers where per unit valuation is private information of each seller and the revenue curve is concave. For this setting, we define two benchmarks. We show that no randomized prior free auction can be constant competitive against any of these two benchmarks. However, for a lightly constrained benchmark we design a prior-free auction PEPA (Profit Extracting Procurement Auction) which is 4-competitive and we show this bound is tight. Second, we study a setting where the sellers have non-unit capacities that are common knowledge and derive similar results. In particular, we propose a prior free auction PEPAC (Profit Extracting Procurement Auction with Capacity) which is truthful for any concave revenue curve. Third, we obtain results in the inherently harder bi-dimensional case where per unit valuation as well as capacities are private information of the sellers. We show that PEPAC is truthful and constant competitive for the specific case of linear revenue curves. We believe that this paper represents the first set of results on single dimensional and bi-dimensional profit maximizing prior-free multi-unit procurement auctions.
We investigate the class of single-round, sealed-bid auctions for a set of identical items to bidders who each desire one unit. We adopt the worst-case competitive framework defined by [9, 5] that compares the profit of an auction to that of an optimal single-price sale of least two items. In this paper, we first derive an optimal auction for three items, answering an open question from [8]. Second, we show that the form of this auction is independent of the competitive framework used. Third, we propose a schema for converting a given limited-supply auction into an unlimited supply auction. Applying this technique to our optimal auction for three items, we achieve an auction with a competitive ratio of 3.25, which improves upon the previously best-known competitive ratio of 3.39 from [7]. Finally, we generalize a result from [8] and extend our understanding of the nature of the optimal competitive auction by showing that the optimal competitive auction occasionally offers prices that are higher than all bid values.  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 (2008) and a special case of the polyhedral clinching auction of (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 (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).  We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn from a distribution, the Bayesian optimal mechanism is given by Myerson (1981) as a virtual-surplus optimizer. We develop a framework for prior-free mechanism design and analysis. A good mechanism in our framework approximates the optimal mechanism for the distribution if there is a distribution; moreover, when there is no distribution this mechanism still performs well. We define and characterize optimal envy-free outcomes in symmetric single-dimensional environments. Our characterization mirrors Myerson's theory. Furthermore, unlike in mechanism design where there is no point-wise optimal mechanism, there is always a point-wise optimal envy-free outcome. Envy-free outcomes and incentive-compatible mechanisms are similar in structure and performance. We therefore use the optimal envy-free revenue as a benchmark for measuring the performance of a prior-free mechanism. A good mechanism is one that approximates the envy free benchmark on any profile of agent values. We show that good mechanisms exist, and in particular, a natural generalization of the random sampling auction of (2001) is a constant approximation. We study digital-goods auctions for items in unlimited supply introduced by Goldberg, Hartline and Wright. Since no deterministic algorithms are competitive for this class of auctions, one of the central research issues is how to obtain a nice probabilistic distribution over truthful algorithms. In this paper, we introduce a rather systematic approach to this goal: Consider for example the Sampling Cost Share (SCS) auction. It is well known that SCS works well if the the current bid vector produces many winners against F(2), the standard benchmark algorithm for competitive analysis. In fact, its competitive ratio is approaching to 2.0 as k (= the number of F(2) winners) grows. On the other hand, its competitive ratio becomes as bad as 4.0 for k = 2. Our new approach is to develop a sequence of similar cost-share type algorithms, DCSk, which work well for small k. Now we choose a sufficiently large constant N and run DCS1, DCS2, ..., DCSN and SCS with probabilities p1, p2, ..., pN and q, respectively. It should be noted that we can use LP to obtain optimal p1, p2,..., pN and q. By this averaging method, we can improve the competitive ratio of SCS from 4.0 to 3.531 and that of the currently best Aggregated γ3 algorithm due to Hartline and McGrew from 3.243 to 3.119. We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders to bid their utility; competitive auctions yield revenue within a constant factor of the revenue for optimal fixed pricing. We show that for any truthful auction, even a multi-price auction, the expected revenue does not exceed that for optimal fixed pricing. We also give a bound on how far the revenue for optimal fixed pricing can be from the total market utility. We show that several randomized auctions are truthful and competitive under certain assumptions, and that no truthful deterministic auction is competitive. We present simulation results which confirm that our auctions compare favorably to fixed pricing. Some of our results extend to bounded supply markets, for which we also get truthful and competitive auctions. In the context of auctions for digital goods, an interesting Random Sampling Optimal Price auction (RSOP) has been proposed by Goldberg, Hartline and Wright; this leads to a truthful mechanism. Since random sampling is a popular approach for auctions that aims to maximize the seller's revenue, this method has been analyzed further by Feige, Flaxman, Hartline and Kleinberg, who have shown that it is 15-competitive in the worst case -- which is substantially better than the previously proved bounds but still far from the conjectured competitive ratio of 4. In this paper, we prove that RSOP is indeed 4-competitive for a large class of instances in which the number λ of bidders receiving the item at the optimal uniform price, is at least 6. We also show that it is 4.68 competitive for the small class of remaining instances thus leaving a negligible gap between the lower and upper bound. Furthermore, we develop a robust version of RSOP -- one in which the seller's revenue is, with high probability, not much below its mean -- when the above parameter λ grows large. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.