# Robust Price Discrimination

Itai Arieli, Yakov Babichenko, Omer Madmon, Moshe Tennenholtz Faculty of Data
and Decision Sciences, Technion - Israel Institute of Technology,
<EMAIL_ADDRESS>of Data and Decision Sciences, Technion - Israel
Institute of Technology<EMAIL_ADDRESS>of Data and Decision
Sciences, Technion - Israel Institute of Technology,
<EMAIL_ADDRESS>of Data and Decision Sciences,
Technion - Israel Institute of Technology<EMAIL_ADDRESS>
###### Abstract

We consider a model of third-degree price discrimination, in which the seller
has a valuation for the product which is unknown to the market designer, who
aims to maximize the buyers’ surplus by revealing information regarding the
buyer’s valuation to the seller. Our main result shows that the regret is
bounded by $U^{*}(0)/e$, where $U^{*}(0)$ is the optimal buyer surplus in the
case where the seller has zero valuation for the product. This bound is
attained by randomly drawing a seller valuation and applying the segmentation
of Bergemann et al. (2015) with respect to the drawn valuation. We show that
the $U^{*}(0)/e$ bound is tight in the case of binary buyer valuation.

##  1 Introduction

The celebrated paper of Bergemann et al. (2015) considers a setting in which a
product is sold via the posted price mechanism. The interaction involves three
agents. A _buyer_ whose value for the product is drawn according to a commonly
known distribution $b\sim\mu\in\Delta(\mathbb{R}_{+})$. A _seller_ whose value
for the product is $\operatorname*{s}$ (e.g., the seller has an outside option
of selling the product for a price of $\operatorname*{s}$). The third entity
is a _market designer_ (a _designer_ for short) who knows the buyer’s value
for the product $b$ and is allowed to credibly reveal information about $b$ to
the seller.

Bergemann et al. (2015) characterize the possible (buyer, seller) utility
profiles that may arise in the above interaction under some revelation policy
of the designer (i.e., under some _market segmentation_). Arguably, the most
interesting case arises when the designer’s objectives are aligned with those
of the buyer; namely when the designer tries to maximize the (ex-ante) buyer’s
surplus. Surprisingly, Bergemann et al. (2015) shows that a careful choice of
market segmentation might yield the entire surplus to the buyer subject to the
obvious constraint that the seller must get at least her no-information
surplus (because the seller can ignore the designer’s information).

This very elegant result relies, however, on the assumption that the designer
knows the seller’s value for the product $\operatorname*{s}$ (in such a case,
$\operatorname*{s}$ can be normalized to $\operatorname*{s}=0$). In many
natural scenarios, the knowledge of $\operatorname*{s}$ (e.g., the outside
options of the seller) by the designer might be a demanding requirement. In
this paper, our goal is to explore the same interaction in the case where
$\operatorname*{s}$ is unknown to the designer. While Bergemann et al. (2015)
is an information design problem in a setting of trade with incomplete
information on one side (i.e., only buyer valuation is private information)
our setting can be viewed as a first step towards understanding information
design in the classical bilateral trade setting (see Myerson and
Satterthwaite, 1983) in which both buyer and seller valuations are private
information.

One natural model that might be considered is the Bayesian one:
$\operatorname*{s}$ is drawn according to a commonly known distribution
$\operatorname*{s}\sim F\in\Delta(\mathbb{R}_{+})$. We observe that the
Bayesian model boils down to a standard Bayesian persuasion problem. Kamenica
and Gentzkow (2011) have shown that the solution for this problem can be
expressed as the concavification of the designer’s (the sender’s) indirect
utility. However, the indirect utility of the designer as a function of the
seller’s (the receiver’s) posterior is high dimensional (of dimension
$|\operatorname*{\operatorname{supp}}(\mu)|$) and its formula is not very
clean. Since concavification in high dimensions is quite a complex object both
computationally and conceptually, we tend to believe that such a Bayesian
approach is not very insightful when
$|\operatorname*{\operatorname{supp}}(\mu)|$ is large.

Another natural approach is the robust perspective. The designer aims to come
up with a market segmentation that performs well _for all_
$\operatorname*{s}$. There are two leading branches of the robust paradigm.
The first one is the max-min paradigm; the market segmentation should yield a
high utility for the buyer for all $\operatorname*{s}$. This approach is not
very insightful either. An adversarial choice of $\operatorname*{s}$ that is
above all elements in $\operatorname*{\operatorname{supp}}(\mu)$ leads to no
trade, and hence, to a 0 surplus for the buyer. The second robustness paradigm
is regret; the market segmentation should yield a utility as close as possible
to the hypothetical scenario in which $\operatorname*{s}$ was known to the
designer.

Surprisingly, we show that the regret paradigm is very insightful despite the
fact that the Bayesian model is involved. Our main result (Theorem 1) shows
that for every $\mu$ there exists a market segmentation that ensures a low
regret of $U^{*}(0)/e$, where $U^{*}(0)$ is the buyer’s surplus in the case
where $\operatorname*{s}=0$ and is known to the designer; i.e., the difference
between the performance of our ignorant designer and that of the hypothetical
designer who knows $\operatorname*{s}$ will never exceed $U^{*}(0)/e$. This
market segmentation is the regret minimizing one whenever
$|\operatorname*{\operatorname{supp}}(\mu)|=2$ (see Theorem 2). The market
segmentation that achieves this low regret is quite intuitive: The designer
does not know $\operatorname*{s}$. A simple idea is to ”guess
$\operatorname*{s}$” according to a carefully chosen distribution $s_{D}\sim
g\in\Delta(\mathbb{R}_{+})$, and thereafter to create a segmentation that is
optimal for the case $\operatorname*{s}=s_{D}$ exactly as described in
Bergemann et al. (2015). This two-step procedure creates yet another market
segmentation and we call the class of these segmentations _BBM segmentations_.

Besides the theoretical results, we also present empirical evidence for the
effectiveness of our BBM segmentation. Empirical studies demonstrate that
realistic valuations fit best Lognormal distributions or Pareto distributions
(see Coad, 2009). We show that in an experimental setting in which buyer and
seller valuations are drawn independently from a shared distribution (which
can be either Lognormal or Pareto), the actual expected difference between the
optimal surplus and the surplus achieved by our segmentation is even lower
than the theoretical bound we prove in Theorem 1.

#### Techniques

The idea behind the proof of the main results (Theorems 1 and 2) is as
follows. As standard in the robustness literature, the interaction can be
viewed as a zero-sum game between the designer who chooses a segmentation and
an adversary who chooses $\operatorname*{s}$. The analysis of this zero-sum
game is involved due to the fact that the strategy space of the designer is
high-dimensional (i.e., segmentations). Once we restrict the designer to BBM-
segmentations the strategy space of the designer turns to a single-dimensional
one (just the choice of $s_{D}\in\mathbb{R}_{+}$). It turns out that the
utilities in this zero-sum game (as a function of $\operatorname*{s}$ and
$s_{D}$) have relatively clean expressions, but are not clean enough to be
able to be solved explicitly. We bound from above the utilities in the zero-
sum game by even cleaner expressions. The latter formula is so clean that we
are able to perform the entire equilibrium analysis of this game (see Lemma
2). These arguments are sufficient to deduce Theorem 1.

For the proof of Theorem 2 we observe that along the proof of Theorem 1 we
have made two relaxations. First, we restricted the designer to BBM
segmentations. Second, we have bounded from above the utilities of the actual
zero-sum game. It turns out that the second relaxation is not actually a
relaxation in the case of $|\operatorname*{\operatorname{supp}}{\mu}|=2$. It
is the actual zero-sum game. Therefore, a natural attempt would be to focus on
the mixed strategy of the adversary in this zero-sum game. Now we allow the
designer to use all the segmentations (not only the BBM ones) and we show that
even if her strategy space is richer (i.e., not only BBM segmentations) she
still cannot gain more than the value of the zero-sum game. Such an analysis
is tractable because in the case of
$|\operatorname*{\operatorname{supp}}(\mu)|=2$ designer’s best reply problem
boils down to a concavification of a single-dimensional function. This
somewhat surprising observation is sufficient to deduce Theorem 2. The
observation is somewhat surprising because there exist mixed strategies of the
adversary (i.e., distributions $\operatorname*{s}\sim F$) for which all best
replies of the designer do not belong to the BBM segmentations class. The
specific mixed strategy that is optimal for the zero-sum game turns out to
have BBM segmentation best-reply.

#### Paper structure

Section 2 introduces the price discrimination model of Bergemann et al.
(2015), which assumes a known seller valuation. In section 3 we discuss the
Bayesian approach, and demonstrate its complexity even for the binary buyer
type case. We then introduce and analyze the robust approach in Section 4: We
state and prove our main result, which is an upper bound on the overall regret
using our BBM segmentation (Theorem 1). We then show in Subsection 4.1 that
this bound is tight for the binary buyer type case (Theorem 2). Section 5
introduces our experimental results in which we evaluate the performance of
our approach compared to the optimal benchmark for a specific class of
distributions that are considered as reflecting the actual distribution of
valuations in realistic settings. We then conclude in Section 6. Proofs of all
technical lemmas are deferred to the appendix.

###  1.1 Related Work

#### Third-degree price discrimination

A fundamental economic question is how third-degree price discrimination111In
”third-degree” price discrimination, the market designer divides the market
into separate segments, where the seller may charge different prices in each
segment. In contrast, ”first-degree” price discrimination refers to a
situation in which the seller is fully informed of the buyer’s value (hence
charges this value as the price), and in ”second-degree” price discrimination
the seller sells goods that are similar, but may vary in quality, at different
prices. Throughout the paper, we use the term ’price discrimination’ to
describe a model of third-degree price discrimination. affects consumer
surplus, producer surplus, and social welfare (see, e.g., the classic work of
Pigou, 1920). Our work extends the work of Bergemann et al. (2015), in which
the price discrimination model is studied from a buyer surplus maximization
perspective. Bergemann et al. (2015) introduced an algorithm for finding a
buyer surplus maximizing market segmentation, which can be computed
efficiently. Several works have then extended the standard model, and provided
either exact or approximate buyer-optimal segmentation under different
assumptions (Shen et al., 2018, Cai et al., 2020, Mao et al., 2021, Bergemann
et al., 2022, Alijani et al., 2022, Ko and Munagala, 2022).

While maximizing surplus often yields an unfair outcome for the buyers, an
alternative promising line of research focuses on _fair price discrimination_
(Flammini et al., 2021, Cohen et al., 2022). In particular, Banerjee et al.
(2023) prove the existence of a segmentation, different than the one of
Bergemann et al. (2015), that simultaneously approximates a large set of
welfare functions (including utilitarian welfare, Nash welfare and the min-max
welfare). Their approach can be viewed as another notion of robustness other
than regret-minimization, since the segmentation is robust to the actual
welfare function.

Closer to our work, Cummings et al. (2020) analyzed several variations of the
price discrimination model, in which the market designer only has a noisy
signal about the _buyer’s_ valuation. Our work completes the picture by
studying the case in which the uncertainty of the designer is with respect to
the _seller’s_ valuation.

#### Robust Bayesian persuasion

As we discuss in the paper, the model of price discrimination closely relates
to the Bayesian persuasion model introduced by Kamenica and Gentzkow (2011).
Bayesian persuasion refers to a situation in which an informed sender aims to
influence the decision of an uninformed receiver by designing a signaling
scheme. One rigid assumption required in the standard model is that the sender
knows the receiver’s type (i.e., utility function), and uses this information
to construct an optimal signaling policy. Several works took different
approaches to relax this restricting assumption: Arieli et al. (2023) took a
natural _Bayesian_ approach, meaning the receiver is sampled from a commonly
known prior distribution; Dworczak and Pavan (2022) took a _minmax_ approach,
which measures the absolute performance of a signaling scheme that does not
rely on knowing the receiver’s type; Castiglioni et al. (2020) considered an
_online learning_ framework, in which the sender repeatedly faces an
adversarially-chosen receiver whose type is unknown, and receives either a
full-information or partial-information feedback.

Closest to our work, Babichenko et al. (2022) studied a _regret-minimizing_
Bayesian persuasion model, in which the performance of a signaling policy is
determined according to the worst-case difference between the optimal utility
the sender could obtain _has she known_ the receiver’s type, and the actual
utility she obtains without having access to this information. The class of
utilities that are studied in Babichenko et al. (2022) is different from the
one that arises in a price discrimination model. Babichenko et al. (2022)
consider a receiver with binary decisions and state-independent utilities for
the sender. In our case, the number of actions for the seller (receiver) is
$|\operatorname*{\operatorname{supp}}(\mu)|$. Moreover, the sender’s utility
is not state-independent. Even in the binary valuation case (i.e.,
$|\operatorname*{\operatorname{supp}}(\mu)|=2$) the class of the sender’s
indirect utilities in our case might have a structure that is much more
complex than the threshold structure of state-independent utilities; see
Examples 1 and 2. The results of Babichenko et al. (2022) indicate that the
sender can guarantee low regret whenever the receiver’s utility is monotonic
in the state. Our results provide another instance where low regret can be
guaranteed.

##  2 Preliminaries: Known Value of the Seller

Before introducing the case in which the seller’s value is unknown, we briefly
discuss the model of Bergemann et al. (2015) in which the seller’s value
$\operatorname*{s}\in\operatorname*{\mathbb{R}}_{+}$ is known by the market
designer. Let
$B\coloneqq\\{b_{1},...b_{n}\\}\subset\operatorname*{\mathbb{R}}_{+}$ be the
buyers’ valuations. We assume that $0<b_{1}<...<b_{n}$. Let $\mu\in
int(\Delta(B))$ be the prior buyer distribution.222For any set $A$, we denote
by $int(A)$ the interior of $A$, and $\Delta(A)$ is the set of all probability
distributions over $A$. A segmentation of the market designer is a Bayes
plausible posterior distribution $\sigma$, i.e., the set of all possible
segmentation is given by:

$\Sigma\coloneqq\\{\sigma\in\Delta(\Delta(B))|\operatorname*{\mathbb{E}}_{p\sim\sigma}[p]=\mu\\}.$

We assume that when indifferent, the seller sets the lowest price. Also, when
the buyer is indifferent (i.e., the price equals its valuation) the buyer buys
the product. Thus, for a given posterior $p\in\Delta(B)$, the seller’s price
is given by:

$\pi(p;\operatorname*{s})\coloneqq\min{\operatorname*{argmax}_{b_{i}\in
B}(b_{i}-\operatorname*{s})\cdot{\sum_{j=i}^{n}p_{j}}}.$

We denote by $b_{i^{*}}$ the _monopolistic price_ that is the price that will
be set without any information; i.e., $b_{i^{*}}=\pi(\mu;\operatorname*{s})$.

We consider a market designer who aims to maximize the buyer’s surplus. For a
given posterior $p\in\Delta(B)$, the buyer’s surplus is

$U(p;\operatorname*{s})\coloneqq{\sum_{j=1}^{n}p_{j}\cdot\max\\{b_{j}-\pi(p;\operatorname*{s}),0\\}}$

and the buyer surplus for a given segmentation $\sigma\in\Sigma$ is simply the
expectation over the possible posteriors:

$U(\sigma,\operatorname*{s})\coloneqq\operatorname*{\mathbb{E}}_{p\sim\sigma}[U(p;\operatorname*{s})]=\sum_{p\in\operatorname*{\operatorname{supp}}{\sigma}}\sigma(p)\cdot{\sum_{j=1}^{n}p_{j}\cdot\max\\{b_{j}-\pi(p;\operatorname*{s}),0\\}}$

where the summation over $p$ should be replaced with integration if
$\operatorname*{\operatorname{supp}}{\sigma}$ is an uncountable set.

We denote by $U^{*}(\operatorname*{s})$ the optimal buyers surplus (across all
segmentations), and by $\sigma^{*}(\operatorname*{s})$ the optimal market
segmentation. Bergemann et al. (2015) provide a very clean formula for
$U^{*}(\operatorname*{s})$:

$U^{*}(\operatorname*{s})=\sum_{j=1}^{n}\mu_{j}\cdot\max\\{b_{j}-\operatorname*{s},0\\}-(b_{i^{*}}-\operatorname*{s})\cdot\sum_{j=i^{*}}^{n}\mu_{j}$
(1)

This formula has a clean interpretation. The first term captures the maximal
social welfare. The second term is the monopolistic surplus of the seller.
Notice that the monopolistic surplus can be guaranteed by the seller for every
segmentation $\sigma$ (simply by ignoring the information). The sum of
surpluses (buyer plus seller) cannot exceed the social welfare. From these
trivial arguments, we deduce that the expression of equation (1) is an upper
bound on the buyer’s surplus. The surprising result of Bergemann et al. (2015)
shows that this bound can be reached by a careful choice of segmentation. This
optimal segmentation is denoted by $\sigma^{*}(s)$.

The behavior of the optimal surplus $U^{*}$ as a function of the seller’s
value for the product $\operatorname*{s}$ will play a significant role in our
analysis. We summarize below the key properties that will be utilized.

######  Lemma 1.

For every prior buyer distribution $\mu$ the optimal buyer surplus function
$U^{*}(\cdot)$ is weakly decreasing, continuous, nonnegative, and
differentiable up to a finite number of points. Moreover, there exists
$s^{*}\geq 0$ such that $U^{*}(\operatorname*{s})$ is constant over
$[0,s^{*}]$, strictly decreasing over $[s^{*},b_{n-1}]$, and constantly 0 over
$[b_{n-1},\infty)$.

The proof of Lemma 1 is relegated to Appendix A.1.

##  3 The Bayesian Approach

In this section, we observe that the Bayesian model boils down to a standard
Bayesian persuasion problem. However, the persuasion problem is
$n$-dimensional. We demonstrate by examples that even in the case in which $n$
is low (i.e., $n=2$) the indirect utility of the persuasion problem takes an
intricate form.

We assume that $\operatorname*{s}$ is drawn from a commonly known prior
distribution $F$, where $F$ is the CDF of the prior distribution. The
segmentation problem now can be viewed as a standard Bayesian persuasion
problem as introduced by Kamenica and Gentzkow (2011). The unknown state is
the buyer’s valuation $b$ which is drawn from a common prior distribution
$\mu$. The market designer (the _sender_ in persuasion) knows the state and
chooses a segmentation (a _signaling policy_ in persuasion). The seller is the
receiver. The market designer’s utility as a function of the seller’s
posterior (the _indirect utility_) is given by

$u_{F}(p)=\mathbb{E}_{\operatorname*{s}\sim F}[U(p,\operatorname*{s})]$

Building upon Aumann et al. (1995), Kamenica and Gentzkow (2011) elegantly
characterize the solution of this persuasion problem via the notion of
concavification which is denoted by $cav$.333Concavification of $u$ is defined
to be the minimal concave function that is pointwise above $u$. The optimal
expected utility of the market designer is $cav(u_{F})(\mu)$. Moreover, a
segmentation $\sigma\in\Sigma$ is optimal if and only if
$(\mu,cav(u_{F})(\mu))$ is a convex combination of $(p,u_{F}(p))_{p\in
supp(\sigma)}$, with weights corresponding to $(\sigma(p))_{p\in
supp(\sigma)}$.

We now demonstrate how even in the case of binary buyer type (i.e., $n=2$) the
analysis of the Bayesian model turns out to be potentially complex and
involved. We begin with constructing the indirect utility function of the
market designer, as a function of $p=P(b_{1})$:

First, let $t(p)$ be the threshold $\operatorname*{s}$ for which the seller is
indifferent between prices $b_{1}$ and $b_{2}$, when the posterior belief is
$p=\operatorname*{\text{I\kern-1.49994ptP}}(b_{1})$. For simplicity, let us
assume that $b_{2}-b_{1}=1$. Now, It holds that:

$b_{1}-t(p)=(b_{2}-t(p))\cdot(1-p)\Rightarrow
t(p)=\frac{b_{1}-b_{2}\cdot(1-p)}{p}=b_{2}-\frac{1}{p}$

Now, notice that the buyer surplus is non-zero if and only if
$\operatorname*{s}\leq t(p)$ and $v=b_{2}$. In this case, the surplus is
$b_{2}-b_{1}$. When $\operatorname*{s}\geq t(p)$ and $v=b_{1}$ there is no
trade, hence zero surplus. When $\operatorname*{s}\leq t(p)$ and $v=b_{1}$
(or, symmetrically, when $\operatorname*{s}\geq t(p)$ and $v=b_{2}$) there is
trade, but zero surplus $b_{1}-b_{1}$ (or $b_{2}-b_{2}$). Therefore, the
indirect utility of the market designer is given by:

$u(p)=(b_{2}-b_{1})\cdot(1-p)\cdot F(t(p))=(1-p)\cdot F(t(p))$

where the last equality is due to the assumption of $b_{2}-b_{1}=1$. Example 1
demonstrates how the optimal buyer surplus can be characterized through the
notion of indirect utility concavification:

######  Example 1.

Consider the case where $b_{2}=2,b_{1}=1$ and $\operatorname*{s}\sim
Uni([0,3])$. Note that $t(p)=2-\frac{1}{p}\geq 0$ if and only if
$p\geq\frac{1}{2}$, and $t(p)\leq 1$ for all $p\in[0,1]$. Therefore, the
indirect utility of the market designer is given by:

$u(p)=\left\\{\begin{array}[]{lr}0,&\text{for }p\leq\frac{1}{2}\\\
\frac{(1-p)(2p-1)}{3p},&\text{for }p\geq\frac{1}{2}\\\ \end{array}\right\\}$

Figure 1 visualizes the indirect utility and its concavification:

0$\frac{1}{2}$1$p$$u(p)$$cav(u)(p)$ Figure 1: The indirect utility of the
market designer $u(p)$ and its concavification, corresponding to Example 1.

In Example 1, the resulting optimal segmentation takes the standard form of an
optimal market segmentation presented by Bergemann et al. (2015): one signal
fully reveals the higher type while another signal induces a mixed posterior.
However, it turns out that this is not always the case. Consider the following
example, which is similar to Example 1 except the prior distribution over
$\operatorname*{s}$ is different. It is notable that in this case, the optimal
market segmentation may take a different form:

######  Example 2.

Consider the case where $b_{2}=4,b_{1}=3$ and $\operatorname*{s}\sim
Uni([0,1]\cup[2\frac{1}{2},3\frac{1}{2}])$. Note that
$t(p)=4-\frac{1}{p}\in[0,1]$ if and only if $p\in[\frac{1}{4},\frac{1}{3}]$,
and $t(p)\in[2\frac{1}{2},3\frac{1}{2}]$ if and only if $p\geq\frac{2}{3}$.
Therefore, the indirect utility of the market designer is given by:

$u(p)=\left\\{\begin{array}[]{lr}0,&\text{for }p\in[0,\frac{1}{4}]\\\
\frac{(1-p)(4p-1)}{2p},&\text{for }p\in[\frac{1}{4},\frac{1}{3}]\\\
\frac{1-p}{2},&\text{for }p\in[\frac{1}{3},\frac{2}{3}]\\\
\frac{1-p}{2}\cdot(4-\frac{1}{p}-\frac{3}{2}),&\text{for
}p\in[\frac{2}{3},1]\\\ \end{array}\right\\}$

Figure 2 visualizes the indirect utility and its concavification, and it can
be now seen that for certain priors $\mu$, the optimal segmentation has a
different, more complex structure compared to the previous example: for
instance, if $\mu=\frac{2}{3}$, the optimal segmentation is a mixture of two
mixed posterior, which is different than the optimal segmentation as in
Bergemann et al. (2015).

0$\frac{1}{4}$$\frac{1}{3}$$\frac{2}{3}$1$p$$u(p)$$cav(u)(p)$ Figure 2: The
indirect utility of the market designer $u(p)$ and its concavification,
corresponding to Example 2.

Example 2 demonstrates the potential complexity in the analysis of the
Bayesian price discrimination model. As we show next, it turns out that in
contrast, the robust approach is very insightful in our setting.

##  4 The Robust Approach

As demonstrated in the previous section, the Bayesian approach may be
involved. In addition, it requires assuming a prior distribution over the
seller’s valuation, which is not always plausible. An alternative approach for
studying the price discrimination model with uncertainty regarding the
seller’s valuation is the _robust_ approach. According to this approach, the
market designer is not equipped with such a prior seller distribution, and its
goal is to minimize the _regret_ , which is defined as the maximal difference
between the optimal buyer surplus (as if the market designer would have known
$\operatorname*{s}$) and the buyer surplus of the segmentation, where the
maximum is taken over the values of $\operatorname*{s}$. Formally, the regret
of a given segmentation is defined as follows:

$R(\sigma)\coloneqq\max_{\operatorname*{s}}\\{U^{*}(\operatorname*{s})-U(\sigma,\operatorname*{s})\\}$

and the _overall regret_ is defined as the minimal regret that can be achieved
by any market segmentation:

$R\coloneqq\min_{\sigma\in\Sigma}{R(\sigma)}$

Importantly, note that the overall regret of the non-Bayesian model also be
written in terms of the indirect utility concavification (as in the Bayesian
approach):

$R=\sup_{F}\\{\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F}[U^{*}(\operatorname*{s})]-cav(u_{F})(\mu)\\}$ (2)

Equation (2) follows from the min-max theorem. We view the interaction as a
zero-sum game between the market designer (who chooses a segmentation) and the
adversary (who chooses $\operatorname*{s}$). By the min-max theorem, there
exists a mixed strategy of the adversary $F$ that guarantees the value of the
game $R$ where $cav(u_{F})(\mu)$ is the best reply of the market designer
against the mixed strategy $F$.

Our goal is to find a market segmentation that is independent of
$\operatorname*{s}$ and achieves low regret. That is, we want to find an
information revelation policy of the market designer that is robust to the
seller’s valuation $\operatorname*{s}$, and achieves a near-optimal buyer
surplus regardless of it.

We now introduce a robust market segmentation of the designer, and show that
the overall regret is bounded from above by $U^{*}(0)/e$. Then, we also show
that this bound is tight for the case of binary buyer type, i.e. when $n=2$.
This robust market segmentation takes the following form: the market designer
first draws $s_{D}$, and then it applies the optimal segmentation of Bergemann
et al. (2015) _as if_ $\operatorname*{s}=s_{D}$. We begin by formally defining
the class of segmentation that contains our robust market segmentation for the
market designer:

######  Definition 1.

A BBM market segmentation is a strategy of the market designer
$\sigma\in\Sigma$, for which there exists a random variable $s_{D}$ such that
for every posterior $p\in\Delta(B)$, $p$ is drawn with probability
$\sigma(p)=\operatorname*{\mathbb{E}}[\sigma^{*}(s_{D})(p)]$.

Note that in the case where $s_{D}$ is a continuous random variable, the BBM
segmentation can be identified with the corresponding density function $g$. In
this case, the unconditional posterior distribution can be written as
$\sigma(p)=\int_{s_{D}=0}^{b_{n}}g(s_{D})\cdot\sigma^{*}(s_{D})(p)\cdot
ds_{D}$. Now, the following theorem introduces our main result:

######  Theorem 1.

The overall regret is bounded from above by $\frac{U^{*}(0)}{e}$, and this
bound is attained by a BBM market segmentation.

The proof of the theorem relies on the analysis of a specific class of zero-
sum games with a continuum of actions. The class of games and the solution is
summarized in the following lemma.

######  Lemma 2.

Let $0<\alpha<\beta$, and let $u:[0,\beta]\to\mathbb{R}_{+}$ be a function
that is constant in $[0,\alpha]$ and strictly decreasing in $[\alpha,\beta]$.
Let $v$ be a two-player zero-sum game in which players 1,2 choose real numbers
$x,y\in[0,\beta]$ (correspondingly). The utility of Player 1 is given by

$v(x,y)=\left\\{\begin{array}[]{lr}u(x),&\text{for }x>y\\\
u(x)-u(y),&\text{for }x\leq y\end{array}\right\\}$

Then, the value of the game is $\frac{u(0)}{e}$, and it can be guaranteed to
Player 2 by playing a mixed strategy with the following density function:

$g(y)=\left\\{\begin{array}[]{lr}-\frac{u^{\prime}(y)}{u(y)},&\text{for
}\alpha\leq y\leq\delta\\\ 0,&\text{otherwise}\end{array}\right\\}$

for $\delta$ such that $u(\delta)=\frac{u(0)}{e}$.444The monotonicity of $u$
implies that $u$ is differentiable almost everywhere, and therefore the
density function $g$ is defined almost everywhere.

Notice the value of the game depends on the initial condition $u(0)$ and does
not depend on the behavior of the function $u$ beside the monotonicity
property. This property is somewhat surprising because the utilities in the
game depend on the behavior of $u$ on the entire interval $[0,\beta]$ and in
equilibrium, both players are playing actions in $[\alpha,\beta]$ with
positive probability. Intuitively, this property follows from the particular
additive structure of the payoffs and the ability of the players to adjust
their mixed strategy to ”cancel out” the dependence on the particular behavior
of $u$ in $[\alpha,\beta]$. Moreover, for both players, it is optimal to
cancel this dependence out. The proof of Lemma 2 is relegated to Appendix A.2.

We now turn to introduce the proof of Theorem 1:

###### Proof of Theorem 1..

Consider a zero-sum game between the market designer and an adversary, in
which the adversary chooses $\operatorname*{s}$ and the market designer
chooses $s_{D}$, and then plays $\sigma^{*}(s_{D})$. The utility of the
adversary in this zero-sum game is defined to be the difference between the
optimal buyer surplus $U^{*}(\operatorname*{s})$, and the actual buyer
surplus, $U(\sigma^{*}(s_{D}),\operatorname*{s})$. Trivially, the value of
this game is an upper bound on the overall regret, since the market designer
is forced to play a BBM segmentations. Denote the utility function of the
adversary in the auxiliary game by $v$, and by definition it holds that:

$v(\operatorname*{s},s_{D})=U^{*}(\operatorname*{s})-U(\sigma^{*}(s_{D}),\operatorname*{s})$

First, notice that from the non-negativity of the buyer surplus, it holds that
$v(\operatorname*{s},s_{D})\leq U^{*}(\operatorname*{s})$ for any
$\operatorname*{s}$ and $s_{D}$. Moreover, for any fixed segmentation
$\sigma$, the buyer surplus $U(\sigma,\operatorname*{s})$ is non-increasing as
a function of $\operatorname*{s}$. Therefore, $\operatorname*{s}\leq s_{D}$
implies that $U(\sigma^{*}(s_{D}),\operatorname*{s})\geq
U(\sigma^{*}(s_{D}),s_{D})=U^{*}(s_{D})$, which means that
$v(\operatorname*{s},s_{D})\leq U^{*}(\operatorname*{s})-U^{*}(s_{D})$.
Altogether, for any $\operatorname*{s}$ and $s_{D}$, it holds that
$v(\operatorname*{s},s_{D})$ is bounded from above by the following function:

$\tilde{v}(\operatorname*{s},s_{D})=\left\\{\begin{array}[]{lr}U^{*}(\operatorname*{s}),&\text{for
}\operatorname*{s}>s_{D}\\\ U^{*}(\operatorname*{s})-U^{*}(s_{D}),&\text{for
}\operatorname*{s}\leq s_{D}\end{array}\right\\}$

Therefore, the value of the game defined by $\tilde{v}$ is an upper bound of
the value of the game defined by $v$, and hence it also bounds the overall
regret from above.

Note that for the adversary, playing $\operatorname*{s}>b_{n-1}$ in the game
defined by $\tilde{v}$ yields utility $0$ regardless of the market designer’s
strategy $s_{D}$, hence it is weakly a dominated strategy (e.g. by $b_{n-1}$).
Now, for the market designer, playing $s_{D}>b_{n-1}$ is equivalent to
$b_{n-1}$ since $s_{D}\geq\operatorname*{s}$ and $U^{*}(s_{D})=0$. Therefore,
for the purpose of finding the value of the game, it can be assumed without
loss of generality that both players play $s_{D}>b_{n-1}$ and
$\operatorname*{s}>b_{n-1}$ with probability zero.

Now, Lemma 1 implies that the game defined by $\tilde{v}$ (after strategies
elimination) satisfies the conditions of Lemma 2. Hence, the value of the game
defined by $\tilde{v}$ is $\frac{U^{*}(0)}{e}$, and therefore this is an upper
bound on the overall regret that can be attained by a BBM segmentation of the
market designer.

∎

Notice that Lemma 2 enables the construction of a concrete market segmentation
that guarantees this upper bound on the regret since the market designer
corresponds to Player 2 in Lemma 2.

###  4.1 Special Case: Binary Buyer Type

We now turn to analyze the special case in which there are only two possible
buyer types, namely $n=2$. We show that in this case, the upper bound on the
overall regret obtained in Theorem 1 is tight, by showing a mixed strategy of
the adversary that guarantees a regret of at least $\frac{U^{*}(0)}{e}$, and
combined with the upper bound presented in Theorem 1 we conclude that the
overall regret is precisely $\frac{U^{*}(0)}{e}$.

Let $b_{2}$ and $b_{1}$ be the two possible buyer valuations. Without loss of
generality, we assume that $b_{2}-b_{1}=1$.555This is without loss of
generality since both the regret and the optimal buyer surplus function are
linear in the difference between the two buyer valuations. For any posterior
$p\in\Delta(B)$ we identify $p$ with
$\operatorname*{\text{I\kern-1.49994ptP}}_{p}(b_{1})=p_{1}$. We note that now
the seller’s optimal price and the buyer surplus function take the following
simpler form for any given posterior $p$ and seller valuation
$\operatorname*{s}$:

$\pi(p;\operatorname*{s})\coloneqq\left\\{\begin{array}[]{lr}b_{1},&\text{for
}b_{1}-\operatorname*{s}\geq(b_{2}-\operatorname*{s})(1-p)\\\ b_{2},&\text{for
}b_{1}-\operatorname*{s}<(b_{2}-\operatorname*{s})(1-p)\end{array}\right\\}$

$U(p;\operatorname*{s})\coloneqq\left\\{\begin{array}[]{lr}1-p,&\text{for
}b_{1}-\operatorname*{s}\geq(b_{2}-\operatorname*{s})(1-p)\\\ 0,&\text{for
}b_{1}-\operatorname*{s}<(b_{2}-\operatorname*{s})(1-p)\end{array}\right\\}$

In the following technical Lemma, we use the result of Bergemann et al. (2015)
to obtain a closed form of the optimal buyers surplus when $\operatorname*{s}$
is known to the market designer:

######  Lemma 3.

When $n=2$ and $\operatorname*{s}$ is known to the market desginer, the
optimal buyers surplus is given by:

$U^{*}(\operatorname*{s})=\left\\{\begin{array}[]{lr}1-\mu,&\text{for
}\operatorname*{s}<b_{2}-\frac{1}{\mu}\\\
(b_{1}-\operatorname*{s})\mu,&\text{for
}b_{2}-\frac{1}{\mu}\leq\operatorname*{s}\leq b_{1}\\\ 0,&\text{for
}\operatorname*{s}>b_{1}\end{array}\right\\}$

0$b_{2}-\frac{1}{\mu}$$b_{1}$$s$$U^{*}(s)$ Figure 3: The optimal buyer surplus
function in the case of binary buyer type.

The proof of Lemma 3 is relegated to Appendix A.3. Figure 3 visualizes the
optimal buyer surplus function in the case of binary buyer type. Using this
technical Lemma we can now conclude that the overall regret in the binary
buyer type case is precisely $\frac{U^{*}(0)}{e}$:

######  Theorem 2.

When $n=2$, the overall regret is $\frac{U^{*}(0)}{e}$, and it is obtained by
a BBM market segmentation.

In order to prove Theorem 2 we make use of the Bayesian approach presented in
Subsection 3. We recall that the overall regret can be expressed in Bayesian
terms (see Equation (2)). This will be now used to show that in the case of
binary type case, the adversary has a strategy $F$ in the zero-sum game that
guarantees a regret of at least $\frac{U^{*}(0)}{e}$, which proves the
tightness of the bound obtained in Theorem 1.

###### Proof of Theorem 2..

Consider a zero-sum game between the market designer and an adversary, in
which the market designer selects a market segmentation $\sigma$ and the
adversary selects $\operatorname*{s}$ to maximize the regret. Note that unlike
the game defined in the proof of Theorem 1, in this game the market designer
is not restricted to BBM segmentations, and can choose any arbitrary market
segmentation $\sigma\in\Sigma$. Denote the value of this game by $R$, and note
that the value of this game is the overall regret. From Theorem 1,
$R\leq\frac{U^{*}(0)}{e}$. It is therefore left to show that the adversary has
a mixed strategy that guarantees a utility of at least $\frac{U^{*}(0)}{e}$.

For each $\beta\in[b_{2}-\frac{1}{\mu},b_{1})$, define a distribution
$F_{\beta}$ such that $supp(F_{\beta})=[0,\beta]$:

$\forall t\in[0,\beta]:F_{\beta}(t)=\frac{b_{1}-\beta}{b_{1}-t}$

Notice that the distribution has an atom at $x=0$, and the corresponding
density function is given by $f_{\beta}(t)=\frac{b_{1}-\beta}{(b_{1}-t)^{2}}$.
Now, under the assumption that $\operatorname*{s}\sim F_{\beta}$, the indirect
utility of the market designer, as a function of the belief
$p=\operatorname*{\text{I\kern-1.49994ptP}}_{p}(b_{1})$, is given by:

$u_{\beta}(p)=(1-p)F_{\beta}(t(p))$

Plugging in $F_{\beta}$, we obtain:

$u_{\beta}(p)=\left\\{\begin{array}[]{lr}0,&\text{for }p<\frac{1}{b_{2}}\\\
(b_{1}-\beta)p,&\text{for }\frac{1}{b_{2}}\leq p\leq\frac{1}{b_{2}-\beta}\\\
1-p,&\text{for }p>\frac{1}{b_{2}-\beta}\end{array}\right\\}$

The concavification of the indirect utility has the following form:

$cav(u_{\beta})(p)=\left\\{\begin{array}[]{lr}(b_{1}-\beta)p,&\text{for
}p\leq\frac{1}{b_{2}-\beta}\\\ 1-p,&\text{for
}p\geq\frac{1}{b_{2}-\beta}\end{array}\right\\}$

0$\frac{1}{b_{2}}$$\frac{1}{b_{2}-\beta}$1$p$$u_{\beta}(p)$$cav(u_{\beta})(p)$
Figure 4: The indirect utility of the market designer $u_{\beta}(p)$ and its
concavification, for a given distribution $F_{\beta}$ over
$\operatorname*{s}$.

Note that the concavification has the structure of a triangle (see Figure 4):
for $p\leq\frac{1}{b_{2}-\beta}$ it is a linear function with slope
$(b_{1}-\beta)$, and for $p>\frac{1}{b_{2}-\beta}$ it is a linear function
with slope $-1$. Using the distribution family $\\{F_{\beta}\\}_{\beta<b_{1}}$
combined with Equation (2), we can obtain the following lower bound on the
overall regret:

$R\geq\sup_{b_{2}-\frac{1}{\mu}\leq\beta<b_{1}}R(F_{\beta})$ (3)

Since we chose $\beta\geq b_{2}-\frac{1}{\mu}$, we know that
$cav(u_{\beta})(\mu)=(b_{1}-\beta)\mu$. It is now left to compute
$\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F_{\beta}}[U^{*}(\operatorname*{s})]$, and here we distinguish between two
cases:

First case: $\mu\leq\frac{1}{b_{2}}$. In this case, we know that
$b_{2}-\frac{1}{\mu}\leq 0$. Therefore, for every $\operatorname*{s}$ in the
support of $F_{\beta}$, it holds that $\operatorname*{s}\geq 0\geq
b_{2}-\frac{1}{\mu}$, and Lemma 3 implies that
$U^{*}(\operatorname*{s})=(b_{1}-\operatorname*{s})\mu$. Now,

$\displaystyle\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F_{\beta}}[U^{*}(\operatorname*{s})]$ $\displaystyle=F_{\beta}(0)\cdot
U^{*}(0)+\int_{\operatorname*{s}=0}^{\beta}U^{*}(\operatorname*{s})f_{\beta}(\operatorname*{s})d\operatorname*{s}$
$\displaystyle=(b_{1}-\beta)\mu+\int_{\operatorname*{s}=0}^{\beta}U^{*}(\operatorname*{s})f_{\beta}(\operatorname*{s})d\operatorname*{s}$
$\displaystyle=(b_{1}-\beta)\mu+\mu\int_{\operatorname*{s}=0}^{\beta}(b_{1}-\operatorname*{s})\cdot\frac{b_{1}-\beta}{(b_{1}-\operatorname*{s})^{2}}d\operatorname*{s}$
$\displaystyle=(b_{1}-\beta)\mu+\mu\int_{\operatorname*{s}=0}^{\beta}\cdot\frac{b_{1}-\beta}{b_{1}-\operatorname*{s}}d\operatorname*{s}$
$\displaystyle=(b_{1}-\beta)\mu\bigg{(}1+\ln(b_{1})-ln(b_{1}-\beta)\bigg{)}$
$\displaystyle=(b_{1}-\beta)\mu\bigg{(}1+\ln\bigg{(}\frac{b_{1}}{b_{1}-\beta}\bigg{)}\bigg{)}$

Second case: $\mu>\frac{1}{b_{2}}$. In this case, Lemma 3 implies that for
$\operatorname*{s}\in[0,b_{2}-\frac{1}{\mu}]$, the optimal surplus is
$U^{*}(\operatorname*{s})=1-\mu$, and otherwise
$U^{*}(\operatorname*{s})=(b_{1}-\operatorname*{s})\mu$. In this case, we
obtain:

$\displaystyle\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F_{\beta}}[U^{*}(\operatorname*{s})]$
$\displaystyle=\int_{\operatorname*{s}=0}^{\beta}U^{*}(\operatorname*{s})f_{\beta}(\operatorname*{s})d\operatorname*{s}$
$\displaystyle=\int_{\operatorname*{s}=0}^{b_{2}-\frac{1}{\mu}}U^{*}(\operatorname*{s})f_{\beta}(\operatorname*{s})d\operatorname*{s}+\int_{\operatorname*{s}=b_{2}-\frac{1}{\mu}}^{\beta}U^{*}(\operatorname*{s})f_{\beta}(\operatorname*{s})d\operatorname*{s}$
$\displaystyle=(1-\mu)F_{\beta}\bigg{(}b_{2}-\frac{1}{\mu}\bigg{)}+\mu\int_{\operatorname*{s}=b_{2}-\frac{1}{\mu}}^{\beta}(b_{1}-\operatorname*{s})\cdot\frac{b_{1}-\beta}{(b_{1}-\operatorname*{s})^{2}}d\operatorname*{s}$
$\displaystyle=(1-\mu)F_{\beta}\bigg{(}b_{2}-\frac{1}{\mu}\bigg{)}+\mu\int_{\operatorname*{s}=b_{2}-\frac{1}{\mu}}^{\beta}\frac{b_{1}-\beta}{b_{1}-\operatorname*{s}}d\operatorname*{s}$
$\displaystyle=(1-\mu)F_{\beta}\bigg{(}b_{2}-\frac{1}{\mu}\bigg{)}+\mu(b_{1}-\beta)\bigg{(}\ln\bigg{(}b_{1}-b_{2}+\frac{1}{\mu}\bigg{)}-\ln(b_{1}-\beta)\bigg{)}$
$\displaystyle=(1-\mu)F_{\beta}\bigg{(}b_{1}-\frac{1-\mu}{\mu}\bigg{)}+\mu(b_{1}-\beta)\bigg{(}\ln\bigg{(}\frac{1-\mu}{\mu}\bigg{)}-\ln(b_{1}-\beta)\bigg{)}$
$\displaystyle=\mu(b_{1}-\beta)+\mu(b_{1}-\beta)\ln\bigg{(}\frac{1-\mu}{\mu(b_{1}-\beta)}\bigg{)}$

Altogether, the regret with respect to $F_{\beta}$ as a function of $\mu$ is
given by:

$R(F_{\beta})=\left\\{\begin{array}[]{lr}\mu(b_{1}-\beta)\ln\big{(}\frac{b_{1}}{b_{1}-\beta}\big{)},&\text{for
}\mu\leq\frac{1}{b_{2}}\\\
\mu(b_{1}-\beta)\ln\big{(}\frac{1-\mu}{\mu(b_{1}-\beta)}\big{)},&\text{for
}\mu>\frac{1}{b_{2}}\end{array}\right\\}$

Now, let $\beta^{*}=b_{1}\bigg{(}1-\frac{1}{e}\bigg{)}$ if
$\mu\leq\frac{1}{b_{2}}$, otherwise $\beta^{*}=b_{1}-\frac{1-\mu}{e\cdot\mu}$.
Plugging into (3) we obtain the following lower bound:

$R\geq\sup_{b_{2}-\frac{1}{\mu}\leq\beta<b_{1}}R(F_{\beta})\geq
R(F_{\beta^{*}})=\left\\{\begin{array}[]{lr}\frac{b_{1}\mu}{e},&\text{for
}\mu\leq\frac{1}{b_{2}}\\\ \frac{1-\mu}{e},&\text{for
}\mu>\frac{1}{b_{2}}\end{array}\right\\}=\frac{U^{*}(0)}{e}$

∎

The result is somewhat surprising. To see why, recall that in the Bayesian
setting, optimal market segmentation is not necessarily a BBM segmentation
(see Example 2). However, Theorem 2 shows that in the binary buyer type case,
there always exists a regret-minimizing segmentation which is indeed a BBM
segmentation.

##  5 Experimental Results

We now turn to evaluate our robust segmentation by computing the surplus it
guarantees to buyers in different markets. For this experimental setting, we
consider the Bayesian model, and given a pair of buyer and seller
distributions we compute the _expected optimal buyer surplus_
$\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F}[U^{*}(\operatorname*{s})]$, and the _expected robust buyer surplus_
$\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F}[U(\sigma,\operatorname*{s})]$, where $\sigma$ is the robust market
segmentation that guarantees the overall regret upper bound of Theorem 1.
While the first reflects the surplus obtained by a market designer who knows
the exact valuation of the seller (and is realized by applying the algorithm
of Bergemann et al., 2015), the latter is the result when the designer is
devoid of any knowledge, including the seller’s valuation distribution. This
is the surplus that is obtained by our main result.

#### Results

We evaluate our robust segmentation with respect to markets in which the
seller and buyer distributions are identical, meaning that the seller’s
valuation $\operatorname*{s}$ is sampled from the distribution $\mu$
(independently from the buyer’s valuation). Following the work of Coad (2009),
we consider two distribution families that represent actual product quality
distributions in markets: the Pareto distribution and the Lognormal
distribution. In the following simulations, we performed a discretization of
these continuous distributions, using $n=15$ discrete values that approximate
the continuous distribution.666Transforming a continuous distribution $F$ into
a discrete random variable with support of size $n$ is done by taking the
values to be $b_{i}=\frac{i}{n}\cdot F^{-1}(1-\epsilon)$ for a small
$\epsilon>0$, with weights corresponding to $F(b_{i})-F(b_{i-1})$, where we
define $b_{0}=0$. For the Pareto distribution, we run simulations with varying
parameter $\alpha$, and for the lognormal distribution we fix the expectation
of the distribution across all experiments and run simulations with varying
parameter $\sigma$.777More precisely, $\sigma$ is the standard deviation for
the random variable $X\sim\mathcal{N}(m,\sigma^{2})$, for which $Y=e^{X}$ has
a lognormal distribution (where we fix $m=1$). Figure 5 shows the expected
optimal surplus achieved by the algorithm of Bergemann et al. (2015) (under
the assumption that $\operatorname*{s}$ is known), and the expected robust
surplus achieved by our segmentation (that relies on knowing the true
$\operatorname*{s}$). Notable, for all tested distributions, the robust
surplus provides a good approximation of the optimal surplus.

(a) Seller and buyer have a Lognormal distribution with fixed expectation and
standard deviation $\sigma$.

(b) Seller and buyer have a Pareto distribution with parameter $\alpha$.

Figure 5: Expected optimal and robust surplus as a function of a shared seller
and buyer distribution parameter.

Our main result guarantees that the maximal difference between the optimal
surplus and the robust surplus is at most $\frac{U^{*}(0)}{e}$. Our experiment
reveals that in practice, for these realistic seller and buyer distributions,
the expected difference between the two terms is significantly lower: Figure 6
shows this expected difference
$\operatorname*{\mathbb{E}}_{\operatorname*{s}\sim
F}[U^{*}(\operatorname*{s})-U(\sigma,\operatorname*{s})]$ compared to the
theoretical upper bound $\frac{U^{*}(0)}{e}$, and demonstrates that the actual
expected difference is much lower in practice. This implies that in some
settings (which might be considered as realistic, following Coad, 2009) our
robust segmentation performs significantly better than our worst-case bound on
the overall regret.

(a) Seller and buyer have a Lognormal distribution with fixed expectation and
standard deviation $\sigma$.

(b) Seller and buyer have a Pareto distribution with parameter $\alpha$.

Figure 6: Expected difference between optimal and robust surplus, and its
theoretical upper bound, as a function of a shared seller and buyer
distribution parameter.

##  6 Conclusions

This work studies the celebrated price discrimination problem of Bergemann et
al. (2015) under the relaxation of a major assumption of complete information
about the valuation of the seller. We began by introducing the natural
Bayesian model, in which the designer only knows a prior distribution of the
seller’s type, and demonstrated its complexity in terms of buyer-optimal
information revelation policy characterization. Then, we turn to the robust
approach, in which instead of assumpting a prior distribution we rather focus
on bounding the worst-case buyer surplus. Our main results suggest that our
two-stage approach of sampling a seller valuation and acting _as if_ this was
the true seller valuation, obtains an upper bound on the overall regret. We
further show that this bound is indeed tight in the binary buyer type case.
Lastly, we demonstrated that in some realistic markets, our approach yields a
regret which is even better than the worst-case guarantee. The question of
whether the upper bound on the overall regret is tight for an arbitrary number
of buyer types is left as an interesting open question.

We argue that many realistic applications of third-degree price discrimination
have the property of partial (or even completely no) information of the
seller’s valuation. As an example, consider an online retail platform, such as
Amazon or eBay, that can control the information available to the seller about
potential buyers by selective presentation of users’ information. Such
platforms may be interested in preserving the average satisfaction of their
uses, which translates into maximizing the buyers’ surplus in our price
discrimination model. In this scenario, it is unreasonable to assume that the
market designer knows exactly how much the seller appreciates her product. In
such a use case, our approach enables the platform to achieve a great level of
user satisfaction _regardless_ of the actual seller type, which may be
considered as an extremely strong guarantee.

## Acknowledgements

Itai Arieli gratefully acknowledges support from the Israel Science Foundation
(grant agreement 2029464). Yakov Babichenko gratefully acknowledges support
from the Bi-national Science Foundation (NSF-BSF grant # 2021680). The work by
Moshe Tennenholtz and Omer Madmon was supported by funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement 740435).

## References

  * Alijani et al. (2022) Reza Alijani, Siddhartha Banerjee, Kamesh Munagala, and Kangning Wang.  The limits of an information intermediary in auction design.  In _Proceedings of the 23rd ACM Conference on Economics and Computation_ , pages 849–868, 2022.
  * Arieli et al. (2023) Itai Arieli, Omer Madmon, and Moshe Tennenholtz.  Reputation-based persuasion platforms, 2023.
  * Aumann et al. (1995) Robert J Aumann, Michael Maschler, and Richard E Stearns.  _Repeated games with incomplete information_.  MIT press, 1995.
  * Babichenko et al. (2022) Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi.  Regret-minimizing bayesian persuasion.  _Games and Economic Behavior_ , 136:226–248, 2022.
  * Banerjee et al. (2023) Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang.  Fair price discrimination.  _arXiv preprint arXiv:2305.07006_ , 2023.
  * Bergemann et al. (2015) Dirk Bergemann, Benjamin Brooks, and Stephen Morris.  The limits of price discrimination.  _American Economic Review_ , 105(3):921–57, 2015\.  doi: 10.1257/aer.20130848.  URL https://www.aeaweb.org/articles?id=10.1257/aer.20130848.
  * Bergemann et al. (2022) Dirk Bergemann, Paul Duetting, Renato Paes Leme, and Song Zuo.  Calibrated click-through auctions.  In _Proceedings of the ACM Web Conference 2022_ , pages 47–57, 2022\.
  * Cai et al. (2020) Yang Cai, Federico Echenique, Hu Fu, Katrina Ligett, Adam Wierman, and Juba Ziani.  Third-party data providers ruin simple mechanisms.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 4(1):1–31, 2020.
  * Castiglioni et al. (2020) Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti.  Online bayesian persuasion.  _Advances in Neural Information Processing Systems_ , 33:16188–16198, 2020.
  * Coad (2009) Alex Coad.  On the distribution of product price and quality.  _Journal of Evolutionary Economics_ , 19:589–604, 2009\.
  * Cohen et al. (2022) Maxime C Cohen, Adam N Elmachtoub, and Xiao Lei.  Price discrimination with fairness constraints.  _Management Science_ , 68(12):8536–8552, 2022\.
  * Cummings et al. (2020) Rachel Cummings, Nikhil R Devanur, Zhiyi Huang, and Xiangning Wang.  Algorithmic price discrimination.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2432–2451. SIAM, 2020.
  * Dworczak and Pavan (2022) Piotr Dworczak and Alessandro Pavan.  Preparing for the worst but hoping for the best: Robust (bayesian) persuasion.  _Econometrica_ , 90(5):2017–2051, 2022.
  * Flammini et al. (2021) Michele Flammini, Manuel Mauro, and Matteo Tonelli.  On fair price discrimination in multi-unit markets.  _Artificial Intelligence_ , 290:103388, 2021.
  * Kamenica and Gentzkow (2011) Emir Kamenica and Matthew Gentzkow.  Bayesian persuasion.  _American Economic Review_ , 101(6):2590–2615, 2011.
  * Ko and Munagala (2022) Shao-Heng Ko and Kamesh Munagala.  Optimal price discrimination for randomized mechanisms.  In _Proceedings of the 23rd ACM Conference on Economics and Computation_ , pages 477–496, 2022.
  * Mao et al. (2021) Jieming Mao, Renato Paes Leme, and Kangning Wang.  Interactive communication in bilateral trade.  _arXiv preprint arXiv:2106.02150_ , 2021.
  * Myerson and Satterthwaite (1983) Roger B Myerson and Mark A Satterthwaite.  Efficient mechanisms for bilateral trading.  _Journal of economic theory_ , 29(2):265–281, 1983.
  * Pigou (1920) Arthur Pigou.  _The economics of welfare_.  Routledge, 1920.
  * Shen et al. (2018) Weiran Shen, Pingzhong Tang, and Yulong Zeng.  A closed-form characterization of buyer signaling schemes in monopoly pricing.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 1531–1539, 2018.

##  Appendix A Omitted Proofs

###  A.1 Proof of Lemma 1

###### Proof.

First, notice that $U^{*}(\cdot)$ is continuous and non-negative by
definition. As for its differentiability and monotonicity properties, we first
recall that the optimal market segmentation $\sigma^{*}(\operatorname*{s})$
takes the following form: if $b_{1}=\pi(\mu;\operatorname*{s})$ then the
optimal market segmentation consists of the prior buyer distribution solely,
i.e. $\sigma^{*}(\mu)=1$. Otherwise, it consists of a set of at most $n$
posteriors, such that at any posterior $p$ the seller is indifferent between
the monopolistic price $\pi(\mu;\operatorname*{s})$ and the lowest buyer type
in the support of $p$. Since the optimal price $\pi(\mu;\operatorname*{s})$ is
weakly decreasing in $\operatorname*{s}$, we get that there must exist some
$s^{*}$ such that no segmentation is optimal if and only if
$\operatorname*{s}<s^{*}$.

Next, note that $U^{*}(\cdot)$ is differentiable up to a finite number of
points, corresponding to the set of points for which the seller is indifferent
between several prices.

It can be now seen from Equation (1) that whenever no segmentation is optimal
(namely $\operatorname*{s}<s^{*}$, which means $i^{*}=1$), $U^{*}(\cdot)$ is
constant and equals $\sum_{j=1}^{n}\mu_{j}\cdot(b_{j}-b_{1})$.

Next, assume that $s^{*}\leq\operatorname*{s}<b_{n-1}$, and in particular
$i^{*}>1$. It is clear that in this case $i^{*}<n$ (since setting the price
$b_{n}$ yields zero utility for the seller, while setting it to e.g. $b_{n-1}$
yields some positive utility, since buyers of type $b_{n}$ will buy the
product). In this case, the optimal buyer surplus can be written as follows:

$U^{*}(\operatorname*{s})=\sum_{j<i^{*}}\mu_{j}\cdot\max\\{b_{j}-\operatorname*{s},0\\}+\sum_{j\geq
i^{*}}\mu_{j}\cdot\bigr{(}\max\\{b_{j}-\operatorname*{s},0\\}-(b_{i^{*}}-\operatorname*{s})\bigl{)}$

For all $j\geq i^{*}$ it holds that $b_{j}\geq
b_{i^{*}}\geq\operatorname*{s}$, and therefore
$\max\\{b_{j}-\operatorname*{s},0\\}-(b_{i^{*}}-\operatorname*{s})=b_{j}-b_{i^{*}}$.
Hence, the rightmost sum is independent of $\operatorname*{s}$. In addition,
there exists at least one $j<i^{*}$ for which $b_{j}>\operatorname*{s}$ and
the leftmost sum is strictly decreasing as a sum of strictly decreasing
functions. Finally, it is clear that when $\operatorname*{s}\geq b_{n-1}$, the
optimal price corresponds to the highest buyer type (namely, $i^{*}=n$), and
$U^{*}(\operatorname*{s})=0$.

∎

###  A.2 Proof of Lemma 2

###### Proof.

Let us consider a mixed strategy profile, in which player 1 chooses a
distribution with density $f$ and CDF $F$, and player 2 chooses a distribution
with density $g$, both with support $[\alpha,\delta]$ for some
$\alpha<\delta\leq\beta$ (where the distribution $f$ also has an atom at
zero). Then, $(f,g)$ is a mixed Nash equilibrium if the following indifference
conditions hold:

  1. 1.

$v(x,g)$ is independent of $x$.

  2. 2.

$v(f,y)$ is independent of $y$, for $y\in[\alpha,\delta]$.

  3. 3.

$v(f,y)\leq v(f,\delta)$ for $y\notin[\alpha,\delta]$.

To satisfy the first condition, we require:

$\frac{\partial v(x,g)}{\partial x}=0$

Since $v(x,g)=u(x)-\int_{y=x}^{\delta}g(y)u(y)dy$, the above condition holds
if and only if:

$u^{\prime}(x)+g(x)u(x)=0\Leftrightarrow g(x)=-\frac{u^{\prime}(x)}{u(x)}$

Notice that indeed $g\geq 0$, since $u$ is non-increasing and nonnegative.
Now, $\delta$ can be found using the normalization constraint of the
distribution $g$:

$1=\int_{x=\alpha}^{\delta}g(x)dx=-\int_{x=\alpha}^{\delta}\frac{u^{\prime}(x)}{u(x)}\cdot
dx=\ln(u(\alpha))-\ln(u(\delta))$
$\Rightarrow\ln(u(\delta))=\ln(u(\alpha))-\ln(e)=\ln\Bigr{(}\frac{u(\alpha)}{e}\Bigr{)}\Rightarrow
u(\delta)=\frac{u(\alpha)}{e}=\frac{u(0)}{e}$

where the last equality come from the fact that $u$ is constant in range
$[0,\alpha]$.

As for the second condition, note that for any $y\in[\alpha,\delta]$:

$v(f,y)=\operatorname*{\mathbb{E}}_{x\sim f}[u(x)]-F(y)u(y)$

The condition holds for $F(y)=\frac{c}{u(y)}$ for some constant $c>0$ (note
that the distribution has an atom at zero). Note that $F$ is a valid CDF since
$u$ is strictly decreasing in $[\alpha,\delta]$. Now it is left to find $c$
for which this indifference holds for any $y\in[\alpha,\delta]$:

$F(\delta)=1\Leftrightarrow c=u(\delta)$

If $y<\alpha$, it holds that $F(y)=0$ and clearly $v(f,y)$ increases - hence
it is not beneficial for player 2 who aims to minimize $v$. Lastly, note that
for $y>\delta$, the term $F(y)u(y)$ decreases, hence $v(f,y)$ increases - and
therefore player 2 does not assign a positive probability for any
$y\notin[\alpha,\delta]$ when player 1 plays $f$.

Overall, we obtain that $(f,g)$ is a mixed Nash equilibrium, and the value of
the game is $u(\delta)=\frac{u(0)}{e}$, as $\delta$ is the highest action
played by player 2 with positive probability, and player 1 is indifferent and
might as well play $\delta$ with probability 1. In that case, $x>y$ with
probability $1$, and hence the value is $u(\delta)$.

∎

###  A.3 Proof of Lemma 3

###### Proof.

First, it is clear that if $\operatorname*{s}>b_{1}$ the seller never sells
the product regardless of the segmentation, and therefore the buyer surplus is
always zero. Assume now that this is not the case. Consider the equivalent
market segmentation problem without seller valuation, and with buyer types
$\tilde{b}_{i}\coloneqq b_{i}-\operatorname*{s}$ for $i\in\\{1,2\\}$. From
Bergemann et al. (2015), if $\tilde{b}_{1}$ is an optimal price in
$(\mu,1-\mu)$, then no segmentation is optimal, and the buyer surplus is
simply $1-\mu$. This happens if and only if:

$\tilde{b}_{1}\geq\tilde{b}_{2}(1-p)\Leftrightarrow\operatorname*{s}\leq
b_{2}-\frac{1}{\mu}$

otherwise, a segmentation that maximizes the buyer surplus is of the following
form:

$\begin{split}(0,1)\text{ w.p. }\alpha,\\\ (p,1-p)\text{ w.p.
}1-\alpha\end{split}$

Such that at the posterior $(p,1-p)$ the seller is indifferent between prices
$\tilde{b}_{1}$ and $\tilde{b}_{2}$, and Bayes plausibility holds. The buyer
surplus is $(1-p)(1-\alpha)$. The seller’s indifference condition yields:

$\tilde{b}_{1}=\tilde{b}_{2}(1-p)\Rightarrow
1-p=\frac{\tilde{b}_{1}}{\tilde{b}_{2}}$ (4)

and from the Bayes plausibility condition:

$x(1-\alpha)=\mu\Rightarrow 1-\alpha=\frac{\mu}{x}$ (5)

Combining (4) and (5), we get:

$(1-p)(1-\alpha)=\frac{\tilde{b}_{1}}{\tilde{b}_{2}}\cdot\frac{\mu}{1-\frac{\tilde{b}_{1}}{\tilde{b}_{2}}}=\tilde{b}_{1}\mu=(b_{1}-\operatorname*{s})\mu$

Finally, notice that for $\operatorname*{s}=b_{2}-\frac{1}{\mu}$,
$(b_{1}-\operatorname*{s})\mu=1-\mu$.

∎


* Wang et al. (2022a) Boshi Wang, Sewon Min, Xiang Deng, Jiaming Shen, You Wu, Luke Zettlemoyer, and Huan Sun.  Towards understanding chain-of-thought prompting: An empirical study of what matters.  _arXiv preprint arXiv:2212.10001_ , 2022a.
  * Wang et al. (2022b) Boxin Wang, Chejian Xu, Xiangyu Liu, Yu Cheng, and Bo Li.  SemAttack: Natural Textual Attacks via Different Semantic Spaces.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pp. 176–205, Seattle, United States, 2022b. Association for Computational Linguistics.  doi: 10.18653/v1/2022.findings-naacl.14.  URL https://aclanthology.org/2022.findings-naacl.14.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022.
  * Wei et al. (2023) Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, et al.  Larger language models do in-context learning differently.  _arXiv preprint arXiv:2303.03846_ , 2023.
  * Weidinger et al. (2021) Laura Weidinger, John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, et al.  Ethical and social risks of harm from language models.  _arXiv preprint arXiv:2112.04359_ , 2021.
  * Wiegreffe & Pinter (2019) Sarah Wiegreffe and Yuval Pinter.  Attention is not not Explanation, September 2019.  URL http://arxiv.org/abs/1908.04626.  arXiv:1908.04626 [cs].
  * Wu et al. (2023) Skyler Wu, Eric Meng Shen, Charumathi Badrinath, Jiaqi Ma, and Himabindu Lakkaraju.  Analyzing chain-of-thought prompting in large language models via gradient-based feature attributions.  2023\.
  * Wu et al. (2021) Tongshuang Wu, Marco Tulio Ribeiro, Jeffrey Heer, and Daniel Weld.  Polyjuice: Generating Counterfactuals for Explaining, Evaluating, and Improving Models.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 6707–6723, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.523.  URL https://aclanthology.org/2021.acl-long.523.
  * Wu & Ong (2021) Zhengxuan Wu and Desmond C. Ong.  On Explaining Your Explanations of BERT: An Empirical Study with Sequence Classification, January 2021.  URL http://arxiv.org/abs/2101.00196.  arXiv:2101.00196 [cs].
  * Wu et al. (2020a) Zhengxuan Wu, Thanh-Son Nguyen, and Desmond Ong.  Structured Self-Attention Weights Encode Semantics in Sentiment Analysis.  In _Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pp. 255–264, Online, November 2020a. Association for Computational Linguistics.  doi: 10.18653/v1/2020.blackboxnlp-1.24.  URL https://aclanthology.org/2020.blackboxnlp-1.24.
  * Wu et al. (2020b) Zhiyong Wu, Yun Chen, Ben Kao, and Qun Liu.  Perturbed Masking: Parameter-free Probing for Analyzing and Interpreting BERT.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 4166–4176, Online, July 2020b. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.383.  URL https://aclanthology.org/2020.acl-main.383.
  * Xiong et al. (2023) Miao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li, Jie Fu, Junxian He, and Bryan Hooi.  Can llms express their uncertainty? an empirical evaluation of confidence elicitation in llms.  _arXiv preprint arXiv:2306.13063_ , 2023.
  * Yang et al. (2023) Jingfeng Yang, Hongye Jin, Ruixiang Tang, Xiaotian Han, Qizhang Feng, Haoming Jiang, Bing Yin, and Xia Hu.  Harnessing the Power of LLMs in Practice: A Survey on ChatGPT and Beyond, April 2023.  URL http://arxiv.org/abs/2304.13712.  arXiv:2304.13712 [cs].
  * Yeh et al. (2023) Catherine Yeh, Yida Chen, Aoyu Wu, Cynthia Chen, Fernanda Viégas, and Martin Wattenberg.  AttentionViz: A Global View of Transformer Attention, May 2023\.  URL http://arxiv.org/abs/2305.03210.  arXiv:2305.03210 [cs].
  * Yin et al. (2023) Fan Yin, Jesse Vig, Philippe Laban, Shafiq Joty, Caiming Xiong, and Chien-Sheng Jason Wu.  Did you read the instructions? rethinking the effectiveness of task definitions in instruction learning.  _arXiv preprint arXiv:2306.01150_ , 2023.
  * Yordanov et al. (2022) Yordan Yordanov, Vid Kocijan, Thomas Lukasiewicz, and Oana-Maria Camburu.  Few-Shot Out-of-Domain Transfer Learning of Natural Language Explanations in a Label-Abundant Setup.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pp. 3486–3501, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  URL https://aclanthology.org/2022.findings-emnlp.255.
  * Yuksekgonul et al. (2023) Mert Yuksekgonul, Maggie Wang, and James Zou.  Post-hoc Concept Bottleneck Models, February 2023.  URL http://arxiv.org/abs/2205.15480.  arXiv:2205.15480 [cs, stat].
  * Zhang et al. (2022a) Lining Zhang, Mengchen Wang, Liben Chen, and Wenxin Zhang.  Probing GPT-3’s Linguistic Knowledge on Semantic Tasks.  In _Proceedings of the Fifth BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pp. 297–304, Abu Dhabi, United Arab Emirates (Hybrid), December 2022a. Association for Computational Linguistics.  URL https://aclanthology.org/2022.blackboxnlp-1.24.
  * Zhang et al. (2022b) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022b.
  * Zhong et al. (2021) Zexuan Zhong, Dan Friedman, and Danqi Chen.  Factual Probing Is [MASK]: Learning vs. Learning to Recall, December 2021.  URL http://arxiv.org/abs/2104.05240.  arXiv:2104.05240 [cs].
  * Zhou et al. (2023) Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, et al.  Lima: Less is more for alignment.  _arXiv preprint arXiv:2305.11206_ , 2023.