NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:535
Title:Optimal Pricing in Repeated Posted-Price Auctions with Different Patience of the Seller and the Buyer

Reviewer 1

This work studies optimal pricing is repeated posted-price auctions. They consider the scenario in which a single seller interacts with a single buyer whose patience is different than that of the seller. The main contribution of this work is designing optimal pricing algorithms to maximize the revenue of the seller. They consider two different cases which are selling to a buyer who is more patient than the seller and selling to a buyer who is less patient. They show that the former case is simpler and they provide an algorithm called the "big deal" algorithm for that. To get this result, they first show how in the case of equal discounts (patience) Myerson's well-known result can be used to obtain the optimal revenue. Then, they use it to solve the case of a less patient seller. Further, for the case of a less patient buyer, they give a more complicated algorithm and to obtain that, they use a reduction to the optimization of a multivariant function. Strengths: --- 1- An interesting problem that is not studied before 2- A well-written paper 3- Paper has a good technical contribution and authors verify some of their claims using practical evidence. Weaknesses: --- My main problem is with the assumption that the seller has an accurate estimate of the buyer's discount and with the fact that it is not explicitly mentioned in the problem statement. This specifically concerns me because the "Big deal" pricing algorithm seems to highly rely on this assumption. As I understand if the seller underestimates buyer's patience and uses this algorithm, it might lead to a zero revenue for him.

Reviewer 2

1. In the preliminaries, it is not clear whether the discount sequences of the buyer and the seller are public information or not. In the later section, in my understanding, the discount sequences are known for both buyer and seller. But I think this assumption is slightly unrealistic, since this means the seller knows the extent of impatience of the buyer. A more reasonable assumption might be that the seller knows the distribution of the discount parameter of the buyer. 2. In line 100, “A*’s ESR is maximal”, is it “maximum”? 3. In section 3, when the seller is less patient, the result in the paper indicates the repeated game is meaningless since the best algorithm is a “once-for-all” deal. It does not seem to match the real case. The reason might be that the seller does not know the exact discount of buyer, which is related to the first comments. 4. In section 4, the results require that the discount is regular. Should the discount also decrease geometrically? 5. In section 4, about the CA algorithm, I understand that any algorithm can be transformed to be a CA algorithm, but I am not quite sure about the intuition behind the CA algorithm. For a CA algorithm, does it mean (in some sense) that there is no “stupid” buyer strategy where any strategy is optimal for at least one valuation? 6. In line 231, “which is piecewise linear”, according to the following argument, is it “piecewise constant”? 7. In section 5, the approximation algorithm looks weak and straightforward. The paper shows that it is a good approximation to consider only finite steps. But the algorithm for t steps needs poly(2^t) times which seems unrealistic in the practice. Is it possible to show some hardness result for the case of t-step pricing algorithm? Such result might be a good justification of the approximation algorithm After the feedback, 1. In the feedback, the authors answer the question about the discount knowledge and provide further explanations about the unknown buyer discount. I think the explanation is good and should be add into the full version of paper. 2. But the feedback about the time complexity is unsatisfying. Since the space complexity is exponential on \tau, the time complexity is also exponential which means only very small constant \tau is tolerable. Then the authors should justify why it is reasonable in the practice.

Reviewer 3

The paper studies the repeated posted-price setting against a single strategic buyer with fixed valuation and a known prior over that valuation, and asymmetric discounting. They give the optimal algorithm when the seller is less patient than the buyer, which is simple and straight-forward but insightful. When the seller is more patient than the buyer, they provide an interesting characterization seller algorithms as a piece-wise linear surplus function over buyer valuations. The final results here are less clean. The authors avoid giving an explicit characterization of the optimal algorithm, but instead suggest an (exponential) procedure for computing the optimal seller algorithm. “The case of our setting where the time discounts of the seller and 42 the buyer are different was never studied before.” This is studied in the referenced works [7], and [8], specifically where the buyer is less patient than the seller. Perhaps the authors mean that this has previously only been studied in the worst-case setting. Line 75: It is a little strange to call a sequence a strategy. A strategy is typically a function of the information received on previous rounds, although maybe this distinction is unimportant since A is deterministic? Line 77: “Given an algorithm A … is uniquely determined.” If this is the case, seller algorithm is constrained to be deterministic, which could be restrictive. This should be stated earlier. Line 99: “Expected” does not make sense as there is no expectation in (1). Line 125: “How greater the maximal ESR” => typo Line 158: typo: Myeson Line 171: The algorithm requires the seller to know gamma_B. Line 211: “tangent” here is a little unclear. Do you mean equal at the valuation v? Lines 213-227: There seems to be something wrong with this construction. Consider, for example, the big deal algorithm from the beginning of the paper. This algorithm is not completely active. Let a be a buyer strategy that accepts the initial big deal, but then rejects some of the free items that come afterwards. There is no valuation that makes this surplus-optimal. However, A(n) cannot be decreased any further (it is already zero). Am I missing something?

Reviewer 4

The authors consider the problem of coming up with a pricing strategy that is god against a strategic buyer. Here, a strategic buyer with a fixed valuation v is one who knows the pricing strategy used by a seller and acts in the auction to optimize her surplus. The authors consider an scenario where both the buyer and the seller have a discount factor in their surplus and revenue. Similar scenarios have been studied before by Kamin et al., Mohri and Munoz and Dustra et al. However, these works have focused on the regret achievable when facing a single buyer. In contrast, this paper wants to find an optimal pricing strategy that works well on average assuming the value of a buyer is chosen from a fixed (known) distribution. The paper describes the set of optimal strategies when the discount factor of the buyer is less than that of the seller and vice-versa. The first case offers surprising results showing that the buyer can recover the same revenue as if he had a discount factor equal to that of the buyer. The case when the seller's discount greater than the buyer discount is much more complicated as it requires optimizing over a discrete set with an exponential number of elements. I would say the main contribution of the authors is to transform this problem into a smooth problem where gradients are available. This was by no means a trivial task and required a very deep understanding of the problem. While the smooth problem size remains exponential, the authors show that a low dimensional approximation to it does not deteriorate the solution too much. The authors conclude showing different performance metrics for their algorithm. Overall I am very impressed with the work done by the authors to obtain a smooth version of this problem and make a connection between strategic revenue optimization and static revenue optimization which was missing in the literature. One question that the authors do not address however is how does their approximation compare to using the algorithm of Drutsa et. al. While the algorithm of Drutsa et al. is designed for facing a fixed buyer, one can plug the guarantees inside the expectation term and see if they are better than the ones proposed by the authors. This would have the advantage of being a much simpler algorithm. Even if this were the case, however, I believe making the connection between strategic revenue optimization and static revenue optimization is a good enough reason to accept this paper. **** I must admit that I did not read the proofs of the paper although intuitively everything seemed correct ******