## 5 Incremental Improvement of Market Mechanism
### Imposing a Penalty on Buyers' Trade Failures  
In perishable goods markets, sellers have an incentive to discount their bids to reduce unsold goods. Buyers tend to underbid in the markets and wait for sellers' prices to fall, as shown in the simulation results in Section 4. To encourage buyers' high valuation, we impose a penalty on buyers for their matching failures. We advocate a _penalized payment policy_\(\{x^{t}\}^{t\in T},x^{t}=(s^{t},b^{t},p^{t})\), where \(p^{t}_{j}(\hat{\theta}^{\leq t})\in\mathbb{R}_{>0}\) represents a penalty imposed on buyer \(j\) as a result of her trade failures until round \(t\), given reports \(\hat{\theta}^{\leq t}\). Although imposing the penalty on buyers seems unrealistic in practical market situations, it can be considered as a market entry fee for the buyers, which is refunded when they successfully trade in the market.  
The penalty of buyer \(j\) is an average price gap between a buyer's bid and sellers' asks in the past matching failures, which is updated every time the market is cleared, as shown in Algorithm 1.  
Figure 3: Simulation results in online markets with naive DA mechanism. (**a**) Buyers’ surplus; (**b**) Buyers’ resale profit; (**c**) Buyers’ utility.  
The penalized pricing policy requires a buyer to pay the sum of a clearing price and the penalty when the buyer's bid is executed. If the required amount exceeds the buyer's bid price, the buyer refuses the payment to cancel the execution and proceed to another bidding. Therefore, the penalized pricing policy does not cause buyers' individual rationality to deteriorate and the matching condition of the market changes as follows.  
**Definition 4** (Matching condition with buyer's penalty).: _Seller i's ask \(\hat{\theta}_{i}^{t}=(\hat{\sigma}_{i}^{t},q_{i}^{t},a_{i}^{p},d_{i}^{p})\) and buyer j's bid \(\hat{\theta}_{j}^{t}=(\hat{\sigma}_{j}^{t},q_{j}^{t},a_{j}^{p},d_{j}^{p})\) are matchable when_  
\[(\hat{\sigma}_{i}^{t}\leq\hat{\sigma}_{j}^{t})\wedge([a_{i}^{p},d_{i}^{p}] \cap[a_{j}^{p},d_{j}^{p}]\
eq\emptyset)\wedge(d_{i}^{p}>d_{j}^{p})\wedge(q_{i}^ {t}>0)\wedge(q_{j}^{t}>0)\wedge(b_{i,j}^{t}(\delta^{\leq t})+p_{j}^{t}(\delta^{ \leq t})\leq\hat{\sigma}_{j}^{t})\,. \tag{4}\]  
The last term in the matching condition (4) guarantees the buyer's individual rationality.  
When the penalized pricing policy is adopted, the buyer's utility is reduced by the penalty for trade failures as follows.  
**Definition 5** (Buyer j's penalized utility in time round \(t\)).: \[U_{j}(\theta^{\leq t})=\sum_{\{p|a_{j}^{t}\leq t\}}\sum_{r\in[a_{j}^{t},d_{i}^ {p}]}\sum_{i\in\wedge n_{i,j}^{t}>0}\left(p_{j}^{p}-b_{i,j}^{p}(\delta^{\leq t })+\gamma_{j}^{p}p_{j}^{p}-p_{j}^{t}(\delta^{\leq t})\right)\pi_{i,j}^{t}( \delta^{\leq t}).\] (5)  
Hence, with the penalized pricing policy, buyers have an incentive to report a high valuation for avoiding matching failures.  
We evaluate a penalized DA mechanism that replaces the simple k-DA pricing policy in the naive DA mechanism with the penalized pricing policy. We execute the same simulations described in Section 4.2.2 to investigate the effects of imposing a penalty on buyers when their bids fail to match sellers' asks.  
Figure 3(a),b,d represent buyers' surplus, resale profit and total utility, respectively, in the same way as the previous experiments. Figure 3(c) shows the penalty imposed on each buyer by the mechanism.  
Comparing Figures 3(b) and 3(b), we find that, after imposing penalties on buyers, misreporting decreases buyers' resale profits drastically, because the matching condition (4) increases matching failures and reduces resale opportunities for penalized buyers. In addition, Figure 3(a),c show that the increase of buyers' surplus by misreporting is canceled out by the penalty imposed on the buyers.  
Therefore, by comparing Figures 3c and 4d, it is shown that the proposed penalized DA mechanism largely succeeds in eliminating buyers' utility gain by misreporting their values in the markets.