Automated negotiation is a well-known mechanism for autonomous agents to
reach agreements. To realize beneficial agreements quickly, it is key to employ
a good bidding strategy. When a negotiating agent has a good back-up plan,
i.e., a high reservation value, failing to reach an agreement is not
necessarily disadvantageous. Thus, the agent can adopt a risk-seeking strategy,
aiming for outcomes with a higher utilities.
Accordingly, this paper develops an optimal bidding strategy called
MIA-RVelous for bilateral negotiations with private reservation values. The
proposed greedy algorithm finds the optimal bid sequence given the agent's
beliefs about the opponent in $O(n^2D)$ time, with $D$ the maximum number of
rounds and $n$ the number of outcomes. The results obtained here can pave the
way to realizing effective concurrent negotiations, given that concurrent
negotiations can serve as a (probabilistic) backup plan.

该论文提出了一种名为 MIA-RVelous 的双边议价的最优投标策略，通过贪婪算法在 $O (n^2D)$ 的时间内找到了最优的出价顺序，为实现有效的并发谈判铺平了道路。

谈判者的备选方案：具有保留价值的最优让步

A Negotiator's Backup Plan: Optimal Concessions with a Reservation Value

In programmatic advertising, ad slots are usually sold using second-price
(SP) auctions in real-time. The highest bidding advertiser wins but pays only
the second-highest bid (known as the winning price). In SP, for a single item,
the dominant strategy of each bidder is to bid the true value from the bidder's
perspective. However, in a practical setting, with budget constraints, bidding
the true value is a sub-optimal strategy. Hence, to devise an optimal bidding
strategy, it is of utmost importance to learn the winning price distribution
accurately. Moreover, a demand-side platform (DSP), which bids on behalf of
advertisers, observes the winning price if it wins the auction. For losing
auctions, DSPs can only treat its bidding price as the lower bound for the
unknown winning price. In literature, typically censored regression is used to
model such partially observed data. A common assumption in censored regression
is that the winning price is drawn from a fixed variance (homoscedastic)
uni-modal distribution (most often Gaussian). However, in reality, these
assumptions are often violated. We relax these assumptions and propose a
heteroscedastic fully parametric censored regression approach, as well as a
mixture density censored network. Our approach not only generalizes censored
regression but also provides flexibility to model arbitrarily distributed
real-world data. Experimental evaluation on the publicly available dataset for
winning price estimation demonstrates the effectiveness of our method.
Furthermore, we evaluate our algorithm on one of the largest demand-side
platforms and significant improvement has been achieved in comparison with the
baseline solutions.

本文提出了一个基于未完全观测数据的 heteroscedastic fully parametric censored regression 方法和混合密度 censored 网络，用于估计广告拍卖中的赢价分布，并在实验上证明了该方法的有效性。