In contextual dynamic pricing, a seller sequentially prices goods based on
contextual information. Buyers will purchase products only if the prices are
below their valuations. The goal of the seller is to design a pricing strategy
that collects as much revenue as possible. We focus on two different valuation
models. The first assumes that valuations linearly depend on the context and
are further distorted by noise. Under minor regularity assumptions, our
algorithm achieves an optimal regret bound of $\tilde{\mathcal{O}}(T^{2/3})$,
improving the existing results. The second model removes the linearity
assumption, requiring only that the expected buyer valuation is
$\beta$-H\"older in the context. For this model, our algorithm obtains a regret
$\tilde{\mathcal{O}}(T^{d+2\beta/d+3\beta})$, where $d$ is the dimension of the
context space.

在此研究中，我们探讨了上下文动态定价的关键问题，提出了两种估值模型，并针对线性性假设和期望买家估值问题分别设计了算法，以实现较低的后悔率。

改进的上下文动态定价算法

Improved Algorithms for Contextual Dynamic Pricing

Complements between goods - where one good takes on added value in the
presence of another - have been a thorn in the side of algorithmic mechanism
designers. On the one hand, complements are common in the standard motivating
applications for combinatorial auctions, like spectrum license auctions. On the
other, welfare maximization in the presence of complements is notoriously
difficult, and this intractability has stymied theoretical progress in the
area. For example, there are no known positive results for combinatorial
auctions in which bidder valuations are multi-parameter and
non-complement-free, other than the relatively weak results known for general
valuations.
To make inroads on the problem of combinatorial auction design in the
presence of complements, we propose a model for valuations with complements
that is parameterized by the "size" of the complements. A valuation in our
model is represented succinctly by a weighted hypergraph, where the size of the
hyper-edges corresponds to degree of complementarity. Our model permits a
variety of computationally efficient queries, and non-trivial
welfare-maximization algorithms and mechanisms.
We design the following polynomial-time approximation algorithms and truthful
mechanisms for welfare maximization with bidders with hypergraph valuations.
1- For bidders whose valuations correspond to subgraphs of a known graph that
is planar (or more generally, excludes a fixed minor), we give a truthful and
(1+epsilon)-approximate mechanism.
2- We give a polynomial-time, r-approximation algorithm for welfare
maximization with hypergraph-r valuations. Our algorithm randomly rounds a
compact linear programming relaxation of the problem.
3- We design a different approximation algorithm and use it to give a
polynomial-time, truthful-in-expectation mechanism that has an approximation
factor of O(log^r m).

研究中提出了一种评估具有互补性的商品的模型，该模型的参数化方法取决于互补性的 “大小”，并为各种计算机查询、效用最大化算法和机制提供了一种选择。