Shen, Weiran, Lahaie, Sébastien, Leme, Renato Paes

The problem of market clearing is to set a price for an item such that quantity demanded equals quantity supplied. In this work, we cast the problem of predicting clearing prices into a learning framework and use the resulting models to perform revenue optimization in auctions and markets with contextual information. The economic intuition behind market clearing allows us to obtain fine-grained control over the aggressiveness of the resulting pricing policy, grounded in theory. To evaluate our approach, we fit a model of clearing prices over a massive dataset of bids in display ad auctions from a major ad exchange. The learned prices outperform other modeling techniques in the literature in terms of revenue and efficiency trade-offs. Because of the convex nature of the clearing loss function, the convergence rate of our method is as fast as linear regression.

Markets are important coordination mechanisms for multiagent systems, and market clearing has become a key application area of AI algorithms. We study optimal clearing in the ubiquitous setting where there are multiple indistinguishable units for sale. The sellers and buyers express their bids via supply/demand curves. Discriminatory pricing leads to greater profit for the party who runs the market than nondiscriminatory pricing. We show that this comes at the cost of computation complexity. For piecewise linear curves we present a fast polynomial-time algorithm for nondiscriminatory clearing, and show that discriminatory clearing is NPcomplete (even in a very special case). We then show that in the more restricted setting of linear curves, even discriminatory markets can be cleared fast in polynomial time. Our derivations also uncover the elegant fact that to obtain the optimal discriminatory solution, each buyer's (seller's) price is incremented (decremented) equally from that agent's price in the quantity-unconstrained solution.

Maehara, Takanori (Shizuoka University) | Kawase, Yasushi (Tokyo Institute of Technology) | Sumita, Hanna (National Institute of Informatics) | Tono, Katsuya (University of Tokyo) | Kawarabayashi, Ken-ichi (National Institute of Informatics)

The optimal pricing problem is a fundamental problem that arises in combinatorial auctions. Suppose that there is one seller who has indivisible items and multiple buyers who want to purchase a combination of the items. The seller wants to sell his items for the highest possible prices, and each buyer wants to maximize his utility (i.e., valuation minus payment) as long as his payment does not exceed his budget. The optimal pricing problem seeks a price of each item and an assignment of items to buyers such that every buyer achieves the maximum utility under the prices. The goal of the problem is to maximize the total payment from buyers. In this paper, we consider the case that the valuations are submodular. We show that the problem is computationally hard even if there exists only one buyer. Then we propose approximation algorithms for the unlimited budget case. We also extend the algorithm for the limited budget case when there exists one buyer and multiple buyers collaborate with each other.

Golrezaei, Negin, Javanmard, Adel, Mirrokni, Vahab

Motivated by pricing in ad exchange markets, we consider the problem of robust learning of reserve prices against strategic buyers in repeated contextual second-price auctions. Buyers' valuations for an item depend on the context that describes the item. However, the seller is not aware of the relationship between the context and buyers' valuations, i.e., buyers' preferences. The seller's goal is to design a learning policy to set reserve prices via observing the past sales data, and her objective is to minimize her regret for revenue, where the regret is computed against a clairvoyant policy that knows buyers' heterogeneous preferences. Given the seller's goal, utility-maximizing buyers have the incentive to bid untruthfully in order to manipulate the seller's learning policy. We propose learning policies that are robust to such strategic behavior. These policies use the outcomes of the auctions, rather than the submitted bids, to estimate the preferences while controlling the long-term effect of the outcome of each auction on the future reserve prices. When the market noise distribution is known to the seller, we propose a policy called Contextual Robust Pricing (CORP) that achieves a T-period regret of $O(d\log(Td) \log (T))$, where $d$ is the dimension of {the} contextual information. When the market noise distribution is unknown to the seller, we propose two policies whose regrets are sublinear in $T$.

Saharoy, Debjyoti, Tulabandhula, Theja

We propose a new efficient online algorithm to learn the parameters governing the purchasing behavior of a utility maximizing buyer, who responds to prices, in a repeated interaction setting. The key feature of our algorithm is that it can learn even non-linear buyer utility while working with arbitrary price constraints that the seller may impose. This overcomes a major shortcoming of previous approaches, which use unrealistic prices to learn these parameters making them unsuitable in practice.