# pareto_efficient_auctions_with_interest_rates__adf9def6.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Pareto Efﬁcient Auctions with Interest Rates

Gagan Goel, Vahab Mirrokni, Renato Paes Leme Google Research gagangoel@gmail.com, mirrokni@google.com, renatoppl@google.com

We consider auction settings in which agents have limited access to monetary resources but are able to make payments larger than their available resources by taking loans with a certain interest rate. This setting is a strict generalization of budget constrained utility functions (which corresponds to inﬁnite interest rates). Our main result is an incentive compatible and Pareto-efﬁcient auction for a divisible multi-unit setting with 2 players who are able to borrow money with the same interest rate. The auction is an ascending price clock auction that bears some similarities to the clinching auction but at the same time is a considerable departure from this framework: allocated goods can be de-allocated in future and given to other agents and prices for previously allocated goods can be raised.

Introduction One of the common simpliﬁcations in mechanism design is to assume that the monetary resources available to each agent are far more than the magnitude of the economic transaction for which a mechanism is being designed. This assumption is hidden in the quasi-linear utility model, which states that the utility for a certain outcome is its value minus the payment, no matter how large the payments are. While this assumption is ﬁne for a variety of settings, this breaks if the magnitude of a transaction is large. For example, if one wants to buy a house or pay for college tuition, the amount of available funds may even be more important than the actual value. A ﬁrst order approximation to this issue is to consider the budget constrained utility function, which assumes that the utility is quasi-linear if the payment is below the budget and minus inﬁnity otherwise. In the recent past, some progress has been made to develop our understanding of design of efﬁcient mechanisms for budget-constrained utility functions. However, budget constrained utility functions fail to capture an important aspect of real life: to make large purchases one can borrow money. This is done by using ﬁnancial instruments such as credit-cards, loans, mortgages, etc. In this paper we investigate this gap between the realworld scenario and our theoretical understanding of moneyconstrained mechanism design by designing mechanisms for agents whose utility functions are non-linear convex

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

functions of their payments. To be more speciﬁc, we consider utilities of the form u = v(x) β(π) where v(x) is the value the agent derives from the implemented outcome, π is the payment and β is a non-linear convex function of the payment. This can be used to model scenarios with interest rates. For example, suppose that an agent has B monetary units readily available and has access to a bank that can lend him money with interest rate, say, γ 1. This setting can be modeled by deﬁning β(π) := π for π B and β(π) := B + γ(π B) for π > B. To see this, if the agent is charged π > B by the auctioneer, he can use B from his own funds and borrow π B from the bank. Since the agent has to pay (γ 1)(π B) in interest to the bank, his ﬁnal true cost will be β(π) := B + γ(π B). The problem of designing auctions with non-quasi-linear utilities is notoriously hard, which explains why the vast majority of work in mechanism design assumes quasi-linearity. The progress in non quasi-linear utilities has been limited, with a few exceptions, mostly to budget-constraints and riskaversion. In this paper, we seek to make progress in the problem of utilities that take interest rates into account. We consider the simplest possible setting: an auction for one unit of a divisible good between two agents who have access to Bi monetary units and can borrow at the same common interest rate. Our main result is an individually-rational, incentivecompatible and Pareto-efﬁcient auction for the setting described above. We note that the usual notion of efﬁciency in mechanism design - social welfare maximization - is impossible to be achieved in an incentive compatible manner in this setting (even if one allows for approximations). By social welfare here we mean the sum of the utilities of all agents (including the seller) which is P

i vi(xi) + πi βi(πi). Note that unlike quasi-linear settings the payments no longer cancel out and hence our social welfare doesn t coincide with the sum of values P

i vi(xi). The reason is that a special case of our setting is that of budget constrained utility functions (by taking γ ), for which incentive compatible social welfare maximization is known to be impossible (Dobzinski, Lavi, and Nisan 2008). In such cases, Pareto-efﬁciency becomes the natural way to achieve efﬁciency. Note for example that when Bi are very large or the interest rates tend to zero, Pareto-efﬁciency boils down to social-welfare maximization.

Since our setting is a strict generalization of budget constrained utilities, our auction must naturally be the clinching auction in the limit when the parameter γ tends to , since the clinching auction is the unique Pareto-efﬁcient incentivecompatible auction for budget constrained utilities. Our auction, therefore, contains many elements in common with Ausubel s clinching auction (Ausubel 1997), but at the same time is a considerable departure from the traditional clinching framework. The major similarities are that our auction can also be cast as an ascending price clock auction, which keeps at each step provisional allocation and payments and computes demands to determine what amount is safe to be given to each agent without violating demands of the others. Unlike the traditional clinching framework, however, the amount allocated to each agent is not monotone in the price, i.e., units can be allocated at some price and later taken away from an agent and given to the other. Secondly, the auction can, at a given price, increase the price charged for goods allocated at lower prices. Thirdly, the outcome is not determined when the price clock reaches the second-highest valuation. In our auction, the clock ascends all the way to the highest valuation and non-trivial changes in the allocation can happen all the way to the end.

Note on the model and contribution The model studied in this paper is admittedly simple: only 2 players and symmetric interest rates. We believe that the major contribution of this work is not a generally applicable framework but a proof of concept that progress can be made for sophisticated utility functions. From the technical perspective our main contribution is a novel and non-trivial ascending auction with unique features. We believe the construction of our ascending auction is interesting in its own right.

Full Version A full version of this paper is available online in (Goel, Mirrokni, and Paes Leme 2018) where additional intuition behind the our new auction format is proposed. In that version we show how to cast the auction design problem as a differential equations problem and show it has a solution by using the Existence Theorem of First-Order Ordinary Differential Equations. We map back the solution to the differential equation to an auction satisfying all the desirable properties. The auction is correct but has a somewhat cryptic description that lacks economic intuition. Later we show how to re-interpret the solution to the differential equation as an ascending price clock auction, which is the auction described in the conference version.

Related Work In Bayesian settings, Maskin and Riley (Maskin and Riley 1984) were the pioneers in studying the design of mechanism with non-quasi-linear utilities. Their approach also uses differential equations as the main mathematical tool, but since their setting is Bayesian (while ours is worst-case), both the equations and mechanisms obtained are quite different. Note that their mechanisms are depend heavily on the distribution from which types are drawn, where our mechanisms have no such dependency.

Also central to the study of the impact of ﬁnancial constraints in auctions is the work of Che and Gale (Che and Gale 1998; 2006). The authors study the impact of ﬁnancial constraints in the Bayes-Nash equilibria of standard auctions (such as ﬁrst and second price auctions). Besides being Bayesian, another major difference to our work is the approach: while Che and Gale compare different auction formats, we take the mechanism design approach. An interesting connection between our papers is that both their work and ours provide a reduction from generic utilities to the quasi-linear setting. Yet, the reductions are different in nature and serve different purposes in the analysis. Che and Gale reduce to the quasi-linear setting by adding a ﬁctitious risk-neutral bidder, while our reduction works by transferring the risk from the buyers to the auctioneer. Also, while our reduction is used to design dominant strategy incentive compatible mechanisms, Che and Gale use their reduction to establish revenue (Bayes-Nash-type) equivalence theorems. The problem of mechanism design in which players have non-quasi-linear utility functions is well studied for the case in which the available goods are indivisible and each agent wants to acquire at most one good (unit-demand agents). For unit-demand agents, the stable marriage model of Gale and Shapley (Gale and Shapley 1962) together with the various ﬂavors of the deferred-acceptance algorithm allow the design of efﬁcient mechanisms with good incentive properties for a variety of settings with sophisticated utility functions. This is the route taken in the papers of Aggarwal, Muthukrishnan, Pal and Pal (Aggarwal et al. 2009), Alaei, Jain and Malekian (Alaei, Jain, and Malekian 2010), Morimoto and Serizawa (Morimoto and Serizawa 2012). Closer to our work is the paper by Dutting, Henzinger and Weber (D utting, Henzinger, and Weber 2011), extend (Aggarwal et al. 2009) the framework to account for hard and soft budget constraints, but stay within the realm of unit-demand bidders and heavily rely on stable matching constructions. Our paper differs from this line of work in the sense that we look at the simplest setting in which the stable matching machinery is not available: divisible multi-unit auctions. Another major difference is that our goal is to design Pareto-efﬁcient auctions while the previously mentioned papers focus on implementing envy-free outcomes. In the last sense, our paper is closer to the line of work initiated by Dobzinski, Lavi and Nisan (Dobzinski, Lavi, and Nisan 2008) and inspired by Ausubel s framework (Ausubel 1997). In (Dobzinski, Lavi, and Nisan 2008) the authors design an incentive compatible, individually rational and Pareto-efﬁcient auction for budget constrained utility functions. Their auction has been extended in multiple directions: (Bhattacharya et al. 2010) show how to elicit budgets truthfully, (Fiat et al. 2011; Colini-Baldeschi et al. 2012) generalize the clinching to matching markets and (Goel, Mirrokni, and Paes Leme 2012) to general polymatroidal environments and (Goel, Mirrokni, and Paes Leme 2013) shows that the clinching auction allows for an online implementation. Closely related to this work is (Goel, Mirrokni, and Leme 2014) which designs Pareto-efﬁcient auctions where agents have constrained quasi-linear utilities, which mean that ui = vi(xi) πi when (xi, πi) belong to

Figure 1: Interest rates represented by a β-function and its corresponding τ-taxation for B = 1 and γ = 2.

a certain admissible set Ai and otherwise. This allows the authors to generalize the Polyhedral Clinching Auction to settings with average budgets and in general to settings in which the available budget is a function of the allocation. However, the model in (Goel, Mirrokni, and Leme 2014) is not expressible enough to capture interest rates and other types of non-linearities.

Multi-Unit Auctions with Interest Rates We say that an agent has βi-utility if his utility for an outcome in which he is assigned a bundle xi and is charged payment πi is

uβ i (xi, πi) = vi(xi) βi(πi)

where βi : R+ R+ is a convex, strictly monotone function such that βi(πi) πi for all πi 0. Intuitively, this measures his cost for acquiring πi dollars. For quasi-linear players, βi is simply the identity βi(πi) = πi. For traditional hard budget constraints βi(πi) = πi for πi Bi and βi(πi) = otherwise. We will denote its left and right derivatives at πi as: β i(πi ) and β i(πi+). We will be particularly interested in the case player i has Bi monetary units available to him and can borrow additional resources at an interest rate r = γi 1. This is represented by:

βi(πi) = πi, πi Bi Bi + γi(πi Bi), πi Bi

which is depicted in Figure 1. We consider this problem in the context of multi-unit auctions with divisible goods: the allocation of each player is a real number xi [0, 1] and vi(xi) = vi xi. The set of feasible allocations is given by F = {x Rn +; P

i xi 1}. We assume that the β-functions are public information and that values are private. So, ﬁxed βi for each player, a mechanism for multi-unit auctions is a pair of mappings x : Rn + Rn + and π : Rn + Rn +. Incentive compatibility and individual rationally have their usual meaning: each player maximizes his utility by reporting his true value and upon reporting his true value, he has non-negative utility. Since this is not a quasi-linear setting, Myerson s characterization (Myerson 1981) doesn t directly apply. We say that an allocation (x, π) is Pareto-efﬁcient if there is no alternative allocation (x , π ) where each agents utility

is at least as good as in the original allocation, the revenue of the auctioneer is at least as good and at least one of them strictly improves. Formally: there is no alternative allocation, where:

vi x i βi(π i) vi x i βi(π i), i X

i uβ i (x i, π i)+π i > X

i uβ i (xi, πi)+πi

Before designing an auction for this setting, it is instructive to see why simple designs fail to achieve the desirable properties. A natural auction for this setting is the one which holds sequential second price auctions for inﬁnitesimal parts of the good: for each inﬁnitesimal part of the good, allocate to the buyer with largest marginal valuation for that piece, where the marginal valuation for buyer i is vi if he hasn t reached his budget and vi/γi otherwise. This design, while simple, doesn t yield an incentive compatible auction. Consider the example with 1 unit of a divisible good and 2 players with values: v1 = 1 + ϵ, v2 = 1, γ1 = γ2 = 1/ϵ and B1 = B2 = 1/3. In the simple design, for the ﬁrst 1/3 of the good, both agents bid 1, so agent 1 acquires the ﬁrst 1/3 and pays his entire budget and from this point on, he bids v1/γ1 = O(ϵ), so agent 2 acquires the remaining 2/3 of the good. Now, if agent 1 were to shade his bid to 1 ϵ, the situation would be reversed and agent 2 would be allocated the ﬁrst 1/3 + O(ϵ) of the good and agent 1 would be alllocated 2/3. Notice that the mechanism can t even be made truthful by changing the payment rule, since the allocation is not monotone. Indeed, there is a deeper reason why it is not possible to get a simple Pareto-efﬁcient auction in this setting. Once γ , any auction that is Pareto-efﬁcient must recover the Clinching Auction in (Dobzinski, Lavi, and Nisan 2008), since it is the unique incentive compatible auction with hard budget constraints. We refer to (Dobzinski and Leme 2014) for an in-depth discussion of why simple designs typically fail to achieve Pareto-efﬁciency in an incentive-compatible manner.

Equivalence between βi-utilities and quasi-linear settings with taxation

First we show that designing a Pareto-efﬁcient auction for agents with βi-utilities is equivalent to designing Paretoefﬁcient auctions for quasi-linear settings in which the auctioneer is subject to taxation over his revenue. The central idea behind the equivalence is to consider effective payments ˆπi = βi(πi) and design an auction in terms of effective payments charged to the buyer. The issue with that is that ˆπi effective payment results in revenue πi = β 1 i (ˆπi) paid to the auctioneer. Below, we formally deﬁne a setting with taxation:

Quasi-linear settings with taxation Consider the problem where there are n agents with quasi-linear utilities ui(xi, πi) = vi xi πi and for each agent there is a taxation function τi : R+ R+ that is strictly monotone, concave and has τi(πi) πi for all πi 0.

An auctioneer is taxed on the income received from each buyer according to the τi-taxation functions. His revenue is therefore P

i τi(πi). An allocation for this setting is Paretoefﬁcient if there is no alternative allocation (x , π ) such that:

vi x i π i vi x i π i, i, X

i τi(π i) X

i ui(x i, π i) + τi(π i) > X

i ui(xi, πi) + τi(πi)

Now, given a mechanism (x, π) for the setting with βutilities, consider the mechanism (x, ˆπ) for the setting with quasi-linear utilities and τ-taxes with τ = β 1 in which ˆπi(v) = βi(πi(v)). It follows directly from the deﬁnitions that (x, π) is incentive-compatible, individually-rational and Pareto optimal for the β-utilities setting iff (x, ˆπ) is such for the τ-taxes setting.

Lemma 0.1 (equivalence). Given βi strictly monotone convex functions and τi = β 1 i strictly monotone concave functions, there is an incentive-compatible, individually-rational and Pareto-optimal mechanism for agents with β-utilities iff there is a mechanism with the same properties for quasilinear agents where the auctioneer pays τ-taxes on his revenue.

The main advantage of Lemma 0.1 is that it allows us to use Myerson s characterization of incentive compatibility, since agents are quasi-linear. We recall Myerson s characterization:

Lemma 0.2 ((Myerson 1981)). A single-parameter mechanism for quasi-linear agents deﬁned by x : Rn + [0, 1]n and π : Rn + Rn + is individually-rational and incentive compatible iff:

xi(vi, v i) is monotone non-decreasing in vi for any ﬁxed v i; payments are such that πi(vi, v i) = vi xi(vi, v i) R vi 0 xi(u, v i)du.

Characterizing Pareto-efﬁcient outcomes

Our ﬁrst step is to provide a characterization of Paretoefﬁcient outcomes for settings with taxation. The following Lemma is a version of Proposition 2.4 in (Dobzinski, Lavi, and Nisan 2008) for the utility model studied in this paper. Versions of this lemma for different settings have been provided in (Bhattacharya et al. 2010; Goel, Mirrokni, and Paes Leme 2012; Goel, Mirrokni, and Leme 2014). We recall the reader that τ i(πi ) and τ i(πi+) denote the left and right derivatives of the taxation function τi.

Lemma 0.3 (Pareto-optimality characterization). Consider n agents with quasi-linear utilities and an auctioneer that obtains revenue P

i τi(πi) from the outcome (x, π) and a divisible multi-unit auctions setting, i.e. P

i xi(v) 1. Such outcome is Pareto-optimal iff (i) all goods are sold, i.e., P

i xi(v) = 1 and (ii) no trade is possible, i.e., for all agents i = j such that xi > 0, it holds that vi τ i(πi ) vj τ j(πj+).

Proof. For the ( ) direction, if the allocation doesn t sum to one, one can allocate the left-over goods to some player for free, improving his utility. Also, if for some pair xi > 0 and vi τ i(πi ) < vj τ j(πj+), then there is some ϵ for which τi(π) τi(πi viϵ) < τj(πj + vjϵ) τj(πj). So, consider the outcome (x , π ) where for k = i, j, x k = xk and π k = πk, x i = xi ϵ, π i = πi viϵ, x j = xj + ϵ and π j = πj + vjϵ. All utilities are still the same, and the auctioneer revenue improved. For the ( ) direction, consider an allocation (x, π) with the two characterization properties and let (x , π ) be a Pareto-improvement. If some players utility strictly improved we can always increase his payment so that the utilities are the same as before for all agents but the revenue of the auctioneer improved. Assuming that, we now compare the revenue in both allocations.

i τi(πi) τi(π i) X

i;πi>π i τ i(πi ) (πi π i)+

i;πi<π i τ i(πi+) (πi π i) =

i;πi>π i τ i(πi ) vi (xi x i)+

i;πi<π i τ i(πi+) vi (xi x i) 0

i;πi>π i xi x i = P

i;π i>πi x i xi and the coefﬁcients τ i(πi ) vi are larger then the coefﬁcients τ i(πi+) vi by the characterization condition. So, this implies that P i τi(πi) τi(π i) = 0 contradicting the fact that (x , π ) is a Pareto improvement.

Ascending Price Clock Auction We now present our main result, which is an ascending clock auction for the quasi-linear setting with taxation, which we call the Taxed Ascending Auction. We consider a setting with 2 agents each of them deﬁned by two public parameters Bi and γ and a private value vi. We will assume in the description that both values vi are multiples of a small quantity ϵ. Our goal is to design an ascending price clock auction to sell one unit of a divisible good. The price clock will be represented by a pair (p1, p2) which will represent the prices for each of the agents. The clock will start at (0, 0) and increment each price by ϵ in a round-robin fashion, i.e., (0, 0), (ϵ, 0), (ϵ, ϵ), (2ϵ, ϵ), (2ϵ, 2ϵ), (3ϵ, 2ϵ), .... We will keep for each player i a vector dxi[p] indexed by price p which indicates how many units he acquired at price p and pri[p] as the price per unit he was charged for those units. In each stage, we will refer to xi = P

p dxi[p] and πi = P

p pri[p] dxi[p]. We will also keep a variable x , which we will call the -pool and use to store the goods that were allocated to an agent but had to be de-allocated because the agent could no longer afford them. The -pool is a pool of goods that will be reserved to the higher valued agent (the -player). The identity of the -player will be determined once one of the agents drops out of the auction.

Given i {1, 2} we will denote the other player by i, so if i = 1, xi and πi will denote x1 and π1 and x i, π i will denote x2 and π2. Finally, we will also use the notation [z]+ to denote max(z, 0). Taxed Ascending Auction

Initialize dxi[p] = 0 and pri[p] = p for all prices p, p1 = p2 = 0 and i = 1.

Main Loop: Repeat while p1 v1 or p2 v2. 1. Choose agent in round-robin schedule and increase price: i = 3 i, pi = pi + ϵ. 2. Update price for previously allocated goods: if p i < v i, then for all prices p γ 1pi, update pri[p ] = γ 1pi. 3. Recollections: if γ 1p > vi, collect back all the goods allocated to player i and add them to the pool. Formally: x = x + P

q xi[q] and xi[q] = 0 for all q. if i total payment is larger then Bi, collect back the most expensive goods and add them to the -pool. Formally: if πi > Bi, ﬁnd p such that P

q<p pri[q] dxi[q] Bi and P

q p pri[q] dxi[q] > Bi. Let Ki = 1 pri[p ][Bi P

q<p pri[q] dxi[q]] be the amount of goods at price p the player can keep. And update: x = x + (xi[p ] Ki) + P q>p dxi[q], dxi[q] = 0 for q > p and dxi[p ] = Ki. 4. Clinching: The demand of i decreases to di = 1 pi [Bi πi] if pi vi and di = 0 otherwise; and compute the clinched amount for player i as δ i = [1 x1 x2 x di]+ and allocate: dx i[p i] = dx i[p i] + δ i. 5. Pool Re-assignment: if p i > v i, then dxi[pi] = dxi[pi] + x , x = 0.

First we show that the Taxed Ascending Auction has the desired properties: Theorem 0.4. The Taxed Ascending Auction is an incentivecompatible, individually rational and Pareto efﬁcient auction for 2 players with taxation functions τi(πi) = πi for πi Bi and τi(πi) = Bi + γ 1(πi Bi) for πi Bi. The ﬁrst part of the theorem is easy, as it is usually the case in the analysis of ascending auctions. The auction is individually rational because no item is ever given to an agent at a price-per-unit larger then his value. Also, if we ever raise the price of previously allocated goods to a price higher then the agent s valuation, we collect back those goods in step (3). For incentive compatibility, notice that the only point in which the valuation affects the auction is when the agent s demand drops to zero in step (4). Besides step (4), the agent valuation is used nowhere else. By increasing his value, the agent can only potentially be allocated goods at a higher price per unit then his valuation. Declaring a smaller value can only prevent him from acquiring goods he wants. Also notice that the price increase for previously allocated goods in step (2) and the recollection in step (3) are unaffected by

the value of the agent. So no matter which value agent i declares, the price per unit paid in the end will be at least γ 1v i. Also note that the re-assignment to the -pool are also not affected by the value declaration of the agents. Finally, we need to show that the outcome is Paretoefﬁcient. First we argue that all the good is allocated in the end, i.e., by the end of the auctions x1 + x2 = 1. The proof of that fact is similar to the one for the traditional clinching auction. First we consider the following invariant:

Lemma 0.5. In the beginning of each iteration of the main loop, the following invariant holds: min(1, 1

pi [Bi πi]) = 1 x1 x2 x .

Proof. This is clearly true for p = (0, 0). Now, we show that this is preserved as an invariant. Notice that in steps (1) and (2), the value of pi and πi. Step (3) prevents πi from being above Bi, so the quantity min(1, 1

pi [Bi πi]) is nonincreasing. If it stays the same, then no clinching happens and since nothing changes for player i, then the invariant continues to hold. If on the other hand, this value decreases, the notice that since 1 x1 x2 x was equal to min(1, 1

pi [Bi πi]) in the beginning of that iteration of the main loop, then the clinched amount δ i is equal to the decrease in min(1, 1

pi [Bi πi]), therefore preserving the invariant.

Lemma 0.6. All goods are allocated in the end of the auction.

Proof. The previous lemma states that while there are unallocated goods, both players have demand that equals the total amount of unallocated goods. At the ﬁrst time that one player reduces his demand to zero, the other player still demands the entire amount of unallocated goods, so he will clinch the remainder. We note that the collection and reassignment of goods, via the -pool doesn t inﬂuence this argument, since recollected goods are eventually re-assigned to the highest valued player.

The following lemma completes the proof of Paretoefﬁciency of the Taxed Ascending Auction.

Lemma 0.7. The outcome of the Taxed Ascending Auction satisﬁes condition (ii) in Lemma 0.3.

Proof. We consider four cases:

1. v2 < γ 1v1. In this case, the price of all items allocated to player 2 are raised to at least γ 1v1 in step (2) of the auction, which causes them to be collected in step (1). Therefore the allocation is (1, 0). For this allocation, condition (ii) in Lemma 0.3 states that v2 τ (π1 )v1 which holds since v2 γ 1v1 τ (π1 )v1. 2. v1 < γ 1v2. Analogous to the previous item. 3. γ 1v1 < v2 v1. Consider the ﬁrst price in which the demand of one of the agents drops to zero. This can happen for one of two reasons:

(a) price p2 reaches v2, his demand drops to zero and player 1 clinches less then his entire demand. The only way this can happen is (by Lemma 0.5) if the demand of 1 was larger then 1, which implies that player 2 didn t have an opportunity to clinch any amount. So the payments are π1 < B1 and π2 = 0, implying a Paretooptimal outcome. (b) price p2 reaches v2, his demand drops to zero and player 1 clinches his entire demand, spending B1. In this case, the payments at that moment of the auction are B1 for player 1 and some π2 < B2 for player 2. The price clock will continue to ascend all the way up to v1 and no more clinching will happen, but the price of previously allocated units to player 2 keep rising. Either: the price increase won t cause player 2 to pay B2 or more. In such case the ﬁnal payments are B1 for player 1 and 0 < π2 < B2. In such case we need to check two inequalities for property (ii) of Lemma 0.3: v1τ (π1 ) = v1 v2τ (π2+) = v2 and v2τ (π2 ) = v2 v1τ (pi1+) = γ 1v1, both of which hold by the assumption in this case. the price increase causes player 2 to pay more then B2 and some units are collected in step (2), assigned to the -pool and then re-assigned later for some price p v2 to player 1, which is the highest value player. By the recollection procedure, the payment of player 2 is exactly B2 while player 1 has some payment strictly greater B1 (strictly greater because he is assigned units from the -pool. Now, checking conditions (ii), we get: v1τ (π1 ) = γ 1v1 v2τ (π2+) = γ 1v2 and v2τ (π2 ) = v2 v1τ (pi1+) = γ 1v1, both of which hold by the assumptions in this case. (c) before reaching v2, the demand of one player reaches zero because his payment reaches Bi by the increase in price of previously allocated goods that happens in step (2) of the auction. If this happens, immediately the payment of the other agent also reaches Bi in the clinching step. As the clock ascends, both agents potentially have the price of their allocated goods increased and have items collected to the -pool, but the total payment remains Bi. Only the higher valued player (in this case player 1) receives the goods from -pool, so we end up with an allocation in which player 2 pays B2 and player 1 pays either B1 or some amount larger or equal to B1. Condition (ii) in Lemma 0.3 holds by the same argument as in the second part of item (b). 4. γ 1v2 < v1 < v2 is analogous.

Open Problems This paper leave open the question of whether it is possible to design incentive-compatible and Pareto-efﬁcient auctions for the following cases: (i) 3 or more agents with symmetric interest rates; (ii) 2 players with agent-speciﬁc interest rates; (iii) 2 players with generic nonlinear βi-functions. The main issue with (i) and (ii) is that the characterization of Pareto-efﬁciency is less crisp in those

cases. Most natural generalizations of the Taxed Ascending Auction break either incentive-compatibility or Paretoefﬁciency when we move to 3 players or asymmetric interest rates.

References Aggarwal, G.; Muthukrishnan, S.; P al, D.; and P al, M. 2009. General auction mechanism for search advertising. In WWW, 241 250. Alaei, S.; Jain, K.; and Malekian, A. 2010. Walrasian equilibrium for unit demand buyers with non-quasi-linear utilities. Co RR abs/1006.4696. Ausubel, L. M. 1997. An efﬁcient ascending-bid auction for multiple objects. American Economic Review 94. Bhattacharya, S.; Conitzer, V.; Munagala, K.; and Xia, L. 2010. Incentive compatible budget elicitation in multi-unit auctions. In SODA, 554 572. Che, Y.-K., and Gale, I. 1998. Standard auctions with ﬁnancially constrained bidders. Review of Economic Studies 65(1):1 21. Che, Y.-K., and Gale, I. 2006. Revenue comparisons for auctions when bidders have arbitrary types. Colini-Baldeschi, R.; Henzinger, M.; Leonardi, S.; and Starnberger, M. 2012. On multiple keyword sponsored search auctions with budgets. In ICALP (2), 1 12. Dobzinski, S., and Leme, R. P. 2014. Efﬁciency guarantees in auctions with budgets. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, 392 404. Dobzinski, S.; Lavi, R.; and Nisan, N. 2008. Multi-unit auctions with budget limits. In FOCS, 260 269. D utting, P.; Henzinger, M.; and Weber, I. 2011. An expressive mechanism for auctions on the web. In Proceedings of the 20th international conference on World wide web, WWW 11, 127 136. New York, NY, USA: ACM. Fiat, A.; Leonardi, S.; Saia, J.; and Sankowski, P. 2011. Single valued combinatorial auctions with budgets. In ACM Conference on Electronic Commerce, 223 232. Gale, D., and Shapley, L. S. 1962. College admissions and the stability of marriage. American mathematical monthly 9 15. Goel, G.; Mirrokni, V. S.; and Leme, R. P. 2014. Clinching auctions beyond hard budget constraints. In ACM Conference on Economics and Computation, EC 14, Stanford , CA, USA, June 8-12, 2014, 167 184. Goel, G.; Mirrokni, V. S.; and Paes Leme, R. 2012. Polyhedral clinching auctions and the adwords polytope. In STOC, 107 122. Goel, G.; Mirrokni, V. S.; and Paes Leme, R. 2013. Clinching auctions with online supply. In SODA. Goel, G.; Mirrokni, V. S.; and Paes Leme, R. 2018. Pareto efﬁcient auctions with interest rates (full version). In Online Appendix in http://renatoppl.com/papers/ clinching-beyond-main.pdf.

Maskin, E. S., and Riley, J. G. 1984. Optimal auctions with risk averse buyers. Econometrica 52(6):1473 1518. Morimoto, S., and Serizawa, S. 2012. Strategy-proofness and efﬁciency with nonquasi-linear preferences: A characterization of minimum price walrasian rule. ISER Discussion Paper 0852, Institute of Social and Economic Research, Osaka University. Myerson, R. 1981. Optimal auction design. Mathematics of Operations Research 6(1):58 73.