Sage Journals: Discover world-class research

Abstract

We are entering the era of digital business moments where autonomous things will buy and sell services from each other in order to make people’s life easier. They will also negotiate in order to achieve the best price for their services which will result in Internet of Things auctions. Such auctions will be combinatorial and recurrent. Recurrent auctions pose a problem of bidder drop which leads to market collapse. Moreover, in Internet of Things, bidders will employ different strategies according to their pattern of consuming resources. We describe two bidding strategies which may lead to market collapse or very low revenue: opportunistic and periodic bidding. We devise two algorithms: revenue maximizing auction and highest bid lock auction, analyze their performance under these two bidding strategies, and compare them to traditional combinatorial auction. We find out that the revenue maximizing auction prevents market collapse under opportunistic bidding while highest bid lock auction provides the highest revenue under both strategies.

Keywords

Combinatorial auction recurrent auction bidding strategy Internet of Things

Introduction

With the rapid development of Internet of Things (IoT), more and more devices are connected and can perform tasks without human intervention.¹ Gartner predicts that we are entering the era of digital businesses and business moments.² Devices will be able to come together instantly to perform actions that were traditionally done by humans. They will also negotiate in order to achieve the best price for their services.³ Therefore, there is a need for marketplaces for IoT resources provided by those machines where the negotiation, or in other words, auction could take place. On such marketplaces, the currency may be either virtual or real. The market price may be highly unpredictable, as the demand and supply can vary according to instantaneous business moments which may have not easily identifiable occurrence patterns. This will make it hard for providers to set the proper price. Currently, just in the area of cloud computing, judging from the proliferation of different pricing rules, pricing is arduous to determine for business owners and hard to navigate for the customers.⁴ In highly dynamic IoT systems, the control over a fixed price will be even more difficult and less scalable. For example, the providers may not be able to rely on setting a global price for their services as prices for the same service may fluctuate among different locations due to the local demand and supply patterns. Auctions, on the other hand, provide a greater flexibility due to the ability to adjust the price to current market demand. For example, Amazon has successfully been using auctions for unused large capacity.⁵ Finally, many of the IoT resources, like the actuators, may only serve one user at a time. For such resources, auctions additionally solve resource access conflicts in cases when more than one customer application requests the service at the same time.⁶

In this article, we will consider auctions where the buyers of IoT resources are the bidders and the providers are the sellers. In order to fulfill a business moment, often a whole bundle of heterogeneous IoT resources will be needed. For example, when an application representing an advertisement company needs to play some multimedia, a display and speakers will be needed (e.g. in the taxi or belonging to a smart city’s public infrastructure). In case one type of resource cannot be provided, the business moment might not be able to take place. Such auctions, where resources will be traded in inseparable bundles, in an “all or nothing” manner, are called combinatorial auctions.⁷ Moreover, many of the business moments will happen over and over again, when the same IoT resources will be requested and consumed repeatedly. For example, in agriculture, the auction for the shared set of tools (drones, sensors, and machinery) is repeated daily in a community of farmers. Such trading will lead to a recurrent auction.⁸ In such auctions, bidders learn from previous rounds and change their strategy. Lower bidders will drop out of the auction when they realize they have no chance of winning, while higher bidders will shade their bids realizing there is less competition since lower bidders dropped out. This may drive prices down in what is called a bidder drop problem.⁹ In extreme cases, the prices drop to nearly zero causing a market collapse.

Another challenge to designing proper recurrent auction mechanism stems from heterogeneous nature of IoT. Different bidders will have different resource consumption needs resulting in different bidding strategies. We identify two resource consumption behaviors that lead to two different bidding strategies. In opportunistic bidding, bidders (e.g. an advertising company) are interested in getting resources as often as possible or at least every specified number of rounds. Thus, to increase their chances of winning, they will start from their maximum possible value and lower the bids in subsequent rounds. In periodic bidding, bidders (e.g. a farmer) are only interested in getting resources once within specified number of rounds. They will use remaining rounds to probe the system for the lowest price. Thus, they will start from the minimum value allowed by an auctioneer and increase their bids in subsequent rounds. Opportunistic bidding is more predictable because bidders reveal the maximum value they are ready to pay. It is also less aggressive in terms of individual bidder behavior since the price drop is not very severe, but it leads to more severe bidder drop, which causes market collapse in the long run, than periodic bidding. On the other hand, periodic bidding does not result in market collapse but is less predictable because bidders do not reveal the maximum value they are ready to pay. This results in overall lower revenue because the bidders may not reach their maximum value.

We show that for opportunistic bidding, optimal revenue can be achieved by first eliminating low bidders from the auction and then alternating the wins among the remaining bidders, thus giving them the incentive to keep their bids high. To achieve this, we propose a revenue maximizing auction (RMA). RMA performs well with more predictable strategies like opportunistic bidding, but it causes market collapse with less predictable strategies like periodic bidding. We develop a second algorithm, called highest bid lock auction (HBLA), which records the highest bid ever submitted by the bidder and prevents them from winning if they bid lower than that. We show that the HBLA is able to both prevent market collapse in opportunistic bidding and increase revenue above traditional combinatorial auction (TCA) in periodic bidding.

The rest of the article is organized as follows. In the next section, we discuss related works. In section “System model,” we discuss the design of auctions for heterogeneous IoT resources and develop two bidding strategies. In section “Winner determination algorithms for IoT,” we propose two algorithms: RMA and HBLA for winner determination in recurrent combinatorial auction. In section “Simulation and results,” we compare the performance of RMA and HBLA applied to two bidding strategies with the performance of TCA. We finish the article with section “Conclusion.”

Related work

Easley and Kleinberg¹⁰ provide introduction to auctions and outline bidding strategies for basic single round auctions in accessible terms. The single round auctions for IoT resources have been proposed with regard to sensing capabilities of smart phones where users perform participatory sensing tasks. For example, Chen and Wang¹¹ propose a strategy proof mechanism for collaborative sensing. Furthermore, Zhu et al.¹² propose a multiple round task allocation algorithm based on auction, but they do not explore the effects of bidders’ strategy on the revenue in such a recurrent auction. Finally, Sun and Ma¹³ propose all-pay auctions and a collection-behavior based multi-parameter posted pricing mechanism for participatory sensing.

One solution to increase revenue in auctions is setting a reserve price. The auctioneer will keep the resources if the bids are below this price. However, this introduces two problems. First, in highly dynamic IoT markets, it may be not possible to predict future bidders’ behavior based on previous bid values, thus making reserve price hard to determine; in the same way, it can be hard to set the fixed price. Second, IoT markets will include resources that are perishable which means they cannot be stored for later use (e.g. access to an actuator). Therefore, improperly set reserve price may lead to excessive resource waste of unsold resources,¹⁴ which will also cause revenue loss. That is why in this work, we focus on solutions that can prevent market collapse without resorting to the reserve price.

Another approach to prevent market collapse in recurrent auctions is described by Lee and Szymanski⁸ as well as Murillo et al.⁹ Both works propose encouraging lower bidders to stay in the auction by providing fair assignment of the resources by assigning them different priorities or scores. However, fairness introduces lower bidders to the auction, and therefore, the overall revenue will also decrease. Murillo et al.¹⁵ also aim at improving the revenue of recurrent auction with fairness and thus cannot achieve optimal revenue, besides they implement a reserve price causing some resource waste.

System model

In order to achieve complete automation of tasks necessary to realize the full potential of digital business moments proposed by Gartner, not only data but also the whole spectrum of IoT resources must be made accessible for trade by digital entities. In our previous work,¹⁶ we have proposed a platform where resources and applications consuming them are represented by agents. In this article, we develop the necessary components of an IoT marketplace, which comprises of resources, bidders, and auctioneer.

Resources

IoT encompasses a wide variety of heterogeneous resources depicted in Figure 1. They could be classified into four groups according to their level of abstraction. At the first level there are everyday objects that are “dumb” by themselves, but by equipping them with electronic tags, for example, a QR code, they become digitized. The second level constitutes electronic devices that can perform a single function, that is, the sensors and actuators. At the next level there are machines and systems composed out of those simple devices, which can perform more complex tasks, for example, an autonomous vehicle. Last are the services which are decoupled from physical machines. These constitute cloud or fog services, data aggregation, business solutions, and so on. The subject of an auction is access to the resources in a specified amount of time, and the ability to perform any action allowed by its Application Programming Interface (API), like using a tagged object, changing the temperature of a thermostat, controlling the autonomous vehicle, or accessing the computing resources. Thus, although they are heterogeneous, each of the resource groups contains resources that are perishable, that is, they must be used in a time specified by an auction, because they cannot be stored for future use. A resource is identified by its unique ID, type, and number of units and time duration of one unit.

Figure 1.

IoT resources ordered according to their level of abstraction.

Bidders

Each bidder has a different valuation for the resources it wants to buy which is called a true value.¹⁰ True value represents the maximum price the bidder is willing to pay for the resources. In non-combinatorial auction, true value represents the price per unit of resource. But since business moments may require whole set of resources, bidders treat resources as compliments,⁷ that is, they are only interested in the whole bundle. Thus, they hold a true value only for the whole bundle, which may be different than the sum of individual resource values. In this article, we are dealing with repeating business moments so the resource requests remain the same in subsequent auction rounds. We assume the bidders are rational, that is, try to maximize their payoffs, and can be dishonest in reporting their true values but there is no collusion or other malpractice. We denote bidder i’s true value as $v_{i}$ and the bid they actually report as $b_{i}$ . Bid value is a function of true value according to bidder i’s strategy $S_{i}$

b_{i} = S_{i} (v_{i})

(1)

The bidder’s strategy is always a trade-off between two opposing goals. One is to bid high enough to win and the other is to bid low enough to pay lowest possible price. Recurrent auctions present an advantage to the bidders since they can use some of the rounds to adjust their strategy, while keeping the overall frequency of winning within desired limits. Bidders will therefore decrease their bids to probe the system, risking not becoming a winner in some rounds. On the other hand, bidders will withdraw from the auction if their win frequency is not satisfied. In this article, we model the bidders’ win frequency requirement after Lee and Szymanski,¹⁴ where the number of consecutive losses denoted $cl$ cannot exceed their tolerance denoted $t$ .

We divide bidders into two main groups, called periodic bidding and opportunistic bidding, according to the way in which they consume resources and in result behave differently while bidding for them. In opportunistic bidding, bidders start from their maximum possible value and lower the bids in subsequent rounds, while in periodic bidding they start from the minimum value allowed by auctioneer and increase their bids in subsequent rounds.

Opportunistic bidding strategy

The bidder needs the resources at minimum once within $t$ rounds, but is also interested in getting resources in other rounds if possible. Thus, this kind of bidder is more concerned with keeping winning the resources rather than finding out the lowest possible price. In this case, the bid lowering is less aggressive; bidders will decrease the bid upon winning the previous round only by the lowest possible decrement, which we assume is equal to 1. We developed the strategy shown in Algorithm 1 to model this kind of behavior. Their strategy can be summarized as follows:

In the first round bid $b_{i} = v_{i}$ ;

Decrease $b_{i}$ by 1 if won in previous round;

Increase $b_{i}$ by 1 if lost in previous round and $b_{i} < v_{i}$ ;

Withdraw from auction if $cl > t$ .

Algorithm 1. Opportunistic bidder pseudocode.
while participating in auction do if round==1 then $b_{i} \leftarrow v_{i}$ else if won in previous round then $cl \leftarrow 0$ $b_{i} \leftarrow b_{i} - 1$ if $b_{i} < v_{\min}$ then $b_{i} \leftarrow v_{\min}$ else {lost in previous round} if $cl \leq t$ then $cl \leftarrow cl + 1$ $b_{i} \leftarrow b_{i} + 1$ if $b_{i} > v_{i}$ then $b_{i} \leftarrow v_{i}$ else { $cl > t$ } withdraw from auction

Algorithm 1. Opportunistic bidder pseudocode.

while participating in auction do
if round==1 then

$b_{i} \leftarrow v_{i}$

else
if won in previous round then

$cl \leftarrow 0$

$b_{i} \leftarrow b_{i} - 1$

$b_{i} < v_{\min}$

then

$b_{i} \leftarrow v_{\min}$

else {lost in previous round}
if

$cl \leq t$

then

$cl \leftarrow cl + 1$

$b_{i} \leftarrow b_{i} + 1$

$b_{i} > v_{i}$

then

$b_{i} \leftarrow v_{i}$

else {

$cl > t$

}
withdraw from auction

Periodic bidding strategy

In this case, the bidder is only interested in getting resources once within $t$ rounds, and in the remaining rounds, it has nothing to lose. Thus, we can say that this kind of bidder is more concerned with finding out the lowest possible price rather than keeping winning the resources. It can aggressively probe the system to find out the lowest winning price. Since bidder can accept losing in the first couple of rounds, it will not want to disclose its true value to the auctioneer. Thus, it will start from lowest bid accepted by auctioneer, $v_{\min}$ , increasing the bid in consecutive rounds, trying to get to $v_{i}$ within $t$ rounds. $v_{i}$ is the upper bound on its bid value, so if it did not win within $t$ rounds, it will drop out of the auction. In case of win anywhere up to and including round $t$ , it decreases the winning bid by a chosen fraction $d$ , $0 < d \leq 1$ , and starts the process again. The choice of $d$ depends on bidder’s risk profile with more risky bidders having lower $d$ . The strategy can be summarized as follows:

In the first round bid $b_{i} = v_{\min}$ ;

Bid $b_{i} * d$ , if won in previous round;

Increase $b_{i}$ by some step if lost in previous round;

Withdraw from auction if $cl > t$ .

Algorithm 2 shows the implementation of this strategy, in which the bidder further divides its tolerance period into $t_{1}$ and $t_{2}$ . During the first $t_{1}$ rounds, it aims at reaching the last winning bid value, stored in $b_{target}$ . It does this by incrementing the bid by step $s_{1}$ . If this does not lead to a win, then in the second part of the tolerance period, $t_{2}$ , it increments the bid by $s_{2}$ trying to reach its true value $v_{i}$ . The reasoning behind such behavior is that bidder wants to pay at most its last successful bid value. However, in case the situation changes and its last winning bid is not high enough to win in current round, it still has several more rounds to reach its true value.

Algorithm 2. Periodic bidder pseudocode.
compute $t_{1}$ compute $t_{2}$ $b_{target} \leftarrow v_{i}$ $s_{1} \leftarrow (v_{i} - b_{i}) / t_{1}$ $s_{2} \leftarrow 0$ while participating in auction do if round==1 then $b_{i} \leftarrow v_{\min}$ else if won in previous round then $cl \leftarrow 0$ $b_{target} \leftarrow b_{i}$ $b_{i} \leftarrow b_{i} * d$ if $b_{i} < v_{\min}$ then $b_{i} \leftarrow v_{\min}$ $s_{1} \leftarrow (b_{target} - b_{i}) / t_{1}$ $s_{2} \leftarrow (v_{i} - b_{target}) / (t_{2} + 1)$ else {lost in previous round} if $cl \leq t$ then $cl \leftarrow cl + 1$ if $b_{i} \leq b_{target}$ then $b_{i} \leftarrow b_{i} + s_{1}$ else if $b_{i} < v_{i}$ then $b_{i} \leftarrow b_{i} + s_{2}$ else $b_{i} \leftarrow v_{i}$ else { $cl > t$ } withdraw from auction

Algorithm 2. Periodic bidder pseudocode.

compute

$t_{1}$

compute

$t_{2}$

$b_{target} \leftarrow v_{i}$

$s_{1} \leftarrow (v_{i} - b_{i}) / t_{1}$

$s_{2} \leftarrow 0$

while participating in auction do
if round==1 then

$b_{i} \leftarrow v_{\min}$

else
if won in previous round then

$cl \leftarrow 0$

$b_{target} \leftarrow b_{i}$

$b_{i} \leftarrow b_{i} * d$

$b_{i} < v_{\min}$

then

$b_{i} \leftarrow v_{\min}$

$s_{1} \leftarrow (b_{target} - b_{i}) / t_{1}$

$s_{2} \leftarrow (v_{i} - b_{target}) / (t_{2} + 1)$

else {lost in previous round}
if

$cl \leq t$

then

$cl \leftarrow cl + 1$

$b_{i} \leq b_{target}$

then

$b_{i} \leftarrow b_{i} + s_{1}$

else if

$b_{i} < v_{i}$

then

$b_{i} \leftarrow b_{i} + s_{2}$

else

$b_{i} \leftarrow v_{i}$

else {

$cl > t$

}
withdraw from auction

Auctioneer and winner determination

Auctioneer represents the seller or the group of sellers of IoT resources, which could be enterprises or private owners. Auctioneer can either be the same entity as the seller or it can be a separate entity that runs an auction for bidders and sellers. The distributed and uncontrolled nature of IoT makes designing an auction for its resources a complex task. In this work, we restrict the problem to one seller selling its goods to multiple buyers, as in case of big resource providers like companies or organizations. Therefore, we assume that resources are traded in a synchronous manner, meaning that their units are of equal length and aligned in time. The auction takes place at time intervals equal to resource unit length and we ignore the computation overhead.

Winner determination in a combinatorial auction is a NP-hard problem similar to a multi-dimensional knapsack problem.⁹ In a recurrent combinatorial auction, it can be modeled as follows

\begin{matrix} \max \sum_{i = 1}^{N} b_{i} (r) x_{i} (r) \\ s . t . \sum_{i = 1}^{N} x_{i} q_{ij} \leq Q_{j}, \forall j \in {1, M} \end{matrix}

(2)

where $r$ is the current auction round, $N$ is the total number of bidders, $b_{i} (r)$ is bidder i’s bid submitted in round $r$ , $x_{i} (r) \in {0, 1}$ represents whether bidder $i$ is assigned resources $(x_{i} = 1)$ or not $(x_{i} = 0)$ , $q_{ij}$ is the number of units of resource $j$ requested by bidder $i$ , $Q_{j}$ is the number of available units of resource $j$ , and $M$ is the number of resource types.

We will call formula (2) a traditional combinatorial auction (TCA). In a recurrent auction, that is, $r > 1$ , the problem arises from the fact that bidders learn the result of previous auction rounds and can change their strategy. Lower bidders will drop out of auction when they realize they have no chance of winning, while higher bidders will lower their bids realizing they have less competition. In our previous work,¹⁷ we have shown that even with scarce resources, the competition may not be enough for the prices to stabilize, causing market collapse. Below we will examine the effect of different bidding strategies on auctioneer’s revenue in a recurrent TCA. There are $N = 20$ bidders and $M = 5$ types of resources, each with $Q_{j} = 20$ units. Bidders’ bids, requests, and tolerance are random and they are the same in both bidding strategies. We use normal distribution with mean of 5 for bidders’ true values $v_{i}$ . Bidders’ requests, $q_{i, j}$ are uniformly distributed over [0..4]. The bidders’ tolerance values $t_{i}$ are uniformly distributed over [2..10]. Lowest accepted bid is $v_{\min} = 1$ .

Opportunistic bidding strategy in TCA

In Figure 2(a), we can observe the revenue resulting from bidders using opportunistic strategy. It will lead to a market collapse after around 100 rounds. In Figure 2(b), we can observe behavior of bidders to further analyze the situation that led to market collapse. Bidders start the auction from bidding their true value. A number of bidders were unable to win any resources despite bidding their $v_{i}$ . They all drop out of the auction after their tolerance ran out, which is signified by their bids dropping to 0 before round 10. The remaining bidders are reducing their bids and still winning resources. Their bids reach the lowest price accepted by auctioneer around round 100. They continue to win resources while offering this price until the end of the auction, because there is no competition.

Figure 2.

Auctioneer’s revenue under (a) opportunistic and (c) periodic bidding strategy and bidder behavior under (b) opportunistic and (d) periodic bidding strategy in traditional combinatorial auction.

Periodic bidding strategy in TCA

In this case, bidders start from lowest possible value; thus, the revenue reaches much lower values than with opportunistic strategy, but it does not cause market collapse. This is shown in Figure 2(c). The bidder behavior that leads to such revenue is shown in Figure 2(d). Everyone starts from minimum value. Those who win in first round keep bidding that value while others increase their bid. This causes the winners and losers switch places. Next, since there are enough resources for everyone, and most bidders can win more often than what is required by their tolerance, they start dropping the bids while still winning. The sudden spikes in bid values signify bidders that did not win resources until $t_{2}$ and have to significantly increase bid to ensure a win.

Winner determination algorithms for IoT

In this section, we develop two auction algorithms for IoT. First, we tackle the more severe problem of market collapse in TCA under opportunistic strategy. In order to prevent the collapse, we need to maintain enough bidders in auction to provide competition. On the other hand, keeping additional bidders for the sake of competition introduces lower bidders into the auction who decrease the average revenue. Therefore, we develop RMA for opportunistic bidding which aims at including the lowest possible number of bidders in order to maintain competition. Second, we extend the design to cover more unpredictable bidding behavior modeled by periodic bidding. We develop HBLA which achieves the same result as RMA for opportunistic bidding and outperforms both RMA and TCA in periodic bidding.

RMA

In order to maximize the revenue in recurrent auction, we need to find an optimal point between the high number of winners needed to sustain competition and the low number of winners needed to maximize the revenue. Since the number of winners depends on the number of available resources and bidders’ requests, in order to find such an optimal point, we can analyze bidder behavior with regard to the ratio of a combined request from all participants and the number of available resources. Let us first consider the opportunistic bidding scenario.

If a combined request from all the participants is more than twice the number of available resources

\sum_{i = 1}^{N} q_{ij} > 2 Q_{j}, \forall j \in {1, M}

(3)

then due to high competition, on average they will lose more often than win. It means that bidders will keep their true value as bid, provided they did not drop from the auction due to their tolerance limit. However, such a large number of participants means low bidders are included in the auction and they will lower the total revenue.

If, on the other hand, combined request from all the participants is less than twice the number of available resources

\sum_{i = 1}^{N} q_{ij} < 2 Q_{j}, \forall j \in {1, M}

(4)

then on average they will win more often than lose. However, it can result in reducing their bids because of lack of competition and driving overall revenue down.

Thus, ideally, the combined request from all participants should be about twice the available resources

\sum_{i = 1}^{N} q_{ij} \approx 2 Q_{j}, \forall j \in {1, M}

(5)

so that each bidder could win every second round. It keeps the necessary competition but cuts the unnecessary low bidders. To achieve this in an opportunistic bidding scenario, we propose a RMA, which works in the following way.

In Round 1, we compute winners according to TCA formula

\begin{matrix} \max \sum_{i = 1}^{N} b_{i} (1) x_{i} (1) \\ s . t . \sum_{i = 1}^{N} x_{i} q_{ij} \leq Q_{j}, \forall j \in {1, M} \end{matrix}

(6)

and denote the set of winners as $W_{1}$ , which is the highest bidding group among all bidders. In Round 2, we exclude the winners from Round 1 and compute the optimal set of winners with the remaining bidders

\begin{matrix} \max \sum_{i = 1, i \notin W_{1}}^{N} b_{i} (2) x_{i} (2) \\ s . t . \sum_{i = 1, i \notin W_{1}}^{N} x_{i} q_{ij} \leq Q_{j}, \forall j \in {1, M} \end{matrix}

(7)

and denote this set of winners as $W_{2}$ , which is the second highest bidding group among all bidders.

Thus, the total set of participants in the recurrent auction will be $W = W_{1} + W_{2}$ . In subsequent rounds, we alternate the set of participants, in even rounds including only $W_{1}$ and in odd rounds including only $W_{2}$ . The bidders will decrease their bid by 1 after they win, but they will lose in the next round, which will cause them to increase the bid back to the previous value. This also causes starvation of the weakest bidders who are not in either set of winners. Thus, two groups of the strongest winners are created who win and lose alternately, keeping up the competition as well as highest possible revenue.

HBLA

The above auction algorithm only works with less aggressive bidding strategies like opportunistic bidding described earlier. With more aggressive and unpredictable strategy, like periodic bidding, the bidder does not reveal neither their true value, nor bid increments or decrements per round. As a result, bidders cannot be clearly assigned into alternating winning groups and eventually RMA will collapse. To remedy this, we develop HBLA to take advantage of the fact that auctioneer can also infer bidders’ values from the past auction rounds. HBLA records highest bid ever submitted by each bidder which we denote as $bma x_{i}$ and does not assign resources if the bidder bids below that bid. Therefore, its algorithm is as follows (Algorithm 3).

Algorithm 3. HBLA pseudocode.
for each round do for each bidder do $bma x_{i} \leftarrow \max (bma x_{i}, b_{i})$ if $b_{i} < bma x_{i}$ then $b_{i}$ = 0 determine winners by TCA

Algorithm 3. HBLA pseudocode.

for each round do
for each bidder do

$bma x_{i} \leftarrow \max (bma x_{i}, b_{i})$

$b_{i} < bma x_{i}$

then

$b_{i}$

= 0
determine winners by TCA

In HBLA, in order to win the auction, the bidders are forced to submit the highest bid they ever revealed to the auctioneer. Thus, even if the bidder does not care to lose in some of the rounds, they will be forced to bid high at least in the rounds that they do care to win the resources. This helps to prevent the market collapse even in highly aggressive bidding strategies like periodic bidding.

Simulation and results

Simulation setup

We simulate the following algorithms:

RMA

HBLA

with two bidding strategies:

Opportunistic bidding strategy

Periodic bidding strategy

We simulate our system in MATLAB and compare the results to TCA. We use the following setup.

Auctioneer and resources

There is one seller, and $M = 5$ types of resources, each with $Q_{j} = 20$ units. The minimum accepted bid is $v_{\min} = 1$ . The winner determination problem is solved using MATLAB’s linear programming tool. Each simulation consists of 1000 auction rounds.

Bidders

All bidders’ variables are generated at the beginning and remain the same throughout the simulation. Bidders’ requests, $q_{i, j}$ are uniformly distributed over [0..4]. We use normal distribution with mean of 5 for bidders’ true values $v_{i}$ . The bidders’ tolerance values $t_{i}$ are uniformly distributed over [2..10]. To model different risk profiles of bidders using the periodic strategy, $d_{i}$ are uniformly distributed over (0..1]. Bidders quit the auction by submitting bid $b_{i} = 0$ and if they quit, they do not return to the auction.

Simulation results

First, we examine revenue of RMA and HBLA under opportunistic and periodic bidding strategy with $N = 20$ bidders. The results are shown in Figure 3. The revenue for RMA is shown in Figure 3(a). The algorithm chooses two groups and awards them alternately. Since the two highest groups of bidders are chosen, and they are competing to stay in the auction, with opportunistic bidding, the algorithm is able to achieve revenue in each round that is comparable to first rounds of TCA (see Figure 2(a)). On the other hand, with periodic bidding, RMA performs poorly. Since all bidders start from lowest value, RMA randomly assigns winners. The other bidders increase the bid to be able to win in the second round, but in subsequent rounds everyone reduces the bid by a higher value after winning compared to the value of increase after loosing. Since they win every second round regardless of the bid value, the ratio of decrease to increase grows and the algorithm causes market collapse. Figure 3(b) shows HBLA revenue. In opportunistic bidding, it achieves the same revenue as RMA due to the fact that in this strategy, bidders start from their maximum value and it stores this value. If they bid lower, they are not considered for the resource assignment so they are forced to increase their bid. Moreover, HBLA in periodic strategy does not cause a market collapse and is able to increase the revenue above the result from combinatorial auction (see Figure 2(c)) because it stores the maximum bid ever submitted by each bidder. The bidders are thus forced to come back to their highest bid each time they are going to run out of tolerance for consecutive loss.

Figure 3.

Auctioneer’s revenue under opportunistic and periodic bidding strategies for (a) revenue maximizing auction and (b) highest bid lock auction.

Next, we vary the number of bidders while keeping the number of resources $Q_{j} = 20$ , to examine how algorithms perform with different supply-to-demand ratios. We calculate average revenue from 10 runs of each auction simulation and the results are shown in Figure 4. In general, all algorithms conform to the principle that increasing demand drives the revenue up, except for RMA under periodic bidding strategy. In opportunistic strategy, as shown in Figure 4(a), since bidders reveal their true value, RMA achieves the same revenue as HBLA for each value of N. TCA leads to collapse when the number of bidders is low. The higher the ratio of bidders to resources, the more chances to achieve stability as the high demand may warrant enough competition for bidders to stay in the auction, which we have shown in our previous work.¹⁷ In periodic bidding strategy shown in Figure 4(b), RMA fails to generate any significant revenue. TCA and HBLA show faster revenue increase with demand than in case of opportunistic bidding. HBLA outperforms TCA especially with small demand when the competition in TCA is not high enough to keep revenue high. Overall, HBLA performs the best in both bidding strategies.

Figure 4.

Auctioneer’s revenue under (a) opportunistic strategy and (b) periodic strategy for varying numbers of bidders and different auction algorithms (TCA—traditional combinatorial auction; RMA—revenue maximizing auction; HBLA—highest bid lock auction).

Conclusion

We have presented two bidding strategies in recurrent auctions for perishable IoT resources: opportunistic and periodic bidding. We have shown that revenue obtained in TCA when bidders use these strategies is not optimal. It may cause market collapse with opportunistic bidding and low revenue with periodic bidding. We have devised two auction algorithms: RMA and HBLA and applied to those bidding strategies. We show that both RMA and HBLA substantially increase revenue in comparison to TCA under opportunistic bidding strategy while HBLA outperforms TCA in periodic bidding strategy. We conclude that HBLA performs best for the two bidder behaviors, thus being better suited for auctions for perishable IoT resources.

Footnotes

Handling Editor: Myungsik Yoo

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The work was supported by Ministry of Science and Technology.

References

Want

Schilit

Jenson

. Enabling the Internet of Things. Comput 2015; 48(1): 28–35.

Schreibenreif

. Digital businesses will compete and seek opportunity in the span of a moment. Technical report G00262735, 24 March 2014. Stamford, CT: Gartner, Inc.

Lopez

. Internet of things scenario: when things negotiate. Technical report G00219512, 11 January 2012. Stamford, CT: Gartner, Inc.

Cloud pricing: it’s (really) complicated, http://www.networkworld.com/article/2172538/cloud-computing/cloud-pricing–it-s–really–complicated.html

Wang

Ren

Meng

. When cloud meets eBay: towards effective pricing for cloud computing. In: Proceedings of the IEEE INFOCOM, Orlando, FL, 25–30 March 2012, pp.936–944. New York: IEEE.

Liang

Hsu

JYJ

Lin

. Auction-based resource access protocols in IoT service systems. In: Proceedings of the IEEE 7th international conference on service-oriented computing and applications, Matsue, Japan, 17–19 November 2014, pp.49–56. New York: IEEE.

Cramton

Shoham

Steinberg

. Combinatorial auctions. Cambridge, MA: The MIT Press, 2005.

Lee

Szymanski

. A participation incentive market mechanism for allocating heterogeneous network services. In: Proceedings of the IEEE global telecommunications conference, Honolulu, HI, 30 November–4 December 2009, pp.1–6. New York: IEEE.

Murillo

Muñoz

Busquets

et al . Schedule coordination through egalitarian recurrent multi-unit combinatorial auctions. Appl Intell 2011; 34(1): 47–63.

10.

Easley

Kleinberg

. Auctions (chapter 9). In: Easley

Kleinberg

(eds) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge: Cambridge University Press, 2010, pp.249–273.

11.

Chen

Wang

. SPARC: strategy-proof double auction for mobile participatory sensing. In: Proceedings of the international conference on cloud computing and big data, Fuzhou, China, 16–19 December 2013, pp.133–140. New York: IEEE.

12.

Zhu

Zhang

Zhu

et al . Towards truthful mechanisms for mobile crowdsourcing with dynamic smartphones. In: Proceedings of the IEEE 34th international conference on distributed computing systems, Madrid, 30 June–3 July 2014, pp.11–20. New York: IEEE.

13.

Sun

. Collection-behavior based multi-parameter posted pricing mechanism for crowd sensing. In: Proceedings of the IEEE international conference on communications, Sydney, NSW, Australia, 10–14 June 2014, pp.227–232. New York: IEEE.

14.

Lee

Szymanski

. Auctions as a dynamic pricing mechanism for e-services. In: Hsu

(ed.) Service enterprise integration, vol. 16. Boston, MA: Springer, 2007, pp.131–156.

15.

Murillo

López

Muñoz

et al . Fairness in recurrent auctions with competing markets and supply fluctuations. Comput Intell 2012; 28(1): 24–50.

16.

Gdowski

Safianowska

Huang

. Atlas: an agent based IoT platform for utilizing private device potential. In: Proceedings of the IEEE 11th VTS Asia Pacific wireless communication symposium, Ping-Tung Hsien, Taiwan, 28 August 2014. New York: IEEE.

17.

Safianowska

Gdowski

Huang

. Revenue maximizing auction for perishable IoT resources. In: Proceedings of the international conference on information and communication technology convergence, Jeju, South Korea, 19–21 October 2016, pp.417–422. New York: IEEE.

Preventing market collapse in auctions for perishable Internet of Things resources

Abstract

Keywords

Introduction

Related work

System model

Resources

Bidders

Opportunistic bidding strategy

Periodic bidding strategy

Auctioneer and winner determination

Opportunistic bidding strategy in TCA

Periodic bidding strategy in TCA

Winner determination algorithms for IoT

RMA

HBLA

Simulation and results

Simulation setup

Auctioneer and resources

Bidders

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References