Introduction

Matching the right pairs of competitive customers and providers for electronic services on double-sided markets is an important optimization problem in Operations Research [2]. On these markets, multiple service providers offer electronic services of a specified quality of service (QoS), while multiple customers demand these services at a specific QoS. To this end, matching markets have recently emerged in different business areas including Cloud computing [1]. In common market settings, strategic participants may engage in bid manipulation in order to influence their transaction prices. While first-best solutions are not available in such settings [10], second-best mechanisms for matching customers and providers with interdependent utilities have been proposed [15]. Although such mechanisms satisfy incentive compatibility and individual rationality, the associated payment schemes are difficult to implement in real-world scenarios. Attempts to simplify the payment scheme, however, may open the way for strategic participants to increase their utilities by misrepresenting their bids. Thus, before modifying the payments, the mechanism designer must obtain an accurate estimation for the potential utility gain that participants can achieve due to strategic bid manipulation. Prior research studies the average utility gain of participants with independent utilities on markets for electronic services. The mechanism proposed by Schnizler et al. uses k-pricing to provide a simple payment scheme that is well-suited for real-world electronic service exchange [12]. Although their approach allows for estimating the utility gain of strategic participants, it does not consider interdependent utilities. Lee analyzes the manipulability of stable matching mechanisms to quantify the utility gain participants can expect through bid manipulation [8]. Yet concrete payment schemes for real-world markets are missing. In the context of generalized assignment problems, Fadaei and Bichler propose truthful approximation mechanisms in paymentfree environments [3]. Fadaei and Bichler use the optimal welfare value as a benchmark to estimate the efficiency loss due to strategic bidding. Because they consider mechanism design without money, no payment rules are provided. Widmer and Leukel [15] provide a lower bound for the efficiency of a second-best mechanism that allocates electronic services with private quality information. Although they specify the incentive compatible payments of customers and providers in double-sided markets, these payment rules turn out to be inexpedient for implementing the associated mechanism in real-world environments. The objective of our research is to study the efficiency loss of a mechanism with two straightforward payment schemes for electronic service matching in double-sided markets. We apply these two payment schemes to markets where participants have interdependent utilities. The first payment scheme is based on the prominent Vickrey–Clarke–Groves (VCG) pricing rules [14], which satisfy incentive compatibility in single-unit and certain multiunit procurement auctions [5]. The second payment scheme is based on k-pricing introduced by Sattherthwaite and Williams [11], where the price is simply calculated as the arithmetic mean of customer valuation and provider cost. Mechanisms with k-pricing, however, are not incentive compatible [10]. In a set of simulation experiments, we study the potential utility gains that participants can expect through strategic bid manipulation. We find that in our model with interdependent utilities, the prominent VCG mechanism is not incentive compatible. The reason for the failure of incentive compatibility is that strategic customers and providers can manipulate their perceived impact on social surplus through the utilities of their matched partners. Hence, participants are able to increase their utilities by manipulation even when VCG pricing is used. The results of our experimental evaluation for both payment schemes provide an accurate estimation for these utility gains.