Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades

Zhengyang Liu [email protected] Beijing Institute of Technology Zeyu Ren [email protected] Renmin University of China Zihe Wang [email protected] Renmin University of China

Abstract

We continue the study of the performance for fixed-price mechanisms in the bilateral trade problem, and improve approximation ratios of welfare-optimal mechanisms in several settings. Specifically, in the case where only the buyer distribution is known, we prove that there exists a distribution over different fixed-price mechanisms, such that the approximation ratio lies within the interval of $[0.71,0.7381]$ . Furthermore, we show that the same approximation ratio holds for the optimal fixed-price mechanism, when both buyer and seller distributions are known. As a result, the previously best-known $(1-1/e+0.0001)$ -approximation can be improved to $0.71$ . Additionally, we examine randomized fixed-price mechanisms when we receive just one single sample from the seller distribution, for both symmetric and asymmetric settings. Our findings reveal that posting the single sample as the price remains optimal among all randomized fixed-price mechanisms.

1 Introduction

In this paper, we study the bilateral trade problem in a basic model: one buyer and one seller want to trade a single and indivisible good. Both of them have their own private valuations to the good, drawn from public distributions respectively. The mechanism designer can access both of their value distributions, but not their particular values. Depending on whether value distributions of these two agents are identical, we have the symmetric setting and the asymmetric (or general) setting. The designer aims to maximize the social welfare, i.e., the value of the one holding the good after the trade (if any).

Formally, we denote by $B$ the value of the buyer, and $S$ the value of the seller. The ideal solution is the so-called “first-best” mechanism, which is the case that the trade happens once $B>S$ and the corresponding social welfare would be $\max\left\{B,S\right\}$ . The celebrated result due to [MS83] states that no individually rational (IR) and Bayesian incentive-compatible (BIC) mechanism with the budget-balanced (BB) constraint can achieve the first-best optimum. In the same paper, Myerson and Satterthwaite also present a “second-best” mechanism attaining the optimal among all the IR, BIC and BB ones. However, a drawback of the second-best mechanism is that the characterization is complicated to describe and thus not suitable for practical implementation. Hence we need to pursue simple and almost-optimal mechanisms.

Fixed-price mechanisms are the best choice in the literature [HR87, McA08, CBGK⁺17, BCWZ17]. In fixed-price mechanisms, the mechanism designer picks a price $p$ (depends on the distributions of two agents, possibly) and gives it to both of the buyer and the seller. In the randomized case, one can pick the price drawn from some distribution. If the price is between the values of two agents (i.e., $S\leq p\leq B$ ), the trade happens. It is easy to see that fixed-price mechanisms are dominant-strategy incentive-compatible (DSIC). A recent research line tries to prove the near-optimal guarantees of such mechanisms. Our paper improves approximation ratios in variant settings for this problem.

1.1 Related Work

Forty years ago, Myerson and Satterthwaite [MS83] initiated the study of the optimal incentive-compatible mechanisms in bilateral trades. In [HR87], Hagerty and Rogerson showed that fixed-price mechanisms are the unique choice of strong budget balanced and dominant-strategy truthful mechanisms in bilateral trades, essentially. By relaxing the budget balance condition to a no-deficit condition, fixed-price mechanisms can be optimal due to [DK15, SZ16].

Recently, a research line pursued near-optimal guarantees of fixed-price mechanisms in bilateral trades w.r.t. the welfare. Blumrosen and Dobzinski [BD14] considered the Median Mechanism which sets a price equals to the median of the distribution of the seller and showed that the approximation ratio is $0.5$ . Blumrosen and Dobzinski [BD21] also showed that given the distribution of either the seller or the buyer, there is a price distribution such that the randomized fixed-price mechanism in expectation achieves at least $1-1/e\approx 0.63$ of the optimal efficiency. It implies that for every pair of the seller and the buyer distributions, there exists a deterministic fixed-price mechanism that achieves at least $1-1/e\approx 0.63$ of the optimal efficiency. Recently, Kang, Pernice and Vondrák [KPV22] showed that in the general setting, the approximation ratio can be greater than $1-1/e+0.0001$ , beating the previous work. Their method is choosing the better one between two mechanisms depending on whether the asymmetry between two agents’ distributions is severe or not. In the same paper, they also provided the tight ratio $(2+\sqrt{2})/4$ for the symmetric setting. On the other side, [CBKLT16] gave an example of the seller and the buyer distributions where no fixed-price mechanism can achieve $0.7485$ of the optimal efficiency. This impossibility result is improved to $0.7385$ by [KV18].

Another setting captures the case where we can only obtain the minimum-possible amount of the prior information from the distributions. For the general setting, [DFL⁺21] provided a $1/2$ -approximation analysis by using the single sample from the seller distribution as the price. For the symmetric setting, Kang, Pernice and Vondrák [KPV22] showed that a $3/4$ -approximation to the welfare can be obtained.

Another notion of characterizing the performance of mechanisms in bilateral trades is gain from trade (GFT), i.e., the expected social utility attained from the trading. Very recently, [DMSW22] and [Fei22] proved that a combination of simple mechanisms (RandOff) achieves the constant approximation of the first-best, and the state-of-the-art ratio is $1/3.15$ . Obtaining the exact ratio is a well-known open problem. On the hardness side, [BDK21] and [CGMZ21] independently showed that there exist instances that RandOff cannot achieve half to the optimal GFT. Besides, [LLR89] and [BM16] proved that no BIC, IR mechanisms can obtain better approximation than $2/e$ to the optimal GFT.

Independent Work.

Very recently, Cai and Wu [CW23] found that the infinite dimensional quadratically constrained quadratic program (QCQP) can characterize the worst-case instance and the approximation ratio is determined by such an instance. They used a finite program to get a lower bound of $0.72$ and a upper bound of $0.7381$ numerically, respectively. It is worth noting that solving the general case of QCQP is an NP-hard problem. Compared with their method, our algorithm is FPTAS. Thus, to approach the tight bound numerically, our method may be more efficient.

1.2 Our Results

In this paper, we reduce gaps mentioned in [KPV22] as shown in Table 1:

1.

For any distribution of the buyer, there is a distribution of prices such that the randomized fixed-price mechanism in expectation achieves $0.71$ approximation of the optimal efficiency. The main tools we use are interesting characterizations of this price distribution (See Section 3.1). Moreover, we characterize the extreme distribution of the buyer where the tight bound can be achieved. We also provide an example where no randomized fixed-price mechanism can achieve $0.7381$ approximation. We show that the same approximation ratio holds for the asymmetric setting. Thus, a direct corollary is that for every pair of buyer and seller distributions, there is a fixed-price mechanism that achieves $0.71$ approximation of the optimal efficiency, improving the previous $(1-1/e+0.0001)$ -approximation.
2.

For the general bilateral trade using a single sample from the seller distribution as the sole information, we show that even for the randomized fixed-price mechanisms, it is impossible to achieve $1/2$ -approximation. Together with the previous work [DFL⁺21], the approximation ratio $1/2$ is tight in this setting. In addition, we show that any randomized fixed-price mechanism using a sample as information cannot attain an approximation better than $3/4$ . in the symmetric setting. Together with the previous work [KPV22], the ratio $3/4$ is also tight.

Variant	Approximation
Asymmetric, full knowledge	${\color[rgb]{1,0,1}[0.71,0.7381]}$
Asymmetric, buyer’s knowledge	${\color[rgb]{1,0,1}[0.71,0.7381]}$
Symmetric, full knowledge	$(2+\sqrt{2})/4^{*}$ [KPV22]
Asymmetric, 1 prior sample from seller	${\color[rgb]{1,0,1}1/2}^{*}$ (also see [DFL⁺21])
Symmetric, 1 prior sample	${\color[rgb]{1,0,1}3/4}^{*}$ (also see [KPV22])

Table 1: A Survey of fixed-price mechanism approximations in bilateral trades w.r.t welfare maximization. Following [KPV22], we also highlight our results in magenta, and mark a

*

for all the tight results. For cases with 1 prior sample, we get tight results by studying randomized mechanisms.

2 Preliminaries

In the bilateral trade, a buyer and a seller trade an indivisible good. They have independent values to the good, $b$ for the buyer and $s$ for the seller. The specific value are unknown to the mechanism designer. We assume that their values are drawn from public distributions $F_{B}$ and $F_{S}$ , i.e., $b\sim F_{B}$ and $s\sim F_{S}$ . The expected gain from trade achieved by using fixed price $p$ can be represented by

		$\displaystyle\mathbb{E}_{B,S}[(b-s)\cdot\mathbf{1}_{b\geq p\geq s}]$
	$\displaystyle=$	$\displaystyle\mathbb{E}_{B,S}[(b-p+p-s)\cdot\mathbf{1}_{b\geq p\geq s}]$
	$\displaystyle=$	$\displaystyle\Pr(s\leq p)\mathbb{E}_{B}[(b-p)\cdot\mathbf{1}_{b\geq p}]+\Pr(b\geq p)\mathbb{E}_{S}[(p-s)\cdot\mathbf{1}_{p\geq s}]$
	$\displaystyle\geq$	$\displaystyle F_{S}(p)\mathbb{E}_{B}[(b-p)\cdot\mathbf{1}_{b\geq p}]+(1-F_{B}(p))\mathbb{E}_{S}[(p-s)\cdot\mathbf{1}_{p\geq s}]$
	$\displaystyle=$	$\displaystyle F_{S}(p)\int_{p}^{\infty}\left(1-F_{B}(b)\right)\mathrm{d}b+(1-F_{B}(p))\mathbb{E}_{S}[(p-s)\cdot\mathbf{1}_{p\geq s}]$
	$\displaystyle=$	$\displaystyle\mathbb{E}_{S}\left[\left(\int_{p}^{\infty}(1-F_{B}(b))\mathrm{d}b+(1-F_{B}(p))(p-s)\right)\cdot\mathbf{1}_{p\geq s}\right].$

The inequality is due to that we ignore the case where the buyer’s value is exactly the price. When the buyer distribution is continuous, the inequality becomes an equality. The welfare can be separated into the sum of the seller’s value of the good and the gain from trade. Thus, We define the expected welfare $\textrm{W}(p;F_{S},F_{B}):=\mathbb{E}_{S}[s]+\mathbb{E}_{B,S}[(b-s)\cdot\mathbf{1}_{b\geq p\geq s}]$ . We also let $W_{1}(p;F_{S},F_{B})$ denote the expression:

\mathbb{E}_{S}\left[s+\left(\int_{p}^{\infty}(1-F_{B}(b))\mathrm{d}b+(1-F_{B}(p))(p-s)\right)\cdot\mathbf{1}_{p\geq s}\right].

We denote by $\textrm{OPT-W}(F_{S},F_{B})$ the first-best optimal welfare, that is $\max\{B,S\}$ . We can also rewrite it as:

	$\displaystyle\textrm{OPT-W}(F_{S},F_{B})$	$\displaystyle=\mathbb{E}_{S}[s]+\mathbb{E}_{B,S}[(b-s)\cdot\mathbf{1}_{b\geq s}]$
		$\displaystyle=\mathbb{E}_{S}[s]+\mathbb{E}_{S}[\mathbb{E}_{B}[(b-s)\cdot\mathbf{1}_{b\geq s}]]$
		$\displaystyle=\mathbb{E}_{S}\left[s+\int^{\infty}_{s}(1-F_{B}(b))\mathrm{d}b\right].$

If the distributions $F_{S}$ and $F_{B}$ are identical, we use $F$ instead and rewrite $\textrm{W}(p;F_{S},F_{B})$ and $\textrm{OPT-W}(F_{S},F_{B})$ as $\textrm{W}(p;F)$ and $\textrm{OPT-W}(F)$ , respectively.

In this paper, we consider the welfare approximation ratios of the optimal fixed-price mechanism,

\inf_{F_{B},F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{p\in\mathbb{R}_{+}}\frac{\mathrm{W}(p;F_{S},F_{B})}{\mathrm{OPT}\text{-}\mathrm{W}(F_{S},F_{B})},

where $\Delta_{L^{1}}(\mathbb{R}_{+})$ denotes the set of all the probability distributions over non-negative real numbers. Both $E_{B}[b]$ and $E_{S}[s]$ should be greater than 0. We are interested in the case where $\mathrm{OPT}\text{-}\mathrm{W}(F_{S},F_{B})$ is finite and it requires both $E_{B}[b]$ and $E_{S}[s]$ are finite. For any function $F_{B}$ , we can always construct a continuous function $\tilde{F}_{B}$ such that $\mathrm{OPT}\text{-}\mathrm{W}(F_{S},\tilde{F}_{B})$ can be arbitrarily close to $\mathrm{OPT}\text{-}\mathrm{W}(F_{S},F_{B})$ and

\sup_{p\in\mathbb{R}_{+}}\mathrm{W}(p,F_{S},F_{B})=\sup_{p\in\mathbb{R}_{+}}\mathrm{W}(p,F_{S},\tilde{F}_{B})=\sup_{p\in\mathbb{R}_{+}}\mathrm{W}_{1}(p,F_{S},\tilde{F}_{B}).

Therefore, we have

\inf_{F_{B},F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{p\in\mathbb{R}_{+}}\frac{\mathrm{W}(p;F_{S},F_{B})}{\mathrm{OPT}\text{-}\mathrm{W}(F_{S},F_{B})}=\inf_{F_{B},F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{p\in\mathbb{R}_{+}}\frac{\mathrm{W}_{1}(p;F_{S},F_{B})}{\mathrm{OPT}\text{-}\mathrm{W}(F_{S},F_{B})}.

3 Welfare Approximation in the General Case

In this section, we consider the general case. We first introduce the optimization problem to facilitate determining the approximation ratios. Then we will show some useful properties of our problem in Section 3.1. Using these properties, we characterize the extreme case where the tight bound can be achieved in Section 3.2. Finally we propose an algorithm to approximate the optimal solution and give numerical bound results in Section 3.3.

We note that

\sup_{p\in\mathbb{R}_{+}}\frac{\textrm{W}_{1}(p;F_{S},F_{B})}{\textrm{OPT-W}(F_{S},F_{B})}=\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\frac{\mathbb{E}_{p}[\textrm{W}_{1}(p;F_{S},F_{B})]}{\textrm{OPT-W}(F_{S},F_{B})}.

Furthermore, given a number $\beta$ , proving that $\beta$ is a lower bound of the approximation ratio is equivalent to proving that the following formula is always non-negative:

\displaystyle\inf_{F_{B},F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\left\{\mathbb{E}_{p}[\textrm{W}_{1}(p;F_{S},F_{B})]-\beta\cdot\textrm{OPT-W}(F_{S},F_{B})\right\}.

Using the specific form in Section 2, we have

		$\displaystyle\mathbb{E}_{p}[\textrm{W}_{1}(p;F_{S},F_{B})]-\beta\cdot\textrm{OPT-W}(F_{S},F_{B})$
	$\displaystyle=$	$\displaystyle\mathbb{E}_{p}\left[\mathbb{E}_{s}\left[s+\left(\int_{p}^{\infty}(1-F_{B}(b))\mathrm{d}b+(1-F_{B}(p))(p-s)\right)\cdot\mathbf{1}_{p\geq s}\right]\right]-\beta\cdot\mathbb{E}_{s}\left[s+\int^{\infty}_{s}(1-F_{B}(b))\mathrm{d}b\right]$
	$\displaystyle=$	$\displaystyle\mathbb{E}_{p,s}\left[(1-\beta)s+\left(\int_{p}^{\infty}(1-F_{B}(b))\mathrm{d}b+(1-F_{B}(p))(p-s)\right)\cdot\mathbf{1}_{p\geq s}-\beta\int^{\infty}_{s}(1-F_{B}(b))\mathrm{d}b\right].$

For convenience, we set $H_{B}(b):=1-F_{B}(b)$ and $G_{B}(b):=\int_{b}^{\infty}H_{B}(p)\mathrm{d}p$ . We have

		$\displaystyle\mathbb{E}_{p}[\textrm{W}_{1}(p;F_{S},F_{B})]-\beta\cdot\textrm{OPT-W}(F_{S},F_{B})$
	$\displaystyle=$	$\displaystyle\mathbb{E}_{p,s}\left[(1-\beta)s+\left(G_{B}(p)+H_{B}(p)(p-s)\right)\cdot\mathbf{1}_{p\geq s}-\beta G_{B}(s)\right].$

We also use $\Gamma(\beta,F_{B},F_{S},F_{P})$ to denote

\mathbb{E}_{p,s}\left[(1-\beta)s+\left(G_{B}(p)+H_{B}(p)(p-s)\right)\cdot\mathbf{1}_{p\geq s}-\beta G_{B}(s)\right].

Fixing $F_{B}$ and switching the order between $\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}$ and $\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}$ , we have

\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\Gamma(\beta,F_{B},F_{S},F_{P})\geq\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\Gamma(\beta,F_{B},F_{S},F_{P}).

(1)

The LHS and RHS of the above inequality correspond to the following two problems:

•

Given distributions $F_{S}$ and $F_{B}$ , at least how much can fixed-price mechanisms achieve the optimal welfare?
•

Given the distribution $F_{B}$ , for any randomized fixed-price mechanism that uses only the knowledge of the buyer distribution, at least how much can it achieve of the optimal welfare for any seller distribution?

Based on Inequality (1), if $\beta$ is a lower bound of the solution of the second problem, it also applies to the first problem. Additionally, we prove that approximation ratios of these two problems are indeed equal in Section 3.2. From now on, we are concerned with the second problem and deal with the RHS of Inequality (1). To prove $\beta$ is a lower bound, it is equivalent to show that given any $F_{B}\in\Delta_{L^{1}}(\mathbb{R}_{+})$ , there exists a price distribution $F_{P}$ such that the following inequality holds for any $s\in\mathbb{R}_{+}$ :

\displaystyle(1-\beta)s+\mathbb{E}_{p\sim F_{P}}[\left(G_{B}(p)+H_{B}(p)(p-s)\right)\cdot\mathbf{1}_{p\geq s}]-\beta G_{B}(s)\geq 0.

(2)

For a weakly increasing function $Q_{P}:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ with $Q_{P}(0)\geq 0$ , we introduce $\phi(s,H_{B},Q_{P})$ to denote the expression

(1-\beta)s+\int_{s}^{\infty}\left(G_{B}(p)+H_{B}(p)(p-s)\right)\mathrm{d}Q_{P}(p)-\beta G_{B}(s).

Given the buyer distribution $F_{B}$ , we consider the following optimization problem:

$\displaystyle\inf$	$\displaystyle~{}\lim_{p\to\infty}Q_{P}(p)$
s.t.	$\displaystyle~{}\phi(s,H_{B},Q_{P})\geq 0,\forall s\in\mathbb{R}_{+},$	(3)
	$\displaystyle~{}Q_{P}(p_{1})\leq Q_{P}(p_{2}),\forall p_{1},p_{2}\in\mathbb{R}_{+},p_{1}<p_{2}.$

We prove that the optimal solution actually exists in Theorem 3.1. Let $Q^{*}_{P}$ denote an optimal solution that achieves the optimal objective $\inf\lim_{p\to\infty}Q_{P}(p)$ . To prove $\beta$ is a lower bound of the approximation ratio, it is equivalent to show that $\lim_{p\to\infty}Q_{P}^{*}(p)\leq 1$ . Here is the idea. If $\lim_{p\to\infty}Q_{P}^{*}(p)\leq 1$ , we set $F_{P}(0)=Q_{P}^{*}(0)-\lim_{p\to\infty}Q_{P}^{*}(p)+1$ and $F_{P}(p)=Q_{P}^{*}(p)-Q_{P}^{*}(0)+F_{P}(0)$ for any $p\in\mathbb{R}_{+}$ . It indicates that $\lim_{p\to\infty}F_{P}(p)=1$ . The function $F_{P}$ is a cumulative distribution function and satisfies Inequality (2). If $\lim_{p\to\infty}Q_{P}^{*}(p)>1$ , there is no way to find a feasible cumulative distribution function $F_{P}$ .

3.1 The Properties of an Optimal Solution

We present some characterizations of an optimal solution $Q_{P}^{*}$ . Recall that we focus on how to design $Q_{P}$ to minimize the objective function while satisfying all constraints in Problem (3). We consider the coefficient concerned with $\mathrm{d}Q_{P}(p)$ and let $\psi(p,s)=G_{B}(p)+H_{B}(p)(p-s)$ and have that

\frac{\partial\psi(p,s)}{\partial p}=H_{B}^{\prime}(p)(p-s)\leq 0.

That is, the function $\psi(p,s)$ weakly decreases in terms of variable $p$ . We also know that $\psi(p,s)\geq 0$ for all $p\in[s,\infty)$ . For any $p_{1}<p_{2}$ and $s$ , $\mathrm{d}Q_{P}(p_{1})$ has a weakly larger positive weight than $\mathrm{d}Q_{P}(p_{2})$ . The idea is that we treat $\mathrm{d}Q_{P}(p)$ as resource and it is better to put resource on the locations with larger weight than that with smaller weight.

We define $s_{2}$ as the unique solution to the equation $(1-\beta)s_{2}=\beta G_{B}(s_{2})$ . We provide the form of an optimal solution directly.

Theorem 3.1.

Given $F_{B}$ , an optimal solution $Q_{P}^{*}$ satisfies that

•

if $s\leq s_{2}$ , the closed form of its derivative function $q_{P}^{*}(s)$ is

\beta\left(\frac{H_{B}(s)}{G_{B}(s)}-\frac{\int_{s}^{s_{2}}H_{B}(t)^{2}\mathrm{d}t}{G_{B}(s)^{2}}\right)+\left(1-\beta\right)\cdot\frac{G_{B}(s_{2})}{G_{B}(s)^{2}};

•

if $s>s_{2}$ , the equation $Q_{P}^{*}(s)=Q_{P}^{*}(s_{2})$ holds.

Note that $Q_{P}^{*}$ is continuous and it is differentiable in $[0,s_{2}]$ . We first show that $Q_{P}^{*}$ satisfies constraints of Problem (3).

Proposition 3.2.

The function $Q_{P}^{*}$ in Theorem 3.1 satisfies:

•

For any $s\leq s_{2}$ , it holds that $\phi(s,H_{B},Q_{P}^{*})=0$ .
•

For any $s>s_{2}$ , it holds that $\phi(s,H_{B},Q_{P}^{*})>0$ .
•

For any $p_{1},p_{2}\in\mathbb{R}_{+}$ and $p_{1}<p_{2}$ , it holds that $Q_{P}^{*}(p_{1})\leq Q_{P}^{*}(p_{2})$ .

Proof.

Given any $s\leq s_{2}$ , we rewrite $\int_{s}^{s_{2}}H_{B}(p)q_{P}^{*}(p)\mathrm{d}p$ as:

		$\displaystyle\int_{s}^{s_{2}}H_{B}(p)\left[\beta\left(\frac{H_{B}(p)}{G_{B}(p)}-\frac{\int_{p}^{s_{2}}H_{B}(t)^{2}\mathrm{d}t}{G_{B}(p)^{2}}\right)+\left(1-\beta\right)\cdot\frac{G_{B}(s_{2})}{G_{B}(p)^{2}}\right]\mathrm{d}p$
	$\displaystyle=$	$\displaystyle\frac{1}{G_{B}(s)}\cdot\left[\beta\int_{s}^{s_{2}}H_{B}(t)^{2}\mathrm{d}t+(1-\beta)\int_{s}^{s_{2}}H_{B}(t)\mathrm{d}t\right].$

Therefore, we get

G_{B}(s)\int_{s}^{s_{2}}H_{B}(p)q_{P}^{*}(p)\mathrm{d}p=\beta\int_{s}^{s_{2}}H_{B}(t)^{2}\mathrm{d}t+(1-\beta)\int_{s}^{s_{2}}H_{B}(t)\mathrm{d}t.

Next, we calculate the derivative of the above formula about $s$ and get

H_{B}(s)\int_{s}^{s_{2}}H_{B}(p)q_{P}^{*}(p)\mathrm{d}p+G_{B}(s)H_{B}(s)q_{P}^{*}(s)=\beta H_{B}(s)^{2}+(1-\beta)H_{B}(s).

We know that $G_{B}(s_{2})=\frac{(1-\beta)s_{2}}{\beta}>0$ . It indicates that $H_{B}(s)>0$ for any $s\leq s_{2}$ . Thus, we divide every term by $H_{B}(s)$ and get

(1-\beta)-\int_{s}^{s_{2}}H_{B}(p)q_{P}^{*}(p)\mathrm{d}p\\ -G_{B}(s)q_{P}^{*}(s)+\beta H_{B}(s)=0.

Notice that the equation $Q_{P}^{*}(s)=Q_{P}^{*}(s_{2})$ holds if $s>s_{2}$ . It means that $\int_{s_{2}}^{\infty}H_{B}(p)\mathrm{d}Q_{P}^{*}(p)=0$ . Therefore, we plug $\int_{s_{2}}^{\infty}H_{B}(p)\mathrm{d}Q_{P}^{*}(p)$ into the above equation and get

(1-\beta)-\int_{s}^{\infty}H_{B}(p)\mathrm{d}Q_{P}^{*}(p)-G_{B}(s)q_{P}^{*}(s)+\beta H_{B}(s)=0.

We consider the integral. Note that $(1-\beta)s_{2}=\beta G_{B}(s_{2})$ . We have

(1-\beta)s+\int_{s}^{\infty}[G_{B}(p)+H_{B}(p)(p-s)]\mathrm{d}Q_{P}^{*}(p)-\beta G_{B}(s)=0.

We finish the proof of the first statement that $\phi(s,H_{B},Q_{P}^{*})=0$ for any $s\leq s_{2}$ .

For the second statement, we have $\phi(s,H_{B},Q_{P}^{*})=(1-\beta)s-\beta G_{B}(s)$ for any $s>s_{2}$ since $Q_{P}^{*}(s)=Q_{P}^{*}(s_{2})$ . Considering the derivative about $s$ and we have $\phi^{\prime}(s,H_{B},Q_{P}^{*})=1-\beta+\beta H_{B}(s)>0$ . We know that $\phi(s_{2},H_{B},Q_{P}^{*})=0$ . Therefore, we finish the proof that $\phi(s,H_{B},Q_{P}^{*})>0$ for any $s>s_{2}$ .

For the third statement, if $s\leq s_{2}$ , the derivative function $q_{P}^{*}(s)>0$ . And if $s>s_{2}$ , the equation $Q_{P}^{*}(s)=Q_{P}^{*}(s_{2})$ holds. The function $Q_{P}^{*}$ is non-decreasing. Thus, it holds that $Q_{P}^{*}(p_{1})\leq Q_{P}^{*}(p_{2})$ for any $p_{1},p_{2}\in\mathbb{R}_{+}$ and $p_{1}<p_{2}$ .

To summarize, the function $Q_{P}^{*}$ satisfies allconstraints of Problem (3).∎

Next, we present that for any $\hat{Q}_{P}$ satisfying constraints of Problem (3), it holds that $\lim_{p\to\infty}\hat{Q}_{P}(p)\geq\lim_{p\to\infty}Q_{P}^{*}(p)$ . Therefore, $Q_{P}^{*}$ is an optimal solution.

Proof of Theorem 3.1.

From Proposition 3.2, we notice that $\phi(s,H_{B},Q_{P}^{*})=0$ for any $s\leq s_{2}$ . Therefore, for any $\hat{Q}_{P}$ satisfying constraints of Problem (3), we have

\phi(s,H_{B},Q_{P}^{*})\leq\phi(s,H_{B},\hat{Q}_{P}),\forall s\leq s_{2}.

(4)

Let $\theta(s):=G_{B}(0)\cdot\left[-H_{B}(s)\int_{0}^{s}\frac{1}{G_{B}(t)^{2}}\mathrm{d}t+\frac{1}{G_{B}(s)}\right].$ Note that $\theta^{\prime}(s)=-G_{B}(0)H_{B}^{\prime}(s)\int_{0}^{s}\frac{1}{G_{B}(t)^{2}}\mathrm{d}t\geq 0$ . We define the function

\xi(H_{B},Q_{P}):=\int_{0}^{\infty}\psi(p,0)\mathrm{d}Q_{P}(p)+\int_{0}^{s_{2}}\int_{s}^{\infty}\psi(p,s)\mathrm{d}Q_{P}(p)\mathrm{d}\theta(s).

We know that $\xi(H_{B},Q_{P}^{*})\leq\xi(H_{B},\hat{Q}_{P})$ by Inequality (4). Next, we rewrite $\xi(H_{B},Q_{P})$ as:

		$\displaystyle\int_{0}^{s_{2}}\theta(p)G_{B}(p)\mathrm{d}Q_{P}(p)+\int_{0}^{s_{2}}H_{B}(p)\int_{0}^{p}\theta(s)\mathrm{d}s\mathrm{d}Q_{P}(p)$
	$\displaystyle+$	$\displaystyle\theta(s_{2})\int_{s_{2}}^{\infty}\psi(p,s_{2})\mathrm{d}Q_{P}(p)+\int_{s_{2}}^{\infty}H_{B}(p)\int_{0}^{s_{2}}\theta(s)\mathrm{d}s\mathrm{d}Q_{P}(p).$

The function $\xi(H_{B},Q_{P})$ can be represented by $\int_{0}^{s_{2}}\tau_{1}(p)\mathrm{d}Q_{P}(p)+\int_{s_{2}}^{\infty}\tau_{2}(p)\mathrm{d}Q_{P}(p)$ . Note that $\int_{0}^{p}\theta(s)\mathrm{d}s=G_{B}(0)G_{B}(p)\int_{0}^{p}\frac{1}{G_{B}(t)^{2}}\mathrm{d}t$ , hence we have that

\tau_{1}(p)=\theta(p)G_{B}(p)+H_{B}(p)\int_{0}^{p}\theta(s)\mathrm{d}s=G_{B}(0).

As for $\tau_{2}(p)$ , we have

\tau_{2}(p)=\theta(s_{2})\psi(p,s_{2})+H_{B}(p)\int_{0}^{s_{2}}\theta(s)\mathrm{d}s.

The derivative $\tau_{2}^{\prime}(p)=H_{B}^{\prime}(p)[\theta(s_{2})(p-s_{2})+\int_{0}^{s_{2}}\theta(s)\mathrm{d}s]\leq 0$ for any $p\geq s_{2}$ . Thus, we have $\tau_{2}(p)\leq\tau_{2}(s_{2})=G_{B}(0)$ .

Consequently, we have

		$\displaystyle\int_{0}^{\infty}G_{B}(0)\mathrm{d}\hat{Q}_{P}(p)$
	$\displaystyle\geq$	$\displaystyle\int_{0}^{s_{2}}G_{B}(0)\mathrm{d}\hat{Q}_{P}(p)+\int_{s_{2}}^{\infty}\tau_{2}(p)\mathrm{d}\hat{Q}_{P}(p)$
	$\displaystyle\geq$	$\displaystyle\int_{0}^{s_{2}}G_{B}(0)\mathrm{d}Q_{P}^{}(p)+\int_{s_{2}}^{\infty}\tau_{2}(p)\mathrm{d}Q_{P}^{}(p)$
	$\displaystyle=$	$\displaystyle\int_{0}^{\infty}G_{B}(0)\mathrm{d}Q_{P}^{*}(p).$

The second step is because that $\xi(H_{B},Q_{P}^{*})\leq\xi(H_{B},\hat{Q}_{P})$ . The last step is because that $Q_{P}^{*}(s)=Q_{P}^{*}(s_{2})$ for any $s>s_{2}$ . Finally, we have $\lim_{p\to\infty}\hat{Q}_{P}(p)\geq\lim_{p\to\infty}Q_{P}^{*}(p)$ . ∎

3.2 The Bound of the Approximation Ratio

Recall that $\beta$ is an lower bound if and only if $\lim_{p\to\infty}Q_{P}^{*}(p)\leq 1$ . Considering properties of $Q_{P}^{*}$ in Theorem 3.1, we use the result below to figure out the lower bound of the exact approximation ratio.

Theorem 3.3.

Given $\beta>0$ , $\beta$ is a lower bound of the approximation ratio if and only if for any $F_{B}\in\Delta_{L^{1}}(\mathbb{R_{+}})$ , it satisfies that

\int^{s_{2}}_{0}\left[\beta\left(\frac{H_{B}(s)}{G_{B}(s)}-\frac{\int^{s_{2}}_{s}H_{B}(t)^{2}\mathrm{d}t}{G_{B}(s)^{2}}\right)+\left(1-\beta\right)\frac{G_{B}(s_{2})}{G_{B}(s)^{2}}\right]\mathrm{d}s\leq 1.

Since both $G_{B}(s)$ and $\int^{s_{2}}_{s}H_{B}(t)^{2}\mathrm{d}t$ can be expressed by the function $H_{B}$ . Therefore, the objective above is only determined by $H_{B}$ . It is easy to see that the function $H_{B}$ is scale free in terms of the variable $s$ , that is, $\hat{H}_{B}(s)=H_{B}(\sigma s)$ for $\sigma>0$ achieving the same objective. WLOG we assume that $s_{2}=1$ and search all possible functions $H_{B}\in\Delta_{L^{1}}[0,1]$ which are weakly decreasing to maximize the objective $\mathrm{obj}(H_{B})$ :

\int^{1}_{0}\left[\beta\left(\frac{H_{B}(s)}{G_{B}(s)}-\frac{\int^{1}_{s}H_{B}(t)^{2}\mathrm{d}t}{G_{B}(s)^{2}}\right)+\left(1-\beta\right)\frac{G_{B}(1)}{G_{B}(s)^{2}}\right]\mathrm{d}s,

where $(1-\beta)\cdot 1=\beta\cdot G_{B}(1)$ . That is $G_{B}(1)=\frac{1-\beta}{\beta}$ .

We know that $1\geq H_{B}(0)\geq H_{B}(1)>0$ , in which $H_{B}(1)>0$ is due to $G_{B}(1)>0$ . However, we allow that $H_{B}(1)$ equals zero by considering the extreme case that there is a very large number with a very low probability in the buyer distribution. Assuming that $H_{B}^{*}$ is the optimal solution and setting $z_{1}:=\sup\{z|H_{B}^{*}(z)=1\}$ and $z_{2}:=\inf\{z|H_{B}^{*}(z)=0\}$ , we present the characterization of $H_{B}^{*}$ .

Theorem 3.4.

The optimal function $H_{B}^{*}$ achieving the maximum of the objective $\mathrm{obj}(H_{B})$ satisfies that, for any $z\in[z_{1},z_{2}]$ , we have

{H_{B}^{*}}^{\prime}(z)=\frac{\int^{z_{2}}_{z}H_{B}^{*}(t)^{2}\mathrm{d}t-H_{B}^{*}(z)G_{B}^{*}(z)-G_{B}(1)^{2}}{G_{B}^{*}(z)^{3}\int^{z}_{0}\frac{1}{G_{B}^{*}(t)^{2}}\mathrm{d}t}.

Proof.

To the begin with, we relax the constraint that $H_{B}^{*}$ is weakly decreasing on the interval $[z_{1},z_{2}]$ . Therefore, we treat the optimization problem as a variational problem. We use $H_{B}(z)=H_{B}^{*}(z)+\epsilon\eta(z)$ to denote an arbitrary function defined on $[z_{1},z_{2}]$ . Note that $H_{B}\in\Delta_{L^{1}}[z_{1},z_{2}]$ does not affect the integral $\int_{z_{2}}^{1}q_{P}^{*}(z)\mathrm{d}z$ . Thus, we define

I(H_{B})=\int^{z_{2}}_{0}\left[\beta\left(\frac{H_{B}(z)}{G_{B}(z)}-\frac{\int^{1}_{z}H_{B}(t)^{2}\mathrm{d}t}{G_{B}(z)^{2}}\right)+\left(1-\beta\right)\frac{G_{B}(1)}{G_{B}(z)^{2}}\right]\mathrm{d}z.

Considering $\frac{\partial I}{\partial\epsilon}\bigg{|}_{\epsilon=0}$ , we have

	$\displaystyle\int^{z_{2}}_{z_{1}}\bigg{[}$	$\displaystyle\frac{\beta}{G_{B}^{}(z)}-\int^{z}_{0}\frac{\beta H_{B}^{}(s)}{G_{B}^{}(s)^{2}}\mathrm{d}s-\int^{z}_{0}\frac{2\beta H_{B}^{}(z)}{G_{B}^{*}(s)^{2}}\mathrm{d}s$
	$\displaystyle-$	$\displaystyle\int^{z}_{0}\left(-\beta\int^{z_{2}}_{s}H_{B}^{}(t)^{2}\mathrm{d}t+(1-\beta)G_{B}(1)\right)\cdot\frac{2}{G_{B}^{}(s)^{3}}\mathrm{d}s\bigg{]}\eta(z)\mathrm{d}z.$

By the first order condition, we have $\frac{\partial I}{\partial\epsilon}\bigg{|}_{\epsilon=0}=0$ . Notice that $\eta(z)$ can be arbitrary. Therefore, the coefficient of $\eta(z)$ should be always zero, so we have that

\frac{1}{G_{B}^{*}(z)}=\int^{z}_{0}\left[\frac{H_{B}^{*}(s)}{G_{B}^{*}(s)^{2}}+\frac{2H_{B}^{*}(z)}{G_{B}^{*}(s)^{2}}+\frac{2G_{B}(1)^{2}-2\int^{z_{2}}_{s}H_{B}^{*}(t)^{2}\mathrm{d}t}{G_{B}^{*}(s)^{3}}\right]\mathrm{d}s.

We calculate the derivative and have

{H_{B}^{*}}^{\prime}(z)=\frac{\int^{z_{2}}_{z}H_{B}^{*}(t)^{2}\mathrm{d}t-H_{B}^{*}(z)G_{B}^{*}(z)-G_{B}(1)^{2}}{G_{B}^{*}(z)^{3}\int^{z}_{0}\frac{1}{G_{B}^{*}(t)^{2}}\mathrm{d}t}.

Next, we demonstrate that ${H_{B}^{*}}^{\prime}(z)<0$ , that is, the function $H_{B}^{*}$ satisfies the decreasing constraint naturally. It implies that $H_{B}^{*}$ is actually the optimal solution that achieves the maximum of the objective $\mathrm{obj}(H_{B})$ . We prove that ${H_{B}^{*}}^{\prime}(z)<0$ by contradiction. Suppose that $z_{3}=\sup\{z|{H_{B}^{*}}^{\prime}(z)\geq 0\}$ . It indicates that ${H_{B}^{*}}^{\prime}(z)<0$ for any $z\in(z_{3},z_{2}]$ . For the numerator, given a sufficient small $\delta>0$ , we consider

	$\displaystyle\int^{z_{2}}_{z_{3}}H_{B}^{}(t)^{2}\mathrm{d}t-H_{B}^{}(z_{3})G_{B}^{*}(z_{3})-G_{B}(1)^{2},$
	$\displaystyle\int^{z_{2}}_{z_{3}+\delta}H_{B}^{}(t)^{2}\mathrm{d}t-H_{B}^{}(z_{3}+\delta)G_{B}^{*}(z_{3}+\delta)-G_{B}(1)^{2}.$

We know that $H_{B}^{*}(z_{3})=H_{B}^{*}(z_{3}+\delta)-\delta{H_{B}^{*}}^{\prime}(z_{3}+\delta)$ . Take the difference of above formulas into account. We have

		$\displaystyle\delta{H_{B}^{}}^{\prime}(z_{3}+\delta)G_{B}^{}(z_{3})-\int^{z_{3}+\delta}_{z_{3}}H_{B}^{}(t)\left(H_{B}^{}(t)-H_{B}^{*}(z_{3}+\delta)\right)\mathrm{d}t$
	$\displaystyle<$	$\displaystyle\delta{H_{B}^{}}^{\prime}(z_{3}+\delta)G_{B}^{}(z_{3})-\delta^{2}H_{B}^{}(z_{3}){H_{B}^{}}^{\prime}(z_{3}+\delta)$
	$\displaystyle=$	$\displaystyle\delta{H_{B}^{}}^{\prime}(z_{3}+\delta)\left(G_{B}^{}(z_{3})-\delta H_{B}^{*}(z_{3})\right)$

Note that ${H_{B}^{*}}^{\prime}(z_{3}+\delta)<0$ . Thus, the difference is less than 0. We derive that ${H_{B}^{*}}^{\prime}(z_{3})<0$ , which contradicts with the assumption that ${H_{B}^{*}}^{\prime}(z_{3})\geq 0$ . ∎

Remark.

Although we get the structure of $H_{B}^{*}$ , it is hard to figure out the expression of $H_{B}^{*}$ explicitly. Therefore, we choose the numerical method to get the lower bound later.

In addition, suppose that $\hat{\beta}$ is the approximation ratio only using the knowledge of buyer distribution. We prove that $\hat{\beta}$ is also the approximation ratio with full knowledge of buyer and seller distributions. We have the following theorem:

Theorem 3.5.

The randomized fixed-price mechanism that only uses the knowledge of $F_{B}$ has the same approximation ratio as the fixed-price mechanism that uses both $F_{B}$ and $F_{S}$ . Additionally, for the worst pair $(\hat{F}_{B},\hat{F}_{S})$ , we have

\hat{F}_{S}(p)=G_{B}(1)\left[-\hat{H}_{B}(p)\int_{0}^{p}\frac{1}{\hat{G}_{B}(s)^{2}}\mathrm{d}s+\frac{1}{\hat{G}_{B}(p)}\right].

It means that given $\hat{F}_{B}$ , the following equality holds

\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\Gamma(\hat{\beta},\hat{F}_{B},F_{S},F_{P})=\sup_{F_{P}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\Gamma(\hat{\beta},\hat{F}_{B},F_{S},F_{P}).

The proof idea is that we can find a seller’s distribution such that $\textrm{W}_{1}(p;F_{S},\hat{F}_{B})-\hat{\beta}\cdot\textrm{OPT-W}(F_{S},\hat{F}_{B})$ is identical for any price $p\in[0,1]$ . And the seller’s distribution is exactly $\hat{F}_{S}$ .

Proof.

First, we show that gain from trade $\textrm{GFT}(p;\hat{F}_{S},\hat{F}_{B})$ is identical for all $p\in[0,1]$ . We have

	$\displaystyle\hat{F}_{S}(p)=$	$\displaystyle\hat{G}_{B}(1)\left[-\hat{H}_{B}(p)\int_{0}^{p}\frac{1}{\hat{G}_{B}(s)^{2}}\mathrm{d}s+\frac{1}{\hat{G}_{B}(p)}\right]$
	$\displaystyle=$	$\displaystyle\left(\hat{G}_{B}(p)\int_{0}^{p}\frac{\hat{G}_{B}(1)}{\hat{G}_{B}(s)^{2}}\mathrm{d}s\right)^{\prime}.$

Thus, we have

\frac{\int_{0}^{p}\hat{F}_{S}(s)\mathrm{d}s}{\hat{G}_{B}(p)}=\int_{0}^{p}\frac{\hat{G}_{B}(1)}{\hat{G}_{B}(s)^{2}}\mathrm{d}s.

We calculate the derivative and get

\hat{F}_{S}(p)\hat{G}_{B}(p)+\hat{H}_{B}(p)\int_{0}^{p}\hat{F}_{S}(s)\mathrm{d}s=\hat{G}_{B}(1).

We rewrite $\textrm{GFT}(p;\hat{F}_{S},\hat{F}_{B})$ as:

		$\displaystyle\mathbb{E}_{B,S}[(b-s)\cdot\mathbf{1}_{b\geq p\geq s}]$
	$\displaystyle=$	$\displaystyle\Pr(s\leq p)\mathbb{E}_{B}[(b-p)\cdot\mathbf{1}_{b\geq p}]+\Pr(b\geq p)\mathbb{E}_{S}[(p-s)\cdot\mathbf{1}_{p\geq s}]$
	$\displaystyle=$	$\displaystyle\hat{F}_{S}(p)\int_{p}^{\infty}\left(1-\hat{F}_{B}(b)\right)\mathrm{d}b+(1-\hat{F}_{B}(p))\int_{0}^{p}\hat{F}_{S}(s)\mathrm{d}s$
	$\displaystyle=$	$\displaystyle\hat{F}_{S}(p)\hat{G}_{B}(p)+\hat{H}_{B}(p)\int_{0}^{p}\hat{F}_{S}(s)\mathrm{d}s.$

Therefore, for the worst pair $(\hat{F}_{S},\hat{F}_{B})$ , gain from trade is a constant for any $p\in[0,1]$ . Furthermore, the following equality holds:

\textrm{W}_{1}(p;\hat{F}_{S},\hat{F}_{B})-\hat{\beta}\cdot\textrm{OPT-W}(\hat{F}_{S},\hat{F}_{B})=c.

(5)

Suppose that $\hat{F}_{P}$ is the optimal price mechanism. We have

\mathbb{E}_{p\sim\hat{F}_{P}}[\textrm{W}_{1}(p;\hat{F}_{S},\hat{F}_{B})]-\hat{\beta}\cdot\textrm{OPT-W}(\hat{F}_{S},\hat{F}_{B})=0.

It indicates that $c=0$ . We also have

		$\displaystyle\max_{p\in[0,1]}\left\{\textrm{W}_{1}(p;\hat{F}_{S},\hat{F}_{B})-\hat{\beta}\cdot\textrm{OPT-W}(\hat{F}_{S},\hat{F}_{B})\right\}$
	$\displaystyle\geq$	$\displaystyle\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\max_{p\in[0,1]}\left\{\textrm{W}_{1}(p;F_{S},\hat{F}_{B})-\hat{\beta}\cdot\textrm{OPT-W}(F_{S},\hat{F}_{B})\right\}$
	$\displaystyle=$	$\displaystyle\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{F_{P}\in\Delta_{L^{1}}[0,1]}\Gamma(\hat{\beta},\hat{F}_{B},F_{S},F_{P})$
	$\displaystyle\geq$	$\displaystyle\sup_{F_{P}\in\Delta_{L^{1}}[0,1]}\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\Gamma(\hat{\beta},\hat{F}_{B},F_{S},F_{P})$
	$\displaystyle=$	$\displaystyle\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\left\{\mathbb{E}_{p\sim\hat{F}_{P}}[\textrm{W}_{1}(p;F_{S},\hat{F}_{B})]-\hat{\beta}\cdot\textrm{OPT-W}(F_{S},\hat{F}_{B})\right\}$

By Equation (5), the first formula should be zero. Since $\hat{F}_{P}$ is the optimal price mechanism, the last formula is also zero. Consequently, we have

\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\sup_{F_{P}\in\Delta_{L^{1}}[0,1]}\Gamma(\hat{\beta},\hat{F}_{B},F_{S},F_{P})=\sup_{F_{P}\in\Delta_{L^{1}}[0,1]}\inf_{F_{S}\in\Delta_{L^{1}}(\mathbb{R}_{+})}\Gamma(\hat{\beta},\hat{F}_{B},F_{S},F_{P})\qed

3.3 Numerical results

Now we try to approach the lower bound by the methods of dicretization and dynamic programming. We show that there exists a step function $\hat{H}_{B}$ that approximates the objective of $H_{B}^{*}$ , where $\hat{H}_{B}$ weakly decreases at points over $\left\{0,\frac{1}{n},\ldots,\frac{n}{n}\right\}$ . Then, we can search the optimal step function $\hat{H}_{B}$ with $\epsilon$ granularity for any $s\in\left\{0,\frac{1}{n},\ldots,\frac{n}{n}\right\}$ to maximize $\mathrm{obj}(\hat{H}_{B})$ . Given $\beta$ , we define $M:=\max\mathrm{obj}(\hat{H}_{B})$ . After adding the discretization error to $M$ , if the result is less than $1$ , the corresponding $\beta$ could be a lower bound. As for the search algorithm in discrete grids, we use dynamic programming (see Algorithm 1). We first present the framework of the algorithm and discuss the concrete discretization error later. We denote by $Sol(x,y,z,s_{k})$ the objective value of the following problem:

	$\displaystyle\max$	$\displaystyle\int^{s_{k}}_{0}\left[\beta\left(\frac{\hat{H}_{B}(s)}{\hat{G}_{B}(s)}-\frac{\int^{1}_{s}\hat{H}_{B}(t)^{2}\mathrm{d}t}{\hat{G}_{B}(s)^{2}}\right)+\left(1-\beta\right)\frac{G_{B}(1)}{\hat{G}_{B}(s)^{2}}\right]\mathrm{d}s$
	s.t.	$\displaystyle\int_{s_{k}}^{1}\hat{H}_{B}(t)^{2}\mathrm{d}t=x,$
		$\displaystyle\int_{s_{k}}^{1}\hat{H}_{B}(t)\mathrm{d}t=y,$
		$\displaystyle\hat{H}_{B}(s_{k})=z.$

Note that $s_{k}$ is in the set of $\left\{0,\frac{1}{n},\ldots,1\right\}$ . Then, we show the original framework of the algorithm as follows.

Input:

\beta,n,\epsilon

Output:

M

set

s_{0}=0

and

k=0

;

Initialize

Sol(x,y,z,s_{k})

by an

\frac{n}{\epsilon^{2}}\times\frac{n}{\epsilon}\times\frac{1}{\epsilon}

tensor with zeros;

while $s_{k}<1$ do

s_{k+1}\leftarrow s_{k}+\frac{1}{n}

;

Initialize

Sol(x,y,z,s_{k+1})

by an

\frac{n}{\epsilon^{2}}\times\frac{n}{\epsilon}\times\frac{1}{\epsilon}

tensor with zeros;

foreach cell $\in Sol(x,y,z,s_{k})$ do

for $z^{\prime}=0:z$ do

x^{\prime}\leftarrow x-z^{\prime}\cdot z^{\prime}/n

;

y^{\prime}\leftarrow y-z^{\prime}/n

;

if $x^{\prime}\geq 0$ and $y^{\prime}\geq 0$ and $Sol(x,y,z,s_{k})+\int_{s_{k}}^{s_{k+1}}q_{P}(s)\mathrm{d}s>Sol(x^{\prime},y^{\prime},z^{\prime},s_{k+1})$ then

Sol(x^{\prime},y^{\prime},z^{\prime},s_{k+1})\leftarrow Sol(x,y,z,s_{k})+\int_{s_{k}}^{s_{k+1}}q_{P}(s)\mathrm{d}s

;

k\leftarrow k+1

;

M\leftarrow\max_{cell\in Sol(x,y,z,1)}cell

;

Algorithm 1 Framework of dynamic programming

Intuitively, the discretization error depends on both $\frac{1}{n}$ and $\epsilon$ . The complexity is $O\left(\frac{n^{3}}{\epsilon^{5}}\right)$ .

To reduce the time complexity, we first use the following two inequalities to eliminate some special cases directly:

	$\displaystyle(1-s)\int_{s}^{1}H_{B}(t)^{2}\mathrm{d}t$	$\displaystyle\geq\left(\int_{s}^{1}H_{B}(t)\mathrm{d}t\right)^{2},$
	$\displaystyle H_{B}(s)\int_{s}^{1}H_{B}(t)\mathrm{d}t$	$\displaystyle\geq\int_{s}^{1}H_{B}(t)^{2}\mathrm{d}t.$

Next, we construct a new function $K(\cdot)$ with $\frac{\epsilon}{n}$ granularity to approximate $\int_{s_{k}}^{1}\hat{H}_{B}(t)^{2}\mathrm{d}t$ . The time complexity can be reduced by $\frac{1}{\epsilon}$ times. We construct functions on grid points as follows:

	$\displaystyle\hat{H}_{B}\left(\frac{i}{n}\right)$	$\displaystyle=\left\lfloor H_{B}^{*}\left(\frac{i}{n}\right)\cdot\frac{1}{\epsilon}\right\rfloor\cdot\epsilon;$
	$\displaystyle K\left(\frac{i}{n}\right)$	$\displaystyle=\sum_{j=i+1}^{n}\left\lfloor H_{B}^{*}\left(\frac{j}{n}\right)^{2}\cdot\frac{1}{\epsilon}\right\rfloor\cdot\frac{\epsilon}{n};$
	$\displaystyle\hat{G}_{B}\left(\frac{i}{n}\right)$	$\displaystyle=\sum_{j=i+1}^{n}\hat{H}_{B}\left(\frac{j}{n}\right)\cdot\frac{1}{n}+G_{B}(1).$

For $s\in\left(\frac{i}{n},\frac{i+1}{n}\right)$ , we use the following continuous extensions:

	$\displaystyle\hat{H}_{B}(s)$	$\displaystyle=\hat{H}_{B}\left(\frac{i+1}{n}\right),$
	$\displaystyle K(s)$	$\displaystyle=K\left(\frac{i+1}{n}\right)+\left(\frac{i+1}{n}-s\right)\cdot\hat{H}_{B}\left(\frac{i+1}{n}\right)^{2},$
	$\displaystyle\hat{G}_{B}(s)$	$\displaystyle=\hat{G}_{B}\left(\frac{i}{n}\right)+\left(\frac{i+1}{n}-s\right)\cdot\hat{H}_{B}\left(\frac{i+1}{n}\right).$

Then, we define $\mathrm{obj}(\hat{H}_{B},K)$ as:

\mathrm{obj}(\hat{H}_{B},K)=\int^{1}_{0}\left[\beta\left(\frac{\hat{H}_{B}(s)}{\hat{G}_{B}(s)}-\frac{K(s)}{\hat{G}_{B}(s)^{2}}\right)+\left(1-\beta\right)\frac{G_{B}(1)}{\hat{G}_{B}(s)^{2}}\right]\mathrm{d}s.

We use $\mathrm{obj}(\hat{H}_{B},K)$ to approximate $\mathrm{obj}(H_{B}^{*})$ . Next, we analyze the discretization error.

Theorem 3.6.

For the discretization error, we have $\mathrm{obj}(H_{B}^{*})-\mathrm{obj}(\hat{H}_{B},K)\leq\beta\ln\frac{1-\beta}{1-\beta\left(1+\epsilon+\frac{1}{n}\right)}$ .

Proof.

First, we have

		$\displaystyle\mathrm{obj}(H_{B}^{*})-\mathrm{obj}(\hat{H}_{B},K)$
	$\displaystyle=$	$\displaystyle\underbrace{\beta\int_{0}^{1}\left(\frac{H_{B}^{}(s)}{G_{B}^{}(s)}-\frac{\hat{H}_{B}(s)}{\hat{G}_{B}(s)}\right)\mathrm{d}s}_{\gamma_{1}}+\underbrace{\beta\int_{0}^{1}\left(\frac{K(s)}{\hat{G}_{B}(s)^{2}}-\frac{\int^{1}_{s}H_{B}^{}(t)^{2}\mathrm{d}t}{G_{B}^{}(s)^{2}}\right)\mathrm{d}s}_{\gamma_{2}}$
		$\displaystyle+\underbrace{(1-\beta)G_{B}(1)\int_{0}^{1}\left(\frac{1}{G_{B}^{*}(s)^{2}}-\frac{1}{\hat{G}_{B}(s)^{2}}\right)\mathrm{d}s}_{\gamma_{3}}.$

Now we will upper bound three parts $\gamma_{1},\gamma_{2}$ and $\gamma_{3}$ in above equation respectively.

Note that functions $H_{B}^{*}$ and $\hat{H}_{B}$ are both decreasing functions. Therefore, we have

		$\displaystyle G_{B}^{*}(s)-\hat{G}_{B}(s)$
	$\displaystyle\leq$	$\displaystyle H_{B}^{}(s)\cdot\left(\frac{i+1}{n}-s\right)+\sum_{j=i+1}^{n-1}H_{B}^{}\left(\frac{j}{n}\right)\cdot\frac{1}{n}-\hat{H}_{B}\left(\frac{i+1}{n}\right)\cdot\left(\frac{i+1}{n}-s\right)-\sum_{j=i+2}^{n}\hat{H}_{B}\left(\frac{j}{n}\right)\cdot\frac{1}{n}$
	$\displaystyle\leq$	$\displaystyle\left(H_{B}^{}(s)-\left(H_{B}^{}\left(\frac{i+1}{n}\right)-\epsilon\right)\right)\cdot\left(\frac{i+1}{n}-s\right)+\sum_{j=i+1}^{n-1}\left(H_{B}^{}\left(\frac{j}{n}\right)-\left(H_{B}^{}\left(\frac{j}{n}\right)-\epsilon\right)\right)\cdot\frac{1}{n}$
	$\displaystyle\leq$	$\displaystyle\frac{1}{n}+\epsilon.$

For any $s\in\left(\frac{i}{n},\frac{i+1}{n}\right)$ , we have $\hat{H}_{B}(s)\leq H_{B}^{*}(s)$ . That is, we always have $\hat{G}_{B}(s)\leq G_{B}^{*}(s)$ and $K(s)\leq\int^{1}_{s}H_{B}^{*}(t)^{2}\mathrm{d}t$ . Therefore, we get $\gamma_{3}\leq 0$ directly.

We get that $\gamma_{2}$ is upper bounded by

		$\displaystyle\beta\int_{0}^{1}\left(\int^{1}_{s}H_{B}^{}(t)^{2}\mathrm{d}t\right)\cdot\left({\hat{G}_{B}(s)^{-2}}-{G_{B}^{}(s)^{-2}}\right)\mathrm{d}s$
	$\displaystyle\leq$	$\displaystyle\beta\int_{0}^{1}\left(H_{B}^{}(s)\int^{1}_{s}H_{B}^{}(t)\mathrm{d}t\right)\cdot\left({\left(\int^{1}_{s}H_{B}^{}(t)\mathrm{d}t+G_{B}(1)-\epsilon-\frac{1}{n}\right)^{-2}}-{\left(\int^{1}_{s}H_{B}^{}(t)\mathrm{d}t+G_{B}(1)\right)^{-2}}\right)\mathrm{d}s.$

Let $x:=\int^{1}_{s}H_{B}^{*}(t)\mathrm{d}t$ and $a:=G_{B}(1)-\epsilon-\frac{1}{n}$ . We get that $\gamma_{2}$ is upper bounded by

		$\displaystyle\beta\int_{0}^{G_{B}^{*}(0)-G_{B}(1)}\left(\frac{x}{(a+x)^{2}}-\frac{x}{(G_{B}(1)+x)^{2}}\right)\mathrm{d}x$
	$\displaystyle=$	$\displaystyle\beta\left(\ln(a+x)+\frac{a}{a+x}-\ln\left(G_{B}(1)+x\right)-\frac{G_{B}(1)}{G_{B}(1)+x}\right)\bigg{\|}_{0}^{G_{B}^{*}(0)-G_{B}(1)}.$

For $\gamma_{1}$ , we have

	$\displaystyle\gamma_{1}=$	$\displaystyle\beta\left(\ln\hat{G}_{B}(s)\bigg{\|}_{0}^{1}-\ln G_{B}^{*}(s)\bigg{\|}_{0}^{1}\right)$
	$\displaystyle=$	$\displaystyle\beta\left(\ln G_{B}^{*}(0)-\ln\hat{G}_{B}(0)\right)$
	$\displaystyle\leq$	$\displaystyle\beta\left(\ln G_{B}^{}(0)-\ln\left(G_{B}^{}(0)-\frac{1}{n}-\epsilon\right)\right).$

Hence, the part $\gamma_{1}+\gamma_{2}$ is upper bounded by

\beta\left(\ln G_{B}(1)-\ln a+\frac{a}{a+G_{B}^{*}(0)-G_{B}(1)}-\frac{G_{B}(1)}{G_{B}^{*}(0)}\right)\leq\beta\ln\frac{G_{B}(1)}{a}.

To summarize, the discretization error is $\beta\ln\frac{1-\beta}{1-\beta\left(1+\epsilon+\frac{1}{n}\right)}$ .∎

Consequently, we update $\tilde{Sol}(x,y,z,s_{k})$ as follows:

	$\displaystyle\max$	$\displaystyle\int^{s_{k}}_{0}\left[\beta\left(\frac{\hat{H}_{B}(s)}{\hat{G}_{B}(s)}-\frac{K(s)}{\hat{G}_{B}(s)^{2}}\right)+\left(1-\beta\right)\frac{G_{B}(1)}{\hat{G}_{B}(s)^{2}}\right]\mathrm{d}s$
	s.t.	$\displaystyle K(s_{k})=x,$
		$\displaystyle\int_{s_{k}}^{1}\hat{H}_{B}(t)\mathrm{d}t=y,$
		$\displaystyle\hat{H}_{B}(s_{k})=z.$

Therefore, we can run our algorithm with $O\left(\frac{n^{3}}{\epsilon^{4}}\right)$ complexity. Note that $x^{\prime}\leftarrow x-\left\lfloor\frac{z^{\prime}\cdot z^{\prime}}{\epsilon}\cdot\frac{\epsilon}{n}\right\rfloor$ in every step. We present the calculation of $\int_{s_{k}}^{s_{k+1}}q_{P}(s)\mathrm{d}s$ :

		$\displaystyle\int_{s_{k}}^{s_{k+1}}\frac{\beta\left(\hat{H}_{B}(s_{k+1})\hat{G}_{B}(s_{k+1})-K(s_{k+1})\right)+(1-\beta)G_{B}(1)}{(\hat{G}_{B}(s_{k+1})+(s_{k+1}-s)\hat{H}_{B}(s_{k+1}))^{2}}\mathrm{d}s$
	$\displaystyle=$	$\displaystyle\frac{\beta\left(\hat{H}_{B}(s_{k+1})\hat{G}_{B}(s_{k+1})-K(s_{k+1})\right)+(1-\beta)G_{B}(1)}{\hat{G}_{B}(s_{k+1})(\hat{G}_{B}(s_{k+1})+(s_{k+1}-s_{k})\hat{H}_{B}(s_{k+1}))}\cdot(s_{k+1}-s_{k}).$

Finally, we are fully prepared to solve the lower bound $\beta$ .

Theorem 3.7.

Given distribution $F_{B}$ , for randomized fixed-price mechanism that uses only the knowledge of the buyer distribution, the designer can achieve at least $0.71$ of the optimal welfare for any seller distribution $F_{S}$ . Given distributions $F_{S}$ and $F_{B}$ , the designer can always select a price that achieves at least $0.71$ of the optimal welfare.

Proof.

We implement the dynamic programming algorithm by Python 3.9, with parameters $\beta=0.71$ , $n=75$ and $\epsilon=\frac{1}{75}$ . We run our algorithm with a computing cloud node whose resource contains the Intel Gold 5218 and 128GB memory. Our program takes 552794s (about 6d). Finally, we get $M=0.9440$ . Besides, the discretization error is $0.0479$ by Theorem 3.6. Thus, we have that $\mathrm{obj}(H_{B}^{*})\leq 0.9919<1$ . That is, we find a lower bound $\beta=0.71$ . All codes can be found at our github repository. ∎

We also summarize lower bounds for different discretization factors in Table 2.

$\beta$	$n$	$\epsilon$	$M$	error	$\mathrm{obj}(H_{B}^{*})$	running time
$0.69$	$35$	$\frac{1}{35}$	$0.9056$	$0.0939$	$0.9995$	$4166$ s ( $\approx 1$ h)
$0.7$	$50$	$\frac{1}{50}$	$0.9245$	$0.0686$	$0.9931$	$42708$ s ( $\approx 12$ h)
$0.71$	$75$	$\frac{1}{75}$	$0.9440$	$0.0479$	$0.9919$	$552794$ s ( $\approx 6$ d)

Table 2: A summary of different factors

In the end, we choose $\beta=0.7381$ and construct an instance function $H_{B}$ . We show that $\int^{1}_{0}q_{P}^{*}(s)\mathrm{d}s>1$ . Consequently, we get an upper bound.

Theorem 3.8.

Given distribution $F_{B}$ , the randomized fixed-price mechanism that uses only the knowledge of the buyer distribution has approximation ratio at most $0.7381$ . Given distributions $F_{S}$ and $F_{B}$ , no fixed-price mechanism has an approximation ratio better than $0.7381$ .

Proof.

Let $\beta:=0.7381$ and consider the following function on $[0,1]$ :

H_{B}(s)=\begin{cases}1,&s\leq 0.25\\ 1-\lambda\left(1-e^{1.5-6s}\right),&0.25<s<0.6\\ 0,&0.6\leq s\leq 1\\ \end{cases}

where $\lambda=1/(1-e^{-2.1})$ . Besides, the function $H_{B}$ satisfies $G_{B}(1)=\frac{1-\beta}{\beta}$ . Then, we calculate the integral $\int^{1}_{0}q_{P}^{*}(s)\mathrm{d}s$ , that is

\int^{1}_{0}\beta\left[\left(\frac{H_{B}(s)}{G_{B}(s)}-\frac{\int^{1}_{s}H_{B}(t)^{2}\mathrm{d}t}{G_{B}(s)^{2}}\right)+(1-\beta)\frac{G_{B}(1)}{G_{B}(s)^{2}}\right]\mathrm{d}s.

We divide the integral into three parts: $\int^{1}_{0.6}q_{P}^{*}(s)\mathrm{d}s$ , $\int^{0.6}_{0.25}q_{P}^{*}(s)\mathrm{d}s$ and $\int^{0.25}_{0}q_{P}^{*}(s)\mathrm{d}s$ .

For the first part, we have

\displaystyle\int^{1}_{0.6}q_{P}^{*}(s)\mathrm{d}s=\int^{1}_{0.6}(1-\beta)\frac{1}{G_{B}(1)}\mathrm{d}s=0.4\beta=0.29524.

For the second part, it is difficult to compute accurately. So we use a program to approximate it and have $\int^{0.6}_{0.25}Q_{P}^{*}(s)\mathrm{d}s\approx 0.41766$ .

For the third part, the integral $\int^{0.25}_{0}q_{P}^{*}(s)\mathrm{d}s$ is

		$\displaystyle\int^{0.25}_{0}\frac{\beta\left(G_{B}(0.25)-\int^{1}_{0.25}H_{B}(t)^{2}\mathrm{d}t\right)+(1-\beta)G_{B}(1)}{\left(0.25-s+G_{B}(0.25)\right)^{2}}\mathrm{d}s$
	$\displaystyle=$	$\displaystyle\frac{A}{0.25-s+G_{B}(0.25)}\bigg{\|}_{0}^{0.25}$
	$\displaystyle=$	$\displaystyle\frac{0.25A}{0.25G_{B}(0.25)+G_{B}(0.25)^{2}}.$

where $A=\beta\left(G_{B}(0.25)-\int^{1}_{0.25}H_{B}(t)^{2}\mathrm{d}t\right)+(1-\beta)G_{B}(1)$ . For each term, we compute it precisely and have $\int^{0.25}_{0}q_{P}^{*}(s)\mathrm{d}s\approx 0.28722$ .

Finally, we get $\int^{1}_{0}q_{P}^{*}(s)\mathrm{d}s\approx 1.00012>1$ . That is, given the function $H_{B}$ above, no matter how we design the price mechanism, there always exists a seller distribution $F_{S}$ such that the welfare ratio is less than $0.7381$ . Please check numerical results at our github repository. ∎

4 Single-sample Approximation

We consider the fixed-price mechanism that receives a single sample from the seller distribution as sole prior information in this section. Previous works [DFL⁺21, KPV22] study deterministic mechanisms. We extend their bounds to randomized mechanisms. For asymmetric case, [DFL⁺21] show that every deterministic IC, IR and BB mechanism has approximation ratio at most $1/2$ . Here we show that the randomization would not help. In other words, given any single sample from the seller distribution, the designer is allowed to use a randomization over different fixed-price mechanisms. We demonstrate that a randomized fixed-price mechanism has approximation ratio at most $1/2$ . [DFL⁺21] also prove that there exists a deterministic fixed-price mechanism of which the lower bound is $1/2$ . Therefore, for randomized fixed-price mechanisms, approximation ratio $1/2$ is also tight.

Theorem 4.1.

Every randomized fixed-price mechanism that receives a single sample from the seller’s distribution as information has approximation ratio at most $1/2$ .

The idea is that we fix the buyer’s value to be quite high. At the same time, we construct the seller distribution on many small discrete values. Under such construction, the approximation ratio is exactly the probability that the trade occurs. That is, for any randomized mechanism, we show that there exists an instance that the seller rejects the trade with probability $0.5$ .

Proof.

For a randomized fixed-price mechanism, we denote it as a function $F_{P}:\mathbb{R}\rightarrow\Delta_{L^{1}}(\mathbb{R})$ that maps a value to a distribution. Then, we construct a set $\{s_{1},s_{2},\ldots,s_{n}\}$ that any two adjacent values satisfy $\Pr\left[F_{P}(s_{k})<s_{k+1}\right]=1-\epsilon$ and $s_{k}\leq s_{k+1}$ for $k\in[n-1]$ . Consider a seller whose valuation is drawn uniformly from the set and a buyer whose valuation equals $s_{n}\cdot 2^{n}$ . Let $s^{\prime}$ denote the seller’s sample and $s$ denote the seller’s valuation. Then the probability that the seller rejects the trade is:

	$\displaystyle\Pr_{s^{\prime},s}\left[F_{P}(s^{\prime})<s\right]$	$\displaystyle=\sum_{i=1}^{n}\Pr\left[F_{P}(s)<s_{i}\right]\cdot\Pr\left[s=s_{i}\right]$
		$\displaystyle\geq\sum_{i=2}^{n}\frac{i-1}{n}\cdot(1-\epsilon)\cdot\frac{1}{n}$
		$\displaystyle=\frac{n-1}{2n}\cdot(1-\epsilon).$

As $n$ grows to infinity and $\epsilon$ decreases to $0$ , the probability that the seller rejects the trade approaches $1/2$ . The approximation ratio approaches the probability that the trade occurs. Therefore, the upper bound of any randomized mechanism is $1/2$ . ∎

As for symmetric case, [KPV22] show that the approximation ratio $3/4$ is tight recently. We extend their bound to the randomized mechanisms.

Theorem 4.2.

Every randomized fixed-price mechanism that receives a single sample from the distribution as information in the symmetric bilateral trade has approximation ratio at most $3/4$ .

Proof.

Similar to the proof of Theorem 4.1, for any randomized mechanism, we want to show that there exists a distribution that achieves $3/4$ of welfare. Suppose that the randomized mechanism $F_{P}(\cdot)$ maps the single sample value to a price (note that it is also a random variable). Given $F_{P}(\cdot)$ and any $\epsilon>0$ , we construct a sequence of positive numbers $\hat{s}=\{s_{1},s_{2},\ldots,s_{n}\}$ such that $\Pr\left[F_{P}(s_{i})<s_{k+1}\right]\geq 1-\epsilon$ , where $i=1,2,\ldots,k$ . Besides, we introduce a value $s_{a}$ which is high enough (say $s_{a}\geq s_{n}^{2}$ ). The support of the value distribution is exactly $\{s_{1},s_{2},\ldots,s_{n},s_{a}\}$ in which the probability that the value is any of $\{s_{1},s_{2},\ldots,s_{n}\}$ is identical, i.e., $\Pr\left[s=s_{i}\right]=\Pr\left[s=s_{j}\right]$ where $i,j\in[n]$ . We denote by $q$ the total probability that the value is from the sequence $\hat{s}$ , that is $\Pr\left[s\in\hat{s}\right]=q$ , and $\Pr\left[v=s_{a}\right]=1-q$ . For convenience, we denote such a distribution as $F$ .

For the optimal welfare, we consider two situations. The first one is that at least one of the seller and buyer has the value $s_{a}$ . The other is that neither seller nor buyer has the value $s_{a}$ . In this case, if the value is less than $s_{n}$ , we increase it to $s_{n}$ , this can only improve the welfare. Thus, we have

\textrm{OPT-W}(F)\leq s_{a}\cdot(1-q^{2})+s_{n}\cdot q^{2}.

Given the distribution $F$ and the randomized mechanism $F_{P}(\cdot)$ , we denote by $\mathrm{LOSS}(F,F_{P})$ the difference between the optimal welfare and the expected welfare by the randomized mechanism mentioned above. We only consider the case that the buyer’s value is $s_{a}$ and the seller’s value is greater than the price $F_{P}(\cdot)$ . We can lower bound $\mathrm{LOSS}(F,F_{P})$ , where $\bar{s}$ is the value sample from the distribution $F$ :

		$\displaystyle\sum_{i=1}^{n}(s_{a}-s_{i})\cdot\Pr\left[F_{P}(\bar{s})<s_{i}\right]\cdot\Pr\left(s=s_{i}\right)\cdot\Pr\left(b=s_{a}\right)$
	$\displaystyle\geq$	$\displaystyle(s_{a}-s_{n})\cdot(1-q)\cdot(1-\epsilon)\cdot\frac{q}{n}\cdot\sum_{i=2}^{n}\frac{(i-1)q}{n}$
	$\displaystyle=$	$\displaystyle(s_{a}-s_{n})\cdot(1-q)\cdot(1-\epsilon)\cdot\frac{(n-1)q^{2}}{2n}.$

The second inequality is due to that we only consider that $\bar{s}=s_{1},s_{2},\ldots,s_{i-1}$ . Now we compute the ratio between the welfare loss and the optimal welfare. Note that $s_{a}$ is very high, we have

	$\displaystyle\frac{\mathrm{LOSS}(F,F_{P})}{\textrm{OPT-W}(F)}\geq$	$\displaystyle\frac{s_{a}\cdot(1-q)\cdot(1-\epsilon)\cdot\frac{(n-1)q^{2}}{2n}}{s_{a}\cdot(1-q^{2})}$
	$\displaystyle=$	$\displaystyle\frac{n-1}{2n}\cdot(1-\epsilon)\cdot\frac{q^{2}}{1+q}.$

For the term $\frac{q^{2}}{1+q}$ , we know that it always increases if $q\in[0,1]$ . Consequently, we have $\mathrm{LOSS}(F,F_{P})\geq\frac{1}{4}\cdot\textrm{OPT-W}(F)$ when $\epsilon\to 0$ , $n\to\infty$ and $q\to 1$ . That is, the upper bound of any randomized mechanism is $3/4$ . ∎

5 Conclusion and Discussion

We improved approximation ratios of fixed-price mechanisms in several settings for the bilateral trade problem with one buyer and one seller, in terms of the optimal welfare. Our methods differs from previous work. We establish the lower bounds by solving an optimization problem. Then we try to find a nearly-optimal solution using the discretization method and dynamic programming. Ideally, we can bound the error caused by discretization within any precision. However, due to the limitation of the hardware, we still leave a gap in approximation ratios.

Several interesting questions arise. Note that we only use the knowledge of the buyer distribution and get Theorem 3.3. In fact, we can also start from the seller distribution instead and get a similar but not the same optimization problem given in Theorem 3.3. If we only use the knowledge of the seller distribution, would we have a worse approximation bound? Another challenging question is to come up with a simple mechanism to approximate the optimal gain-from-trade. We do also think the ratio of RandOff [DMSW22, Fei22] could be improved significantly, but it needs new and deep insights.

References

[BCWZ17] Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proc. 18th ACM Conference on Economics and Computation (EC), pages 589–590, 2017.
[BD14] Liad Blumrosen and Shahar Dobzinski. Reallocation mechanisms. In Proc. 15th ACM Conference on Economics and Computation (EC), pages 617–617, 2014.
[BD21] Liad Blumrosen and Shahar Dobzinski. (almost) efficient mechanisms for bilateral trading. Games and Economic Behavior, 130:369–383, Nov 2021.
[BDK21] Moshe Babaioff, Shahar Dobzinski, and Ron Kupfer. A note on the gains from trade of the random-offerer mechanism. arXiv preprint arXiv:2111.07790, 2021.
[BM16] Liad Blumrosen and Yehonatan Mizrahi. Approximating gains-from-trade in bilateral trading. In Proc. 12th International Conference on Web and Internet Economics (WINE), pages 400–413, 2016.
[CBGK⁺17] Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Fixed price approximability of the optimal gain from trade. In Proc. 13th International Conference on Web and Internet Economics (WINE), pages 146–160, 2017.
[CBKLT16] Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In Proc. 27th ACM-SIAM Symposium on Discrete algorithms (SODA), pages 1424–1443, 2016.
[CGMZ21] Yang Cai, Kira Goldner, Steven Ma, and Mingfei Zhao. On multi-dimensional gains from trade maximization. In Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1079–1098, 2021.
[CW23] Yang Cai and Jinzhao Wu. On the optimal fixed-price mechanism in bilateral trade. arXiv preprint arXiv:2301.05167, 2023.
[DFL⁺21] Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Efficient two-sided markets with limited information. In Proc. 53rd ACM Symposium on Theory of Computing (STOC), pages 1452–1465, 2021.
[DK15] Moritz Drexl and Andreas Kleiner. Optimal private good allocation: The case for a balanced budget. Games and Economic Behavior, 94:169–181, Nov 2015.
[DMSW22] Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In Proc. 54th ACM Symposium on Theory of Computing (STOC), pages 718–721, 2022.
[Fei22] Yumou Fei. Improved approximation to first-best gains-from-trade. In Proc. 18th International Conference on Web and Internet Economics (WINE), pages 204–218, 2022.
[HR87] Kathleen M. Hagerty and William P. Rogerson. Robust trading mechanisms. Journal of Economic Theory, 42(1):94–107, Jun 1987.
[KPV22] Zi Yang Kang, Francisco Pernice, and Jan Vondrák. Fixed-price approximations in bilateral trade. In Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2964–2985, 2022.
[KV18] Zi Yang Kang and Jan Vondrák. Strategy-proof approximations of optimal efficiency in bilateral trade. Online, 2018.
[LLR89] Wolfgang Leininger, Peter B. Linhart, and Roy Radner. Equilibria of the sealed-bid mechanism for bargaining with incomplete information. Journal of Economic Theory, 48(1):63–106, Jun 1989.
[McA08] R Preston McAfee. The gains from trade under fixed price mechanisms. Applied Economics Research Bulletin, 1(1):1–10, 2008.
[MS83] Roger B. Myerson and Mark A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, Apr 1983.
[SZ16] Ran Shao and Lin Zhou. Optimal allocation of an indivisible good. Games and Economic Behavior, 100:95–112, Nov 2016.

		$\displaystyle\delta{H_{B}^{}}^{\prime}(z_{3}+\delta)G_{B}^{}(z_{3})-\int^{z_{3}+\delta}_{z_{3}}H_{B}^{}(t)\left(H_{B}^{}(t)-H_{B}^{*}(z_{3}+\delta)\right)\mathrm{d}t$
	$\displaystyle<$	$\displaystyle\delta{H_{B}^{}}^{\prime}(z_{3}+\delta)G_{B}^{}(z_{3})-\delta^{2}H_{B}^{}(z_{3}){H_{B}^{}}^{\prime}(z_{3}+\delta)$
	$\displaystyle=$	$\displaystyle\delta{H_{B}^{}}^{\prime}(z_{3}+\delta)\left(G_{B}^{}(z_{3})-\delta H_{B}^{*}(z_{3})\right)$