An Equilibrium Analysis of a Secondary Mobile Data-Share Market

Abstract

Internet service providers are offering shared data plans where multiple users may buy and sell their overage data in a secondary market managed by the ISP. We propose a game-theoretic approach to a software-defined network for modeling this wireless data exchange market: a fully connected, non-cooperative network. We identify and define the rules for the underlying progressive second price (PSP) auction for the respective network and market structure. We allow for a single degree of statistical freedom—the reserve price—and show that the secondary data exchange market allows for greater flexibility in the acquisition decision making of mechanism design. We have designed a framework to optimize the strategy space using the elasticity of supply and demand. Wireless users are modeled as a distribution of buyers and sellers with normal incentives. Our derivation of a buyer-response strategy for wireless users based on second price market dynamics leads us to prove the existence of a balanced pricing scheme. We examine shifts in the market price function and prove that our network upholds the desired properties for optimization with respect to software-defined networks and prove the existence of a Nash equilibrium in the overlying non-cooperative game.

1. Introduction

We study an evolving non-cooperative real-time market. The changing demand of consumers operating on a wireless network has led companies to change their strategy towards data management and networking among wireless users. Mobile phone data experiences dynamically changing demand. Companies are beginning to measure, customize prices, and serve customers according to their individual demand in real time. Recently, AT&T has introduced a mobile data-sharing plan [1], which allows consumers to manage their own data usage in a real-time auction on a public platform managed by AT&T. In this work, we derive the Nash equilibrium by examining the resulting structure of this secondary data market. We address several topics: data as a product in the real-monetary market, and data as a network resource in a wireless topology.

As older softwares move from (wired) grid-based to node-based communication, a new paradigm of programmable network architectures is becoming the standard for wireless communication. These decentralized software-centric networks manage services modularly and allow for flexibility of demand; a decentralized design better suited to managing mobile networks, and mobility becomes a factor in network design. The relationship between the provider and the consumer is shifting; it is becoming a necessity to discretize consumer valuation. This is the new paradigm of digital economics.

There is a clear need for algorithms designed for optimization in this mobile space. Mobile devices provide flexibility, and may make individual decisions regarding local network infrastructure. In many cases, the direct communication between mobile devices allows for a simple mutation of classic optimization models. In online (web) resource allocation algorithms, auctions are used to implement the fair distribution of resources in network allocation algorithms. Mobile data is individually requested by each consumer as demand is unique to each mobile device. For the customer, they perceive a higher level of value for the service. For the ISP, progressive pricing allows for all customers to actively control, create, and share value. As stated by Izaret and Schürmann, “Making progressive pricing a …reality can happen only if firms change how they create, define, and measure value so that they can share it fairly.” [2].

An auction mechanism is defined as distributed when the allocations at any element depend only on local state, i.e., no single entity holds a global market knowledge. In [3], Lazar and Semret introduced the Distributed Progressive Second Price (PSP) Mechanism for bandwidth allocation, auction mechanisms that are (1) easily distributed, and (2) allocate an infinitely divisible resource. In classic mechanism design, with multiple user types, there is no single way to design the transformation from the direct revelation mechanism to its corresponding computational design. We apply a modifier to the PSP mechanism in order to mutate the strategy space, following the dynamics of user correspondence. As in [3], we obtain our result by design in composition with the PSP rules.

The secondary market provides a unique opportunity for social equilibrium, as it allows users to share data without sharing the same data plan, a restriction in most ISPs, such as [1]. We address the need for privacy in the bidding market; bid privacy is a concern for two reasons: (1) Sellers may use a buyer’s valuation to discriminate against a specific buyer(s), (2) an auctioneer might create a fake second highest bid slightly below the highest bid in order to increase his revenue. In general, the buyer does not trust the auctioneer. We therefore determine that our mechanism must be locally privacy preserving. By privacy preserving, we mean anonymous. That is, the winning bid in each local auction maintains anonymity, although the bid itself may be public information. In this way, consumers are able to trust the pricing scheme of the local auction and the resulting allocation.

To the best of our knowledge, this is the first work to provide a comprehensive derivation of a truthful mechanism that is self-contained within this specific dynamic market topology, the second price auction platform pioneered by AT&T. We focus on providing the existing auction platform with an incentive framework, and so rational users choose a collaborative exchange. In other words, adhering to the second-price rule, where price is derived from autonomous demand, we build “order” within the dynamic network of shifting demand and supply based on non-cooperative, autonomous consumers. This is the (built-in) transformation from the direct-revelation mechanism to the desired message space. Our auction mechanism may be described in game-theoretical terms as a pure-strategy progressive game with incomplete, but perfect, information.

The rest of of this paper is structured as follows: Section 2 presents the related work on auction theory and resulting policy software. Section 3 details the market derivation and mathematical form, which we present as an extension of the formulation found in [3]. The analysis of user behavior and the resulting algorithms that drive the non-cooperative game are presented in Section 4 along with a simple example. The analysis of the VCG properties and the network Nash equilibria are given in Section 5. Conclusions and Future Work follow in Section 6.

2. Related Work

Different definitions of social welfare define different auction strategies. Typical goals of optimization are the maximization of revenue and optimal allocation. Google AdWords allows advertisers to set their own prices by using an auction system where advertisers bid on keywords to get their ads placed in Google search results [2]. According to [2], progressive pricing, when used in combination with an auction platform, is a fairer way to determine prices. This is the “smart” pricing rule. We are used to understanding prices in units of data, or rates such as units of data per hour. If we can instead see prices in terms of a unit of value, then the price the customer pays can scale in proportion to the value demanded; this is our dynamic reserve price. Progressive second price auctions strive for this dynamic price in different ways, some try to optimize the sellers’ reserve price, or market price, as in this work. Research has been done for PSP auctions, and improvements have been made to the original work from Lazar and Semret. In [4], user strategy gives a “quantized” version of PSP, improving the rate of convergence of the game by shifting the bid price based on some threshold. Modifications to the mechanism that result in improved convergence also appear in [5], which relies on a global approximation function of demand.

Approximation of demand is a popular avenue of research for the division of data in a PSP auction. The complexity and amount of data inherent in digital data sharing creates a natural necessity; platforms must take advantage of the continuity of auctions restricted to simple sellers and buyers, as well as grid-based platforms. An approximation of the global demand function that uses a statistical approximation of the state space is derived from the theory of potential games. Potential games make use of a global strategy defined by the potential function; many companies use this as a mathematical tool to gather user data in order to further shape their market space. The idea of potential games in PSP markets was used by Zhong to coordinate the fair charging of electric vehicles in [6]; the potential game modeled the distribution of the load variance in electric vehicle charging, minimizing it as a global function with some constraints. The benefit of potential games is that, under some conditions, we are guaranteed convergence to a Nash equilibrium.

The analysis and interpretation of the data exchanged between the data-serve platform and the user quantify user value individually and strive to understand the decision process with increasing granularity. Usually, companies only know their marginal costs and can only infer user value by sample estimation. Today, with pervasive data and increasingly precise analytical capabilities, companies can derive a more precise estimate of value per user, and still maintain a zero marginal cost. Recently, using a mobile app as a platform,  Ref. [7] assigns electric vehicles to charging stations, replacing a first-come-first-serve system, and ensuring that there is enough power assigned to keep each user satisfied without overloading the supply. Importantly,  Ref. [7] considers the individual valuations of the users. More generally,  Ref. [8] defines an optimal strategy for buyers and brokers using a game-theoretic derivation, and further shows the existence of network-wide market equilibria obtained by the specific provisioning of this network given specific network dynamics. Indeed, various equilibria may be derived by designing the structure of provisioning in distributed systems, motivated by individual users interests. The continuity of data supplied by the customer demand allows for the continuity of change to the pricing system of the data-serve platform. By allowing a user preference to, loosely, represent a policy, we may interpret a user preference from the data exchange market as a plan to allow users to set their own policies, and rely on the existing framework to implement their preferences. Game-theoretical analysis of mobile data has been presented in [9] as a framework for mobile-data offloading.

This new type of provisioning is described as virtual elasticity in [10], a paper that has recently provided an innovative way to estimate future prices, an avenue of research that is of great interest to the marketing community. The estimation of future prices is difficult in PSP auctions, due to the dynamically changing bids. However, an estimation of future demand (price) can greatly affect the efficiency of the provisioning system, particularly with static resources, such as computer memory.

Finally, we mention that the concern of privacy is addressed in [11]. This paper addresses the problem of privacy between the web user and the advertiser, which is beyond the scope of this paper. However, we mention that the issue of privacy can change based on the platform, and the extent to which we have implemented data privacy, through anonymous bids, may not be sufficient. Our analysis is largely based on the work of [12] and his examination of second price auctions in networked settings. In particular, we make use of the assumption of consistent bids, in the special case where consistent bidding is an optimal solution, i.e., a Nash equilibrium.

3. Market Formulation and Definitions

3.1. The Market Mechanism

We aim to design a distributed PSP auction, operating within a strategic framework that determines the bidding behavior of users in a wireless network. The auction design must must meet a certain set of known criteria: (1) truthfulness, (2) individual rationality/selfishness, (3) social welfare maximization, and (4) an anonymous winning bid. For the secondary data exchange market, we determine that the strategy space must meet additional criteria: (5) privacy and independence from the ISP, (6) locally fair division, and (7) minimize crossover in buyer/seller pools. In second-price markets, the winning bid does not pay the winning bid price, but the price from next lowest bid. This provides the market with the property of truthfulness through incentive compatibility, meaning that a bidder will truthfully reveal its valuation of the resource. The exclusion-compensation principle, or Pareto criterion, is built into the pricing mechanism, and guarantees that at equilibrium, any change to the system would make at least one user worse-off.

Let the set of all wireless users be labeled by the index set $\mathcal{I}=\{1,\cdots ,I\}$. In our current formulation, we do not allow a seller to host multiple auctions, and so we may assume that data is a unary resource belonging to the seller, and identify each local auction with the index of the seller $j\in \mathcal{I}$. The bid profiles of the users are given as, $s\equiv \left[s_i^j\right]$ where $(i,j)\in \mathcal{I}\times \mathcal{I}$. We assume that all inactive bids are zeroed, i.e., if there is no interaction between two players i and j, then $(i,j)=0$. Then, $\mathcal{I}\times \mathcal{I}$ is a matrix, with each element of the matrix representing a single buyer-seller interaction, one projective representation of the space. The matrix allows for ease in our analysis by vectorizing the space, and represents a single snapshot of a static system, all quantities and prices are fixed. We call this space S, as in standard game-theoretic notation, and so the (full) strategy space for buyer i as all possible bids at all auctions: $S_i={\Pi }_{j\in \mathcal{I}}{S}_i^j$, and $S_{-i}={\Pi }_{j\in \mathcal{I}}\left({\Pi }_{k\ne i\in \mathcal{I}}{S}_k^j\right)$ as the associated opponent profiles.

The grid(s) of bid profiles, s, represents the statistical distribution of player types and corresponding actions, the userwise distributed state of actions in the secondary market. We will use the context of the bid to indicate the user type as well as the notation: $s_i$ is a buyer’s bid, $s_{-i}\equiv {[s_1^j,\cdots ,s_{i-1}^j,s_{i+1}^j,\cdots ,s_I^j]}_{j\in \mathcal{I}}$ is the profile of user i’s opponents, and $s^j$ a seller’s local auction. We describe the rules as follows:

• The bid is represented by $s_i^j=(d_i^j,p_i^j)$, indicating that i would like to buy from j a quantity $d_i^j$ and is willing to pay a unit price $p_i^j$.
• The auction platform maintains and updates all bids.
• $s_i^j>0$ represents an active bid in s, with bid, $s_i^j=(d_i^j,p_i^j)$.
• A buyer that does not submit a bid, i.e., $s_i^j=0$, will not receive opponent profiles from seller j.
• A seller’s profile $\left[s_i\right]$ is comprised of buyers in auction j, and a buyer’s profile $\left[s^j\right]$ a set of auctions in which the buyer holds active bids.

We will assume that a buyer’s budget is sufficient, as the alternative would be to pay a higher price to the ISP.

3.2. Market Incentive

As a market with perfect with incomplete information, we determine that sellers can only gain information about the market by observing buyer behavior in their local auction. Buyers are able to see the sellers reserve price for each market in which they bid. The reserve price of each auction is determined by the valuations of the buyers, that is, the seller takes a passive, or reactive role, and modifies its reserve price according to market demand. Thus the buyer is able to determine the state of the market through the reserve price of its active auctions, and so may be able to infer some behavior resulting from opponent bid profiles. Our analysis focuses the role of buyers, who are able to directly influence global market dynamics. Each buyer i will have information from each seller j, as well as opponent profiles $s_{-i}$, from each auction in which it is participating. In the extreme case, where i submits bids to all auctions $j\in \mathcal{I}$, buyer i gains access all buyer profiles, $[s_1,\cdots ,s_I]$ for each auction j.

Define the set of sellers chosen by buyer $i\in \mathcal{I}$ as,

$${\mathcal{I}}_i\left(n\right)=\underset{{\mathcal{I}}^{\prime }\subset \mathcal{I},\left|{\mathcal{I}}^{\prime }\right|=n}{arg\; max}\sum _{j\in {\mathcal{I}}^{\prime }}{D}^j,$$

and similarly, for a seller $j\in \mathcal{I}$, we define the set of buyers participating in auction j as,

$${\mathcal{I}}^j\left(m\right)=\underset{{\mathcal{I}}^{\prime }\subset \mathcal{I},\left|{\mathcal{I}}^{\prime }\right|=m}{arg\; max}\sum _{i\in {\mathcal{I}}^{\prime }}{p}_i^j,$$

where $m,n\in \mathcal{I}$.

We now must determine a function which regulates the behavior of the buyers in our dynamic market. We define an opt-out function, ${\sigma }_i$, associated with a buyer i as part of its type. Buyer i, when determining how to acquire a possible allocation a, will determine its bid quantities by,

$${\sigma }_i\left(a\right)={\left[{\sigma }_i^j\left(a\right)\right]}_{j\in \mathcal{I}}.$$

(1)

In a general sense, ${\sigma }_i$ applies the PSP rules to our user strategy. The rules presented here incorporate the opt-out function with the auction mechanism. The market price function, $P_i$, for a buyer in the secondary market is:

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill & {\displaystyle P_i(z,s_{-i})=\sum _{j\in \mathcal{I}}{\sigma }_i^j\circ p_i^j(z_i^j,s_{-i}^j)}\hfill \\ \hfill & =\sum _{j\in \mathcal{I}}\left(inf\left\{y\ge 0:d_i^j(y,s_{-i}^j)\ge {\sigma }_i^j\left(z\right)\right\}\right),\hfill \end{array}\end{array}$$

(2)

which we interpret as the aggregate of minimum prices that buyer i bids in order to obtain data amount z given opponent profile $s_{-i}$. The maximum available quantity of data in auction j at unit price y given $s_{-i}^j$ is given as:

$$d_i^j(y,s_{-i}^j)={\sigma }_i^j\circ d_i^j(y,s_{-i}^j)={\left[D^j-\sum _{p_k^j>y}{\sigma }_k^j\left(a\right)\right]}^{+}.$$

(3)

It follows from the upper-semicontinuity of $D_i^j$ that for $s_{-i}^j$ fixed, $\forall y,z\ge 0$,

$${\sigma }_i^j\left(z\right)\le {\sigma }_i^j\circ d_i^j(y,s_{-i}^j)\iff y\ge {\sigma }_i^j\circ p_i^j(z,s_{-i}^j).$$

(4)

The data allocation rule is a function of the local market interactions between buyers and sellers over all local auctions, as is composed with i’s opt-out value, so that for each $i\in \mathcal{I}$, the allocation from auction j is,

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill a_i^j(s)& ={\sigma }_i^j\circ a_i^j\left(s\right)\hfill \\ \hfill & =min\left\{{\sigma }_i^j\left(a\right),\frac{{\sigma }_i^j\left(a\right)}{{\displaystyle \sum _{p_k^j=p_i^j}{\sigma }_k^j\left(a\right)}}{d}_i^j(p_i^j,s_{-i}^j)\right\}.\hfill \end{array}\end{array}$$

(5)

Remark 1.

The bid quantity ${\sigma }_i^j\left(a\right)$ and the allocation $a_i^j$ are complementary.

Finally, we must have that the cost function.

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill c_i\left(s\right)& {\displaystyle =\sum _{j\in \mathcal{I}}{p}_i^j\left(a_i^j(0;s_{-i}^j)-a_i^j(s_i^j;s_{-i}^j)\right).}\hfill \end{array}\end{array}$$

(6)

The cost to buyer i adds up the willingness of all buyers excluded by player i to pay for quantity $a_i^j$, i.e.,

$${\displaystyle c_i^j\left(s\right)={\int }_0^{a_i^j}{p}_i^j(z,s_{-i}^j)dz.}$$

This is the “social opportunity cost” of the PSP pricing rule.

3.3. The Anonymity Problem

The PSP auction given in [3] is comprised of a set of simple and symmetric rules that closely follow market theory, and as it is distributed we require privacy to be computed on an individual basis, each user must be able to confirm its own anonymity. We describe the process as given in [13]. In general, a distributed computation, where buyer i is part of a coalition comprising auction j, is as follows:

Denoting $m_{-i}={[(s_i^j,r_i),m_1,\cdots ,m_n]}_{k\ne i\in \mathcal{I}}$, buyer sends a message to each of its opponents, where $s_i^j$ is i’s bid, $r_i$ is an independent random value, and $m_1,\cdots ,m_n$ the messages i has received so far. Then, all buyers are able to confirm the winning bid $s_{\overline{i}}^{*}$. It was proven in [13] that full privacy is not possible in a second price auction, even if we allow partial revelation and weak coalitions. We propose anonymity, in the winning bid only.

3.3.1. Buyers Are Anonymous

In our secondary market, we have that any local auction is anonymous by definition, as a permutation of the valuations results in a permutation of allocations and prices, equivalently, exchanging the bids of two losing buyers does not change the auction’s result. Formally,

Definition 1

((Anonymous auction) [13]). Given an auction j and buyers $i\in \mathcal{I}$, a protocol for computing $max\{i\in \mathcal{I}:p_i^j\ge p_k^j\forall k\in \mathcal{I}\}$ if for all coalitions $T\subset \mathcal{I}$, any pair of inputs $x=[s_1^j,\cdots ,s_I^j],\xi$, so that ξ is a permutation of x, $\forall i\in T:x_i={\xi }_i$, and $max\left(\right)$, and any choice of random inputs ${\left\{r_i\right\}}_{i\in T}$. Let $\overline{T}=T\times \mathcal{I}\backslash T$,

$$Pr\left({[x,{\left\{r_i\right\}}_{i\in T}]}_{x\in }|{\left\{r_i\right\}}_{i\in T}\right)$$

$$=Pr\left({[\xi ,{\left\{r_i\right\}}_{i\in T}]}_{\xi \in T\times \mathcal{I}\backslash T}|{\left\{r_i\right\}}_{i\in T}\right)),$$

which states that any two inputs, the messages seen by coalition T are identically distributed.

3.3.2. The Winning Bid Is Trusted (Anonymous) Information

We claim that a buyer’s trust in a local auction is fulfilled when the outcome of the auction is guaranteed to be correct, and if the winner’s identity remains private information. For each local auction, we define a coalition to be the participating buyers. The winning bidder is chosen by distributed computation via homomorphic encryption. We present the Lemma in its general form,

Lemma 1

(Benaloh 1987). $f(x_1,x_2,\cdots ,x_n)={\sum }_{i=1}^n{x}_{i}modp$ is privately computable.

Thus, it is possible to anonymously compute,

$$\omega =max\left({\left[p_i^j\right]}_{i\in {\mathcal{I}}^j}\right)=(p_1^j,p_2^j,\cdots ,p_n^j,arg\; max\left(p^j\right)).$$

(7)

Algorithm 1 presents the procedure determining the winner of auction j for some fixed time in the bid progression, where $D^j>0$.

Algorithm 1 Max bid private computation.

1: $\omega \leftarrow 1,e\leftarrow 0$ 2: while $e\le 1$do 3:  for $i\in {\mathcal{I}}^j$ do 4:   if $p_i^j\le \omega$ then 5:    $p_i^j\leftarrow 1$ 6:   else 7:    $p_i^j\leftarrow 0$ 8:   end if 9:  end for 10:  $e={\sum }_{i\in {\mathcal{I}}^j}{p}_i^{j}mod(n+1)$ (Lemma 1) 11:  for $i\in {\mathcal{I}}^j$ do 12:   if $p_i^j\ge e$ then return $i\left(winner\right)$ 13:   end if 14:  end for 15: end while

The winning buyer then leaves the auction, and so we have that the privacy of the winning buyer is persistent. We note that it is possible for a winner to anonymously rejoin an auction; however, this does not alter our result. At time $t=0$, a seller j entering the market will submit bid $s_{\kappa }^j=(D^j,ϵ)$ to the public data exchange platform, and so the initial bid $s_{\kappa }^j$, is public knowledge. The auction begins at time $t>0$, and at $t=0$, j will initializing its reserve price by executing a single bid iteration.

We will assume that the cost of participating in the secondary market is absorbed by the bid fee, which could represent data used in submitting bids, or a fee charged per unit of data, or a flat rate charged at the completion of the purchase. We do not model ISP revenue, but assume it may be extracted from the bid fee at $t=0$.

The formulation is inspired to the thinnest allocation route for bandwidth given in [3]. We note that if a single seller j can satisfy i’s demand, then (8) reduces to the original form, defined in [12] as “a simple buyer at a single resource element”.

3.3.3. Truthfulness (Incentive Compatibility)

We will prove that the dominant strategy for buyers is to submit coordinated bids, where all bids the buyer submits are equal. Our motivation for coordinated bids comes from the idea of potential games. In potential games, the incentive of all users to change strategy can be expressed as a single global function. We map the incentive of a buyer over all auctions $j\in \mathcal{I}$ to a single potential function. This is a standard method that is used often, as it simplifies the analysis of both strategy and auction design. Thus, our strategic bid is an $ϵ$-best response. The necessary condition of an $ϵ$-best reply is that the new bid price must differ from the last by at least $ϵ$. Now, an $ϵ$-best reply for user i is $p_i^{*}={\theta }_i^{\prime }\left({\sigma }_i\left(a\right)\right)+ϵ$, for a given opponent profile $s_{-i}$, and for each $j\in {\mathcal{I}}_i$. Now, as $ϵ$ is the bid fee, we have that $p_i^j$ is equal to the marginal valuation of player i in auction j, and so incentive compatibility holds.

4. Strategic Framework

4.1. User Valuation (Strategic Incentive)

In any market, a buyer or seller would like to obtain the maximum amount of utility possible while staying within budget. The buyer’s utility maximizes the amount of data allocated by the seller, while the seller’s utility maximizes the cost of the data sold. We illustrate the resulting product space for the buyer in Figure 1.

The level, or price associated with the buyer’s bid may be projected onto a line. As we will show, this holds when buyers use the same bid price for all non-zero bids. The projection, or the amount of data requested, is a plane, since buyers may bid in more than one auction. Clearly, the allocation is the product of the price and the data request. The resulting step function is convex. We define a move to a better market position to be synonymous with a strategic bid.

Remark 2.

The terms “bid” and “strategy” are often interchangeable, from auction design and game theory, respectively.

Our mechanism allows a buyer to opt-out of auctions by submitting zero bids. This strategy maximizes utility while minimizing the number of positive bids submitted to the overall market. We define each buyer as a user $i\in \mathcal{I}$ with quasi-linear utility function $u_i={\left[u_i^j\right]}_{j\in \mathcal{I}}$, a buyers’ utility function is of the form,

$$u_i={\theta }_i\circ {\sigma }_i\left(a\right)-c_i,$$

(8)

where the composition of the elastic valuation function ${\theta }_i$ with ${\sigma }_i$ distributes a buyers’ valuation of data allocation a across local markets (and thus multiple sellers). The composition map (the codomain of ${\theta }_i\left({\sigma }_i\right)$ is the same as the domain of ${\sigma }_i\left(a\right)$) and restricts the buyer’s domain to minimize $d^j{p}^j-c_i$ and so maximize $u_i$. We formally extend the PSP rules described in [12] to determine the presence of equilibria across fully connected subsets of local data-exchange markets. By fully connected, we mean that the market subset maintains its own equilibrium without the influence of any other data-exchange (any other auction). The sellers, $j\in \mathcal{I}$ are not associated with an opt-out function. The sellers’ strategy can only be to determine the reserve price of their local auction, using only information from buyers who have not opted out.

Remark 3.

It is possible that a seller would be able to derive information about other auctions by examining buyer bids over time, particularly if the seller had knowledge of the buyer strategy. In this work, we assume sellers are unable to derive opponent information from buyer bids.

Elastic valuation functions allow for even infinitesimal changes in the market dynamics to be modeled. We give the definition for an elastic valuation function as in [3].

Definition 2

(Elastic demand [3]). A real valued function, $\theta (·):[0,\infty )\to [0,\infty )$, is an (elastic) valuation function on $[0,D]$ if

• $\theta \left(0\right)=0$,
• θ is differentiable,
• ${\theta }^{\prime }\ge 0$, and ${{\theta }_i}^{\prime }$ is non-increasing and continuous,
• There exists $\gamma >0$, such that for all $z\in [0,D]$, ${\theta }^{\prime }\left(z\right)>0$ implies that for all $\eta \in [0,z),{\theta }^{\prime }\left(z\right)\le {\theta }^{\prime }\left(\eta \right)-\gamma (z-\eta )$.

The elastic valuation of users and homogeneous nature of data in the secondary market allows for continuity in the constraints imposed by the user strategies. We begin our analysis with buyer valuation ${\theta }_i$. A buyers’ valuation of an amount of data represents how much a buyer is willing to pay for that amount. This is equivalent to the bid price, given a fixed amount of data, satisfying ${\theta }_i$. We determine the buyers’ utility-maximizing bid given quantity $z\ge 0$ to be a mapping to the lowest possible unit price. We have,

$$f_i\left(z\right)\triangleq inf\left\{y\ge 0:{\rho }_i\left(y\right)\ge z,\forall j\in \mathcal{I}\right\},$$

(9)

where ${\rho }_i\left(y\right)$ represents the demand function of buyer i at bid price $y\ge 0$, and gives the quantity that buyer i would buy at a given price. We determine that the market supply function corresponds to an extreme of possible buyer demand, and acts as an “inverse” function of $f_i$. We have, for bid price $y\ge 0$,

$${\rho }_i\left(y\right)=\sum _{j\in \mathcal{I}:p_i^j\ge y}{D}^j.$$

(10)

We note that $f_i$ is such that i could still bid in any auction $j\in \mathcal{I}$. Therefore, the utility-maximizing bid price is the lowest unit cost of the buyer to participate in all auctions, and corresponds to the maximum reserve price amongst the sellers.

From the perspective of the seller we have a more direct interpretation of valuation as revenue. We determine the demand function of seller j at reserve price $y\ge 0$ to be,

$${\rho }^j\left(y\right)=\sum _{i\in \mathcal{I}:p_i^j\ge y}{\sigma }_i^j\left(a\right),$$

(11)

and define the “inverse” of the buyer demand function for seller j as potential revenue at unit price y, we have,

$$f^j\left(z\right)\triangleq sup\left\{y\ge 0:{\rho }^j\left(y\right)\ge z,\forall i\in \mathcal{I}\right\},$$

(12)

and, unsurprisingly, $f^j$ maps quantity z to the highest possible unit data price.

The valuation of any user must be modeled as a function of the entire marketplace. Naturally, a buyers’ valuation is aggregated over local markets, and the sellers’ valuation is aggregated over its own auction. We have already introduced the composition ${\theta }_i\circ {\sigma }_i$ as the valuation of the buyers. We further show that user valuation satisfies the conditions for an elastic demand function, with valuations based on (11) and (12). We first note that, in general (and so we omit the subscript/superscript notation), the valuation of data quantity $x\ge 0$ is given by,

$$\theta \left(x\right)={\int }_0^{x}f\left(z\right)dz,$$

as in [12]. Now, we have the following Lemma,

Lemma 2

(User valuation). For any buyer $i\in \mathcal{I}$, the valuation of a potential allocation a is,

$${\displaystyle {\theta }_i\circ {\sigma }_i\left(a\right)=\sum _{j\in \mathcal{I}}{\int }_0^{{\sigma }_i^j\left(a\right)}{f}_i\left(z\right)dz.}$$

(13)

Now, we may define seller j’s valuation in terms of revenue,

$${\displaystyle {\theta }^j=\sum _{i\in \mathcal{I}}{\theta }^j\circ {\sigma }_i^j\left(a\right)=\sum _{i\in \mathcal{I}}{\int }_0^{{\sigma }_i^j\left(a\right)}{f}^j\left(z\right)dz.}$$

(14)

We have that ${\theta }_i$ and ${\theta }^j$ are elastic valuation functions, with derivatives ${\theta }_i$ and ${{\theta }^j}^{\prime }$ satisfying the conditions of elastic demand.

Proof. 

Let $\xi$ be a unit of data from buyer bid quantity ${\sigma }_i^j\left(a\right)$. If $\xi$ decreases by incremental amount x, then seller bid $d_i^j$ must similarly decrease. The lost potential revenue for seller j is the price of the unit times the quantity decreased, by definition, $f^j\left(\xi \right)x$, and so,

$${\theta }^j\left(\xi \right)-{\theta }^j(\xi -x)=f^j\left(\xi \right)x.$$

Thus (14) holds. As we may use the same argument for (13), as such, we will denote $f_i=f^j=f$ for the remainder of the proof. We observe that the function f is the first derivative of the valuation function with respect to quantity. Letting ${\theta }_i={\theta }^j=\theta$, the existence of the derivative implies $\theta$ is continuous, and therefore, in this context, f represents the marginal valuation of the user, ${\theta }^{\prime }$. Also, clearly $\theta \left(0\right)=\theta \left(\sigma \right(0\left)\right)=0$. Now, as we consider data to be an infinitely divisible resource, we have a continuous interval between allocations a and b, where $a\le b$. Now, as $\theta$ is continuous, for some $c\in [a,b]$,

$${\theta }^{\prime }\left(c\right)=\underset{x\to c}{lim}\frac{\theta \left(x\right)-\theta \left(c\right)}{x-c}=f\left(c\right),$$

and so $f={\theta }^{\prime }$ is continuous at $c\in [a,b]$, and so as $a\ge 0$, ${\theta }^{\prime }\ge 0$. Finally, we have that concavity follows from the demand function. Then, as ${\theta }^{\prime }$ is non-increasing, we may denote its derivative $\gamma \le 0$, and taking the derivative of the Taylor approximation, we have, ${\theta }^{\prime }\left(z\right)\le {\theta }^{\prime }\left(\eta \right)+\gamma (z-\eta )$.    □

The sellers’ natural utility is the potential profit, or simply $u^j={\theta }^j$, where we have chosen to omit the original cost of the data paid to the ISP, as it is not a component of our mechanism, and as a discussion of mobile data plans is outside the scope of this paper. Now, a rational user will try to maximize its utility, thus, user incentive manifests as a response to market dynamics. A buyer has the choice to opt-out of any auction, and as a seller will try to sell the maximum amount of data, the highest possible reserve price is conditioned by “natural” constraints. Utility-maximization acts as revenue maximization for a rational seller, and as cost minimization for a rational buyer. Thus, for each user $p_i^j\ge min(p_i^j)$ and $p_i^j\le max(p_i^j)$, which holds $\forall i,j\in \mathcal{I}$ such that $s_i^j>0$. Now, rational buyer does not want to purchase extra data, as this would be equivalent to overpaying, however i submits positive bids to a set of sellers, and a rational seller will attempt to maximize profit, and so will try and sell all of its data. Therefore,

$${\displaystyle \sum _{i\in \mathcal{I}}{\sigma }_i^j\left(a\right)\ge D^j\mathrm{and}\sum _{j\in \mathcal{I}}{d}_i^j\ge D_i,}$$

(15)

which holds $\forall i,j\in \mathcal{I}$. We will assume that buyers and sellers do not overbid, and so omit this constraint from our formulation. Thus, at equilibrium all users are satisfied, and $D^j=D_i$, although we observe that this result does not imply that $s_i=s^j$.

Finally, it is worth mention that the analysis of the auction as a game assumes some forms of demand and supply, in order to derive properties. The mechanism itself does not require any knowledge of user demand or valuation.

4.2. User Behavior

The user local strategy space is non-deterministic: the preferences of users are subject to change, determinations and predictions are based on the binary dependence of the variables. Arrow’s Theorem states that no deterministic strategy can provide a mapping of the preferences of users into a market-wide (complete and transitive) strategy. As individual bids cannot map to a general objective, a better market position can only be determined by an adaptive strategy. We will address the market risks and securities in our secondary data exchange market, and provide a game-theoretic model of a real market progression, which we then use to derive, and then define, adaptive variables.

Assuming equal bandwidth for all users, we derive a globally optimal strategy suited for users with local information in a distributed data-sharing model. In a multi-auction market, each auction a buyer joins has the possibility of decreasing the potential cost of its data. However, increasing the size of the auction implies a certain risk, which we may interpret as a definite liability. Increasing the number of transactions causes additional messaging overhead, fees, and increased competition from other buyers. A transaction also causes potential indirect costs, which may be considered work done to find sellers, or effort of communication from participation. A seller has the potential for greater profit with each new buyer in its auction, taking the same risk. To simplify our analysis, here the liability of any user is naturally absorbed into the bid fee $ϵ$, as in [12]. Therefore, according to our interpretation, the bid fee is dependent on the association between two users and their market positions, in addition to the underlying network structure. Now, both sellers and buyers must consider the cost of adding additional users to their subsequent pools.

Buyer i’s seller pool is determined by minimizing n, and is the smallest set of sellers that allows for a coordinated bid, and the aggregate bids satisfy its demand, $D_i$.

$$\min \{n\in \mathcal{I}|n{D}^n\ge D_i\}.$$

(16)

Similarly, seller j determines the minimal set of buyers that maximizes revenue and sells all of its data, $D^j$.

$${\displaystyle min\left\{m\in \mathcal{I}|\sum _{i\in {\mathcal{I}}^j\left(m\right)}{d}_i^j\ge D^j\right\},}$$

(17)

We further determine that the set of buyers and sellers participating in a single equilibrium is bounded by the potential indirect costs of participation. We will denote this individual cost to each user as $\varrho$. The indirect cost is the portion of the bid fee $ϵ$ that is dependent on the underlying network and the individual. Observing that $\varrho$ indirectly effects user utility, and therefore acts to establish a natural budget for each user. We define this constraint as,

$$u\le \varrho ,$$

(18)

which may be interpreted as the effort a rational user is willing to expend on its message space, and serves to limit the size of the buyer/seller pools. This information may be collected from a specific device’s configuration, i.e., enabled roaming, daily data restrictions. It is clear that an unconstrained market, even with a finite number of users, could suffer from the expense of many local auctions trading an infinitely divisible resource, thus $\varrho$ is interpreted as the “liability” component of $ϵ$, and attempts to regulate network congestion.

4.2.1. Buyer Strategy

Although it is possible for a seller to fully satisfy a buyer i’s demand, it is also reasonable to expect that a seller may come close to using their entire data cap, and only sell the fractional overage. In this case, a buyer must split its bid among multiple sellers. The buyer strategy bids in auctions with the highest quantities first, a natural exploitation of the demand curve. A new seller entering the market with a large quantity of data will be in high demand. This behavior contributes to market price stability, as seller valuation is determined by buyer demand, the buyer strategy tends towards equal valuation of all local markets, and therefore similar prices. If a buyers’ demand is not satisfied, they will need to bid in markets with smaller data quantities, and so will bid on a larger portion of the sellers’ bid quantity, increasing their unit price. We define $j^{*}=n\le I$ represent the seller with the least amount of data $\in {\mathcal{I}}_i$, i.e., $D^{j^{*}}\le D^j,\forall j\in {\mathcal{I}}^j$. We define the composition,

$${\sigma }_i^j\circ a={\sigma }_i^j\left(a\right)=\frac{a_i^j}{|{\mathcal{I}}_i|},$$

to be the buyer strategy with respect to quantity for all sellers $j\in {\mathcal{I}}_i$. We propose the following strategy.

Lemma 3

(Opt-out buyer strategy). Let $i\in \mathcal{I}$ be a buyer and fix all other buyers’ bids $s_{-i}$ at time $t>0$, and let a be i’s desired allocation. Define,

$${\sigma }_i^j\left(a\right)\triangleq \left\{\begin{array}{c}{\sigma }_i^{j^{*}}\left(a\right),j\in {\mathcal{I}}^j,\hfill \\ 0,j\ni {\mathcal{I}}^j.\hfill \end{array}\right.$$

(19)

and bid price $p_i^j={\theta }_i^{\prime }\left({\sigma }_i^j\left(a\right)\right)$. Now, (19) holds $\forall j\in \mathcal{I}$.

Each time step, $s^j$, the vector of bids held by auction j, is updated and is shared with all participating buyers. At this point buyers have the opportunity to bid again, where a buyer that does not bid again is assumed to hold the same bid, since a buyer dropping out of the auction will set their bid to $s_i^j=(0,0)$. The implementation of the Opt-out buyer strategy is presented in Algorithm 2.

Proof. 

We assume that a buyer will try and fill their data requirement. In the case that there exists a seller who can completely satisfy a buyers’ demand, $j^{*}=1$, $|{\mathcal{I}}_i|=1$ and (16) holds. If such a buyer does not exist, as the set ${\mathcal{I}}_i$ is ordered by the quantity of the sellers’ bids, i may discover $j^{*}$ by computing ${\mathcal{I}}_i$. Suppose that $D_i>{\sum }_{j\in \mathcal{I}}{D}^j$, then $j^{*}>I$ and ${\mathcal{I}}_i=Ø$. We model the ISP at time $t>0$ as a seller $\kappa$ with bid $s^{\kappa }=(d^{\kappa },p^{\kappa })$, where $d^{\kappa }>D^j,\forall j\in {\mathcal{I}}_i$, and $p^{\kappa }$ represents the price for data set by the ISP, which we note is also the upper bound of the sellers’ pricing function. We note that in [14] this cost is the data overage fee. Consider some $k\ne i\in \mathcal{I}$ where $p_i^j=p_k^j$. The allocation rule (5) determines that the data will be split proportionally between all buyers with the same unit price. It is possible that the resulting partial allocation of data to i and k would not satisfy some demand. As the two cases i and k are the same, we will only consider one. Suppose seller j updates its bid to reflect the new data quantity, where $d_i^{j(t+1)}<{\sigma }_i^{j\left(t\right)}\left(a\right)$. First, i sets its bid to $s_i^j=0$, and from the new subset ${\mathcal{I}}_i$, submits bids until ${\sum }_{j\in {\mathcal{I}}_i}\sigma {\left(a\right)}_i^j\ge D_i$, by (15). Now, we consider the case where a new buyer k with bid price $p_k^j>p_i^j$ for some $j\in {\mathcal{I}}_i$, in other words, a new buyer k may enter the market with a better price, decreasing the value of i’s bid for $j\in {\mathcal{I}}_i$. In this case, by (16), i will choose ${\mathcal{I}}_i$ so that, ${\sigma }_i^{j(t+1)}\left(a\right)={\sigma }_i^{j\left(t\right)}\left(a\right)-{\sigma }_k^{j\left(t\right)}\left(a\right)$, and so ${\mathcal{I}}_i$ is large enough to balance the additional demand from k. Finally, we consider the case where $|{\mathcal{I}}^j|=I$, where the demand of buyer i exceeds the supply, and the case where ${\sigma }_i\left(\varrho \right)>{\theta }_i\left({\sigma }_i\left(a\right)\right)$, where the overhead exceeds the current valuation of the data. Then, by (9), the valuation of the data increases until either the demand is satisfied, the debit from the overhead costs are balanced (18), or the upper bound of the sellers’ reserve price $p^{\kappa }$ is reached. Thus, as in each case we have that i is able to satisfy their demand, and we determine that the opt-out strategy is optimal.    □

Finally, we note that ${\mathcal{I}}_i$ is not the only possible minimum subset $\in \mathcal{I}$ able to satisfy i’s demand, in fact, by restricting the size of the set ${\mathcal{I}}_i$, we would be able to improve the computation time of buyer i, at the cost of increasing the price.

Algorithm 2 Buyer response.

1: $p_{i\left(0\right)}\leftarrow ϵ$, $s_{i\left(0\right)}\leftarrow (p_i,D_i)$, $D_t\leftarrow D_i$, compute ${\mathcal{I}}_{i\left(0\right)}$ 2: Update $s_i$ 3: while$D_i\left(t\right)>0$do 4:  $D_{i(t+1)}^j\leftarrow {\sum }_{j\in {\mathcal{I}}_i}{\sigma }_i^{j\left(t\right)}\left(a\right)$ 5:  if $D_{i(t+1)}^j<D_t$ then 6:   Compute ${\mathcal{I}}_{i\left(t\right)}$ 7:   $p_i\leftarrow {\theta }_i\left({\sigma }_i\left(a\right)\right)$ 8:  end if 9:  $s_{i(t+1)}\leftarrow ({\sigma }_i\left(a\right),p_i)$ 10:  Update $s_i$ 11:  $D_{i(t+1)}^j\leftarrow D_{i\left(t\right)}^j$ 12:  $t\leftarrow t+1$ 13: end while

4.2.2. Seller Strategy

We define the reserve price for seller j as,

$$p_{*}^j=p_{i^{*}}^j+ϵ,$$

(20)

where $i^{*}$ is the highest losing bidder with respect to bid price. We claim that the choice of reserve price $p_{*}^j$ does not force any buyers out of the local auction. In order to maximize revenue, the seller must also be able to respond dynamically to strategic bids. In order to do this, we determine that the seller may modify its reserve price in response to the changing market dynamics.

Define any auction duration to be $\tau \in [0,\infty )$. We will show that sellers are able to maximize revenue in restricted subset of buyers in $\mathcal{I}$, and as such will attempt to facilitate a local market equilibrium for this subset. A local auction j converges when $\forall i\in \mathcal{I}$, $s_i^{j(t+1)}=s_i^{j\left(t\right)}$, at which point the allocation is stable, the data is sold, and the auction ends. In the sellers’ local environment, we determine that the best course of action is to maximize revenue, and then try to keep its buyer pool stable until convergence occurs.

Lemma 4

(Localized seller strategy (i.e., progressive allocation)). For any seller j, fix all other bids ${\left[s_i^k\right]}_{i,k\ne j\in \mathcal{I}}$ at time $t>0\in \tau$. For each $t\in \tau$, let $\omega \left(t\right)$ be given by (7), and perform the update,

$$D^{j(t+1)}=D^{j\left(t\right)}-{\sigma }_{\omega \left(t\right)}^{j\left(t\right)}\left(a\right).$$

(21)

Allowing t to range over τ, we have that $D^j=0$, and a local market equilibrium.

Consider a user purchasing data from a subset of other network users. The sellers’ auction will function as follows: at each bid iteration all buyers submit bids, and the winning bid is the buyer i that has the highest price $p_i^j$. The seller allocates data to this winner, at which point all other buyers are able to bid again, and the winner leaves the auction (or equivalently, maintain their bid). The auction progresses as such until all the sellers’ data has been allocated. The seller progressive allocation algorithm is given in Algorithm 3.

Proof. 

We assume that the seller will try to maximize its revenue. In the case where $|{\mathcal{I}}^j|=1$, then if ${\sigma }_i^j\left(a\right)=D^j$, then j’s market is at equilibrium. Otherwise, we arrive at the case of multiple buyers, which we note includes the case where ${\sigma }_i^j\left(a\right)<D^j$, which is reflected trivially here.

For auction j with multiple buyers, $i^{*}$ is the losing buyer with the highest unit price offer, determined by (17), Suppose that for some $i\in {\mathcal{I}}^j$, buyer demand is not met. In this case, by (15) the seller must notify i of a partial allocation by changing the bid vector at index i. With this caveat, and Proposition 3, we have that the aggregate demand of subset ${\mathcal{I}}^j$ is satisfied by seller j. Although the buyers’ valuation ${\theta }_i$ is not known to the seller, we will assume that buyers are bidding truthfully, and so the new reserve price $p_{i^{*}}^j+ϵ={{\theta }_{i^{*}}}^{\prime }+ϵ$. For clarity, let the reserve price be denoted by $p_{*}^j$. Now, by the elasticity of (9) and (12), we have that, $\forall z\ge 0$, $f_{i^{*}}\left(z\right)<f^j\left(z\right)\le f_i\left(z\right)$, which holds $\forall i\in {\mathcal{I}}^j$, and $\forall j\in {\mathcal{I}}_i$. We claim that the choice of reserve price $p_{*}^j$ does not force any buyers out of the local auction. To show this, we use the assumption of truthful bids, and the fact that since the auction begins at time $t>0$, buyers will bid at least once. As will be addressed in further analysis, we assume that a new bid price differs from the last bid price by at least $ϵ$. Suppose the auction starts at equilibrium, so ${\sum }_{i\in {\mathcal{I}}^j}{\sigma }_i^j\left(a\right)=D^j$ at time $t=0$. The reserve price $p_{*}^j$ set at time $t=0$ begins the auction with the first bid iteration, and so at $t>0$, $\forall i\in {\mathcal{I}}^j$, we have that $p_i^j-p_{*}^j\ge ϵ$. Now, in the case where at $t=0$, ${\sum }_{i\in {\mathcal{I}}^j}{\sigma }_i^j\left(a\right)>D^j$, by (5), the seller notifies (any) buyer k with the lowest bid price of a partial allocation by changing $d_k^j$ thus by Proposition 3, k either decreases its demand or increases its valuation until ${\sigma }_i^j\left(a\right)\le d_i^j$. Then, as the seller computes the set ${\mathcal{I}}^j$ at each time step, a new $i^{*}$ may be chosen and the buyers bid again. Suppose $\exists k\in {\mathcal{I}}^j$ such that $\forall l\in {\mathcal{I}}_k,i\ni {\mathcal{I}}^l\forall i\ne k\in {\mathcal{I}}^j$. That is, k is disconnected from all other buyers $i\in {\mathcal{I}}^j$, and suppose that $d_k^j$ is partial allocation at $t>0$, and further suppose that there are many $l\in {\mathcal{I}}_k$ where $|{\mathcal{I}}^l|>|{\mathcal{I}}^j|$. The more buyers an auction has, the more likely that cases will occur that cause buyers to rebid, particularly if auctions $l\in {\mathcal{I}}_k$ have overlapping buyers, then k may opt-out of auction j, i.e., $s_k^{j\left(t\right)}\ne s_k^{j(t+1)}=0$, then the seller may simply return the tentatively allocated data to $D^j$. Finally, we note that if for some $i\in {\mathcal{I}}^j\exists k\in {\mathcal{I}}^j$ such that $p_i^j=p_k^j$, then the seller again notifies the buyers of a partial allocation by changing $d_i^j$ and $d_k^j$ by (5). Thus we determine the valuation between seller j and buyer i is well-posed, the reserve price (20) is justified, and we have a local equilibrium at time $\tau$.    □

Remark 4.

In the case where market resources do not satisfy (15), we reason that in the case of insufficient data in the market buyers may wait for additional sellers or purchase from the ISP, κ, as a monopoly sale. Similarly, in the case of insufficient demand, where we may assume that data is held at time $t=0$ by κ at bid price ϵ.

4.3. A Simple Example

Example 1.

Finally, we give an additional simple example of convergence to a local market equilibrium, where the buyers are assumed to respond with their truthful, ϵ-best replies. The data for this example is shown in

Table 1. Data for Example.

Name	Bid Total	Unit Price
A	50	1
B	40	1.2
C	26	1.5
D	20	2
E	14	2.2

.

Algorithm 3 Seller progressive allocation.

1: $p^{j\left(0\right)}\leftarrow ϵ$, $s^{j\left(0\right)}\leftarrow (p^j,D^j)$, $\overline{\mathcal{I}}=Ø$, compute ${\mathcal{I}}^{j\left(0\right)}$ 2: Update $s^j$ 3: while  $D^j\left(t\right)>0$  do 4:  ${\displaystyle \overline{i}\leftarrow \underset{i\in I^j}{max}\sum _{i\in I^j}{p}_i^j}$ 5:  $D^{j(t+1)}\leftarrow D^{j\left(t\right)}-{\sigma }_{\overline{i}}^{j\left(t\right)}\left(a\right)$ 6:  $p^j\leftarrow p_{i^{*}}^j+ϵ$ and $d^j\leftarrow D^{j(t+1)}$ 7:  $s^{j(t+1)}\leftarrow (d^j,p^j)$ 8:  Update $s^j$ 9:  $\overline{\mathcal{I}}\leftarrow \overline{\mathcal{I}}\cup \overline{i}$ 10:  for $k\in \overline{\mathcal{I}}$ do 11:   if $p_k^j<p_{i*}^j$ then 12:    $D^{j(t+1)}=d_k^j$ 13:    $\overline{\mathcal{I}}\leftarrow \overline{\mathcal{I}}\backslash \left\{k\right\}$ 14:   end if 15:  end for 16:  Compute ${\mathcal{I}}^{j\left(t\right)}$ 17:  ${\mathcal{I}}^{j(t+1)}={\mathcal{I}}^{j\left(t\right)}\backslash \overline{\mathcal{I}}$ 18:  $t\leftarrow t+1$ 19: end while

Let $s^{\left(1\right)}={\left[(65,ϵ)\right]}_{i\in \mathcal{I}}$ and $s^{\left(2\right)}={\left[(85,ϵ)\right]}_{i\in \mathcal{I}}$. The buyer bids are as follows:

$$\begin{array}{cc}\hfill s_A& =\left[\right(0,0),(50,1\left)\right],\hfill \\ \hfill s_B& =\left[\right(0,0),(40,1.2\left)\right],\hfill \\ \hfill s_C& =\left[\right(0,0),(26,1.5\left)\right],\hfill \\ \hfill s_D& =\left[\right(0,0),(20,2\left)\right],\hfill \\ \hfill s_E& =\left[\right(0,0),(14,2.2\left)\right].\hfill \end{array}$$

Then at $t=1$, we have bid vector $s^{\left(2\right)}=[(0,p^{\left(2\right)}),(20,p^{\left(2\right)}),(26,p^{\left(2\right)}),(20,p^{\left(2\right)}),(14,p^{\left(2\right)})]$, and so $(D^{\left(2\right)},p^{\left(2\right)})=(85,1+ϵ)$, The buyer response is,

$$\begin{array}{cc}\hfill s_A& =\left[\right(50,1),(0,0\left)\right],\hfill \\ \hfill s_B& =\left[\right(40,1.2),(0,0\left)\right],\hfill \\ \hfill s_C& =[(0,0),(26,p^{\left(2\right)})],\hfill \\ \hfill s_D& =[(0,0),(20,p^{\left(2\right)})],\hfill \\ \hfill s_E& =[(0,0),(14,p^{\left(2\right)})].\hfill \end{array}$$

At $t=2$, $(D^{\left(1\right)},p^{\left(1\right)})=(65,1+ϵ)$, with bid vector $s^{\left(1\right)}=[(25,p^{\left(1\right)}),(40,p^{\left(1\right)}),(0,0),$$(0,0),(0,0)]$. $(D^{\left(2\right)},p^{\left(2\right)})=(25,1+ϵ)$. Then,

$$\begin{array}{cc}\hfill s_A& =[(25,p^{\left(1\right)}),(25,p^{\left(2\right)})],\hfill \\ \hfill s_B& =[(40,p^{\left(1\right)}),(0,0)],\hfill \end{array}$$

where we have removed bids to indicate winner(s) with a tentative allocation. At $t=3$, $(D^{\left(1\right)},$$p^{\left(1\right)})=(50,1+ϵ)$, with bid vector $s^{\left(1\right)}=[(25,p^{\left(1\right)}),(40,p^{\left(1\right)}),(0,0),(0,0),(0,0)]$. $(D^{\left(2\right)},p^{\left(2\right)})=(0,1+ϵ)$ and $s^{\left(2\right)}=[(25,p^{\left(1\right)}),(0,0),(26,p^{\left(2\right)}),(20,p^{\left(2\right)}),(14,p^{\left(2\right)})]$. Then,

$$\begin{array}{cc}\hfill s_A& =[(25,p^{\left(1\right)}),(0,0))].\hfill \end{array}$$

At $t=4$ the auction ends.

4.3.1. Individual Rationality/Selfishness

We conclude this portion by examining the relationship between the strategies of buyers and sellers in local auctions. We have proven that a buyer cannot have a negative utility. Our strategic framework creates an incentive for the seller to maintain a local equilibrium, where supply equals demand. A truthful bid implies that the new bid price differs from the last bid price by at least $ϵ$. As a seller must distribute bid vectors to all buyers in its auction, we reason that the seller may employ a strategic caveat. The seller will notify a buyer who is subject to a market shift by changing its bid at the appropriate index. As we have shown, the seller is a functional extension of the buyer, with rules determined by the buyers’ behavior. This gives an auction j a natural logical extension into the global market through its buyers. We demonstrate that the symmetry between buyer and seller behavior, consequently strategies, stretches into a symmetry across subsets of local auctions. Value is modeled as a function of the entire marketplace: a buyer’s valuation is aggregated over all the auctions, and the seller’s valuation is aggregated over its own auction. We must ensure that a user’s private action satisfies the conditions of a direct-revelation mechanism, as well as adheres to the collective goals. We show that, from Lemma 4 and Definition 3, an individual user will contribute to local stability, given global market dynamics S.

We model the impact of the dynamics of S of the data-exchange market on a local auction j. The market fluctuations from S give auctioneer j the chance to infer information about the global market. We identify a clear bound restricting the range of influence that local auctions have on each other. Consider a single iteration of the auction, where a seller updates bid vector $s^j$, and the buyers’ response $s_i$, to comprise a single time step. We have the following Proposition,

Proposition 1

(Valuation across local auctions). For any $i,j\in \mathcal{I}$,

$$j\in {\mathcal{I}}_i\iff i\in {\mathcal{I}}^j.$$

(22)

Fix an auction $j\in \mathcal{I}$ with duration τ and define the influence sets of users. The primary and secondary influencing sets are given as,

$${\displaystyle \Lambda =\bigcup _{i\in {\mathcal{I}}^j}{\mathcal{I}}_i,\mathrm{and}\lambda =\bigcup _{i\in {\mathcal{I}}^j}\left(\bigcup _{k\in {\mathcal{I}}_i}{\mathcal{I}}^k\right).}$$

(23)

Define $\Delta =\Lambda \cup \lambda$. Fixing all other bids $s_i^j\in \mathcal{I}$, and time $t>0\in \tau$, we have that,

$${\displaystyle \sum _{j\in \Lambda }{\theta }_i^j=\sum _{i\in \lambda }{\theta }_i^j.}$$

(24)

Proof. 

As this is our main result, we provide an outline of the (exhaustive) proof, illustrating the most important case, when a market shifts affect auction j, and the direct influence of the shift on the connected subset of local markets.

A local auction $j\in \mathcal{I}$, is determined by the collection of buyer bid profiles. Using Lemma 4 and (22), we have that,

$$i\in {\mathcal{I}}^j\iff p_i^j>p_{i^{*}}^j,$$

(25)

where we define $i^{*}$ as the losing buyer with the highest bid price in auction j. By (9) $p_i^j\ge p_{i^{*}}^j+ϵ$, thus $p_i^j<p_{i^{*}}^j$ can only happen during a market shift. Consider $k\in {\mathcal{I}}^j$ at time t where, for example, some buyer(s) enter the auction, and so (25) implies that ${\sum }_{i\in {\mathcal{I}}^j}{\sigma }_i^j\left(a\right)>D^j$. Now, $p_i^j<p_{i^{*}}^j\Rightarrow k\ni {\mathcal{I}}^j$ and $s_k^j>0$ will cause k to initiate a shift. By Definition 3, k will set $s_k^j=0$, and begin to add sellers to its pool. Suppose that at time t, j’s market is at equilibrium. Unless k adds a seller with a higher reserve price within $|{\mathcal{I}}^j|$ time steps, by (21), the auction ends. We have that, $\forall i\in {\mathcal{I}}^j$, $\nexists s_i^j>0$ where $i\ni {\mathcal{I}}^j$, and (22) holds.

Now, the subset ${\mathcal{I}}^j\subset \mathcal{I}$ determines j’s reserve price $p_{i^{*}}^j$. We will assume the buyer submits a coordinated bid, using (5). The reserve price (20) of seller j is determined at each shift, and is the lowest price that j will accept to perform any allocation. Let $p_{*}^j$ denote the reserve price of auction j and $p_i^{*}$ denote the bid price of buyer i, i.e., $p_i^k=p_i^{*},\forall k\in {\mathcal{I}}_i$. Using Lemma 4, for each $i\in {\mathcal{I}}^j$, we have from (9), (12), that $p_i^{*}\ge p_{*}^k,\forall k\in {\mathcal{I}}_i$. In the simplest case, consider a disjoint local market j, where $\forall i\in {\mathcal{I}}^j$, $s_i^k=0,\forall k\ne j\in {\mathcal{I}}_i\Rightarrow \Lambda =\left\{j\right\}$ and $\lambda ={\mathcal{I}}^j$. Again using (9) and (12), it is clear that ${\theta }_i={\theta }^j,\forall i\in {\mathcal{I}}^j$. In all other cases, the sellers $\in \Lambda$ are competing to sell their respective resources to buyers whose valuations are distributed across multiple auctions. The bid price of buyer $i\in {\mathcal{I}}^j$ is determined by, $p_i^{*}={max}_{k\in {\mathcal{I}}_i}\left(p_{*}^k\right)$. $\Lambda$ is the set of sellers directly influencing the bids of buyers in auction j. Now, the reserve price for auction j is such that, $p_{*}^j\le {min}_{i\in {\mathcal{I}}^j}\left(p_i^{*}\right)-ϵ$. From (23), $\Lambda$ is defined by a seller $j\in \mathcal{I}$, where each user $k\in \lambda$ has some direct or indirect influence on j. Denote ${\Delta }^j={\Lambda }^j\cup {\lambda }^j$.

Consider the set ${\lambda }^j$. For some buyer $i\in {\mathcal{I}}^j$, and then for some seller $k\in {\mathcal{I}}_i$, we have a buyer $l\in {\mathcal{I}}^k$. By (22), $i,l\in {\mathcal{I}}^k$, and so the reserve price $p_{*}^k\le min(p_l^{*},p_i^{*})$, and $k,j\in {\mathcal{I}}_i\Rightarrow p_i^{*}\ge max(p_{*}^k,p_{*}^j)$. Suppose that $l\ni {\mathcal{I}}^j\iff j\ni {\mathcal{I}}_l$, so that $p_l^{*}<p_{*}^j$, and the valuation of buyer l does not impact auction j and vice versa, i.e., ${\theta }_l^j=0$. Since $l\in {\mathcal{I}}^k$, $p_l^{*}\ge p_{*}^k\Rightarrow p_{*}^k<p_{*}^j$, and $i\in {\mathcal{I}}^j\Rightarrow p_i^{*}\ge p_{*}^j$. Therefore, we have that the ordering implied by (23) holds, and,

$$p_{*}^k\le p_l^{*}<p_{*}^j\le p_i^{*},$$

(26)

for any buyer $l\in {\lambda }^j$ such that $l\ni {\mathcal{I}}^j$. We use a similar argument for a secondary user $q\in {\mathcal{I}}_l$.

Finally, consider the subset ${\Lambda }^j$; a shift occurs in 2 cases. (1) If $i\in {\mathcal{I}}^j$ decreases its bid quantity so that ${\sum }_{i\in {\mathcal{I}}^j}{\sigma }_i^j\left(a\right)<D^j$, and (2) if buyer $i^{*}$, defined in Lemma 4, increases its valuation so that $p_{i^{*}}^j<p_{*}^j$. Fixing all other bids, a decrease in q’s demand will directly impact buyer i. If at the end of the bid iteration, we still have that i is the buyer with the lowest bid price, then (12) holds and j’s valuation does not change. Otherwise a new $i^{*}$ will be chosen upon recomputing ${\mathcal{I}}^j$, as a consequence of Definition 3 and Lemma 4, and the market will attempt to regain equilibrium. We determine the influence of ${\Delta }^{k^{*}}$ on ${\Delta }^j$ by (25).

In each case we have that (9) and (12) hold for some fixed time t, and so, $\forall i\in {\mathcal{I}}^j$, any bid outside of our construction has a zero valuation, with respect to buyers $\in \lambda$ and sellers $\in \Lambda$, and therefore cannot cause shifts to occur except through a shared buyer, e.g., some $l\in {\mathcal{I}}^k$. Thus, in all cases, (9) and (12) hold. Fixing all bids in any auction where $q\ni {\Lambda }^j$, $\forall i\in {\mathcal{I}}^j,\forall k\in {\mathcal{I}}_i,\forall l\in {\mathcal{I}}^k$,

$$\begin{array}{cc}\hfill {\int }_0^{{\sigma }_i^k\left(a\right)}{f}_i\left(z\right)dz& ={\int }_0^{{\sigma }_i^k\left(a\right)}{f}^k\left(z\right)dz,\hfill \end{array}$$

(27)

and

$$\begin{array}{cc}\hfill {\int }_0^{{\sigma }_l^k\left(a\right)}{f}^k\left(z\right)dz& ={\int }_0^{{\sigma }_l^k\left(a\right)}{f}_l\left(z\right)dz.\hfill \end{array}$$

(28)

Thus, with a slight abuse of notation for clarity,

$$\sum _{\lambda }{\int }_0^{\sigma \left(a\right)}{f}^{\Lambda }\left(z\right)dz=\sum _{\Lambda }{\int }_0^{\sigma \left(a\right)}{f}_{\lambda }\left(z\right)dz,$$

(29)

where the result follows by construction, and the continuity of ${\theta }^{\prime }$. □

For completeness, in the case where the ISP $\kappa$ does not adhere to the market dynamics, so $p^{\kappa }>p^j+ϵ,\forall j\in \mathcal{I}$, then we may absorb the overage (difference) as part of the bid fee.

4.3.2. Locally Fair Division

We claim that the allocation a by seller j for a local auction at equilibrium is an equitable division, a fair division where each buyer equally values their valuation. We have that equitable division holds from (27) Proposition 1.

4.3.3. Social Welfare Maximization

We define an optimal state of social welfare to be when valuations are equal across a subset of local auctions. Then, $\Delta \subset \mathcal{I}$ to be a subset of users where an optimal social welfare is achieved.

4.3.4. Social Welfare Maximization (Exclusion-Compensation)

We define an optimal state of social welfare to be when valuations are equal across a subset of local auctions. Then, $\Delta \subset \mathcal{I}$ is the subset of users where social welfare is achieved. We finally have:

Corollary 1

($\Delta$-Pareto efficiency). The subset $\Delta \subset \mathcal{I}$ is Pareto efficient, in that no user can make a strategic move without making any other user worse off.

Proof. 

Define $s_{*}=(z_{*},{\theta }_{*}^{\prime }\left(z_{*}\right)$ as the set of truthful $ϵ$-best replies for user i given opponent bid profile $S_{-i}$, where $\forall j\in {\mathcal{I}}_i$, $s_{*}^j=s_{*}$. Since ${\theta }_i^{\prime }$ is continuous, as was shown in Lemma 2, and as ${s|}_{\Delta }=\{\left[s_i^j\right]\in {\lambda }^j\times {\Lambda }^j\}$ is continuous in s on $S_k={\Pi }_{k\in {\lambda }^j}{S}_k^j$, then given that $s_{*}=s^{*}=(f^{*}\left(p^{*}\right),p^{*})=(z^{*},{\theta }^{\prime }\left(z^{*}\right))$, we have that $s^{*}$ is truthful. The result now follows directly from the result of Proposition 1. □

5. Equilibrium Analysis

We intend to show evidence shared network optima (a global optimum). A buyer $i\in \mathcal{I}$ will have incentive to change its bid quantity if it increases its opt-out value ${\sigma }_i$, and therefore its utility (8). We will show that, without loss of utility, buyer i may use a “consistent” bid strategy within its seller pool, i.e., $d_i^j=d_i^k,\forall j,k\in {\mathcal{I}}_i$, and as such, Proposition 3 supports an optimal strategy with respect to (8). Our result shows that a buyer may select ${\mathcal{I}}_i$ in order to maximize its utility while maintaining a coordinated bid strategy. Reasonably, if $j^{*}<I$, a buyer may increase the size of its seller pool ${\mathcal{I}}_i$, thereby lowering its coordinated bid quantity while obtaining the same (potential) allocation $a_i$. As buyer i submits identical bids to multiple auctions, the bid price must be as high as the highest reserve price $p_i^j\in {\mathcal{I}}_i$. Buyer i’s bid then has identical bid price $p_i^j\forall j\in {\mathcal{I}}_i$. We further note that i optimal strategy does not require reducing its bid price to a minimum in each auction, where the bid quantity ${\sigma }_i^j\left(a\right)$ is still fulfilled. The pricing rule of the PSP auction dictates that a buyer i will pay the cost of excluding other players from the auction, and as i’s bid price reflects its valuation of it data requirement $D_i$ across all local markets, we have identical bid prices in each auction where $s_i^j>0$. Obviously, if $j\ni {\mathcal{I}}_i$, then ${\theta }_i^j=0$.

Lemma 5

(Opt-out buyer coordination). Let $i\in \mathcal{I}$ be a opt-out buyer and fix all sellers’ profiles $s^j$. For any profile $S_i=(D_i,P_i)$, let $a_i\equiv {\sum }_j{a}_i^j\left(s\right)$ be a tentative data allocation. For any fixed $S_{-i}$, a better reply for i in any auction is $x_i={\sigma }_i\circ (z_i,y_i)$, where $\forall j\in {\mathcal{I}}_i$,

$$\begin{array}{cc}\hfill z_i^j& ={\sigma }_i^j\left(a\right),\hfill \\ \hfill y_i^j& ={\theta }_i^{\prime }\left(z_i^j\right).\hfill \end{array}$$

Furthermore,

$$a_i^j(z_i,y_i)=z_i^j,$$

(30)

and

$$c_i^j(z_i,y_i)=y_i^j,$$

(31)

where i’s strategy is as in Proposition 3.

The proof follows closely the work in [12].

Proof. 

As $s_{-i}$ is fixed, we omit it, in addition, we will use $u\equiv u_i\equiv u_i\left(s_i\right)\equiv u_i(s_i;s_{-i})$. In full notation, we intend to show

$$u_i((d_i,p_i);s)\le u_i((z_i,y_i);s_{-i}).$$

Now, if there exists a seller who can fully satisfy i’s demand, then $|{\mathcal{I}}_i|=1$, and the case is trivial as no coordination is necessary for a single bid. Otherwise, buyer i’s demand can only be satisfied by purchasing data from multiple sellers. We will show that i may increase $|{\mathcal{I}}_i|$, and so decreasing $d_i^j,\forall j\in {\mathcal{I}}_i$, without decreasing ${\sum }_{j\in {\mathcal{I}}_i}{u}_i^j$. Buyer i maintains ordered set ${\mathcal{I}}_i$ where the sellers with the largest bid quantities are considered first; the index of seller $j^{*}$ defines a minimal subset ${\mathcal{I}}_i$, satisfying (16). By construction, $d_i^{j^{*}}$ is the minimum quantity bid offered by any $j\in {\mathcal{I}}_i$. Thus by (16) and (19), $\forall j\in {\mathcal{I}}_i$, $k\ni {\mathcal{I}}_i$, ${\sigma }_i^k\left(a\right)\le z_i^j={\sigma }_i^j\left(a\right)$, and so, using (24),

$${\sigma }_i^j\left(a\right)\le {\left[D^j-\sum _{k\in {\mathcal{I}}^j:p_k^j>y_i^j}{d}_k^j\right]}^{+}.$$

(32)

The buyer valuation function (13), guarantees that $\forall j\in {\mathcal{I}}_i$, $y_i^j\ge p_{i^{*}}^j$, where $p_{i^{*}}^j$ is the reserve price of seller j, defined in Proposition 4, and is by definition the minimum price for a buyer bid to be accepted. As ${\overline{D}}_i^j$ is non-decreasing, $\forall j\in {\mathcal{I}}_i$, $k\ni {\mathcal{I}}_i$,

$$D_i^j\left(y_i^j\right)\ge D_i^j\left(p_i^j\right)\ge D_i^j\left(p_i^k\right).$$

Thus (32) holds and so, by (5),

$$\begin{array}{cc}\hfill a_i^j(z_i,p_i)& =\underset{i\in {\mathcal{I}}^j}{min}\left(z_i^j,{\left[D^j-\sum _{p_k^j>y_i^j}{d}_k^j\right]}^{+}\right)\hfill \\ \hfill & =z_i^j={\sigma }_i^j\left(a\right)\hfill \end{array}$$

where the last equality is by definition, and so (30) is proven. From (3), ${\overline{D}}_i^j(y,s_{-i})=0\forall y<p_{i^{*}}^j$, and ${\overline{D}}_i^j(y,s_{-i})=0\le ϵ\Rightarrow {\sigma }_i^j\left(a\right)=0\Rightarrow z_i^k=0,\forall k\ni {\mathcal{I}}_i$, and therefore,

$$\begin{array}{c}\hfill {\displaystyle \sum _{j\in {\mathcal{I}}_i}{c}_i^j(z_i,y_i)=\sum _{j\in {\mathcal{I}}_i}{c}_i^j(z_i,p_i),}\end{array}$$

thus (31) simply shows that changing the price $p_i^j$ to $y_i^j$ does not exclude any additional buyers, as the bid $p_i^j$ was already above the reserve price of any seller $j\in {\mathcal{I}}_i$. We proceed to show that $x_i$ does not result in a loss of utility for buyer i, that is,

$$u_i\le u_i(z_i,y_i).$$

From (30), we have $a_i^j(z_i,y_i)=z_i^j={\sigma }_i^j\left(a(z_i,y_i)\right)$, and so,

$${\theta }_i\circ {\sigma }_i^j\left(a(z_i,y_i)\right)={\theta }_i\circ {\sigma }_i^j\left(a\right),$$

which holds $\forall j\in {\mathcal{I}}_i$. Therefore, by the definition of utility (8), and the buyers’ valuation (13),

$$\begin{array}{cc}\hfill & {\theta }_i\circ {\sigma }_i\left(a(z_i,y_i)\right)-{\theta }_i\left(a\right)\circ {\sigma }_i\left(a\right)\hfill \\ \hfill & {\displaystyle =u_i(z_i,y_i)-u_i=\sum _{j\in {\mathcal{I}}_i}{c}_i^j-c_i^j(z_i,y_i)}\hfill \\ \hfill & =\sum _{j\in {\mathcal{I}}_i}{\int }_{a_i^j(z_i,p_i)}^{a_i^j}{f}_i(d_i^j-x)dx.\hfill \end{array}$$

Then, as $a_i(z_i,p_i)\le z_i^j\le a_i^j$, and noting that $z_i^j>0\Rightarrow {\theta }_i\ge 0\Rightarrow f_i\ge 0$, we have $u_i(z_i,y_i)-u_i\ge 0$, $\forall j\in {\mathcal{I}}_i$. □

The property of truthfulness is an essential component of equilibrium in second-price markets. The strategies described in this paper have removed the necessity for a user to determine its own valuation function, we intend to show that the market dynamics resulting from the construction of the user strategy space results in truthful bids that are optimal for all users, i.e., bid prices are to the marginal value as determined by market dynamics. To achieve incentive compatibility, we find that the opt-out buyer must choose We have so far only made the assumption of truthful bids throughout our analysis. As was shown in Proposition 1, a buyer only has incentive to change its bid as a result of a market shift or partial allocation. In a truthful reply, the term $ϵ/{\theta }_i^{\prime }\left(0\right)$ ensures that a new bid price differs from the last bid price by at least $ϵ$, thereby ensuring that a buyer does not change its bid without correcting the effects of unstable shifts. For any buyer i, it suffices to show the continuity of the set of truthful $ϵ$-best replies in the set of opponent bid profiles. So, for a buyer i, define the set of possible $ϵ$-best replies,

$$\begin{array}{cc}{S}^{ϵ}\left(s\right)& =\{s_i\in S_i\left(s_{-i}\right):u(s_i;s_{-i})\\ & \ge u_i(s_i^{\prime };s_{-i})-ϵ,\forall s_i^{\prime }\in S_i\left(s_{-i}\right)\},\end{array}$$

(33)

and the set of truthful bids,

$${\displaystyle T_i=\{s_i\in S_i\left(s_i\right):z=\sum _{j\in {\mathcal{I}}_i}{\sigma }_i^j\left(a\right)\wedge p_i={\theta }_i^{\prime }\left(z\right)\},}$$

(34)

where ∧ denotes the logical “and” operator. We note that the “strategic” set $T_i$ is restricted by Proposition 3. We have the following Proposition,

Proposition 2

(Incentive compatibility across local auctions). Let Λ, λ be defined as in Proposition (1), and fix time $t>0\in \tau$, and fix $s^j,\forall j\in \Lambda$, and for some buyer $i\in {\mathcal{I}}^j$, let $s_l$ also be fixed $\forall l\ni i\in \lambda$. Define,

$${\chi }_i=\{x\in [0,D_i]:{{\theta }_i}^{\prime }\left(x\right)>\underset{j\in \Lambda }{\max }{P}_i^j\left(x\right)\},$$

(35)

and $z=sup{({\chi }_i-ϵ/{\theta }_i^{\prime }\left(0\right))}^{+}$, and for each $j\in \Lambda$,

$$v_i^j={\sigma }_i^j\left(z\right),$$

and

$$w_i^j={\theta }_i^{\prime }\left(z\right).$$

Then a (coordinated) ϵ-best reply for the opt-out buyer is $t_i=(v_i,w_i)\in T_i\cap S_i^{ϵ}\left(s_{-i}\right)$, i.e., $\forall s_i,u_i(t_i;s_{-i})+ϵ\ge u_i(s_i;s_{-i})$. With reserve prices $p^j>0$, there exists a “truthful” strategy game embedded $\in \Delta$. Therefore, a fixed point $\in \Delta$ is a fixed point in the multi-auction game.

Proof. 

We claim that $t_i$ is an $ϵ$-best reply for buyer i. That is,

$$u_i(t_i;s_{-i})+ϵ\ge u_i(s_i;s_{-i}).$$

As a result of auction initialization, a seller j’s valuation defines its reserve price to be determined by a buyer $i\ni \lambda$, even if this price is zero, we have that $p^j=ϵ\ge 0\forall j\in \Lambda$. Let $z=sup\left({\chi }_i^j\right)$, and again let $p_{*}^j=f^j\circ {\sigma }_i^j\left(a\right)$ denote the reserve price of auction j, and $p_i^{*}=f_i\circ {\sigma }_i^j\left(a\right)$ denote the (coordinated) bid price of buyer i. We have that $i\in {\mathcal{I}}^j$, and (9) defines ${\theta }_i^{\prime }\left(z\right)$ as being max of the reserve prices $p_{*}^j,\forall j\in {\mathcal{I}}_i$, therefore (35) is such that,

$${\theta }_i^{\prime }\left(z\right)>\underset{j\in \Lambda }{max}{P}_i^j\left(v_i^j\right),$$

which implies, as ${\theta }_i^{\prime }$ is non-increasing and $P_i^j\ge 0$, we have $\forall j\in {\mathcal{I}}_i$,

$$\begin{array}{cc}\hfill w_i^j& >P_i^j\left(v_i^j\right)\hfill \\ \hfill \Rightarrow v_i^j& \le D_i^j\left(w_i^j\right)=D^j-{\rho }^j\left(w_i^j\right).\hfill \end{array}$$

And so, by (5),

$$\begin{array}{cc}\hfill a_i^j(t_i;s_{-i})& =v_i^j\hfill \\ \hfill {\displaystyle \Rightarrow \sum _{j\in \Lambda }{a}_i^j(t_i;s_{-i})}& =z.\hfill \end{array}$$

Therefore, $\forall j\in \Lambda$ and $\forall i\in \lambda$ such that (27) and (28) hold,

$$\begin{array}{c}\hfill {\int }_0^{v_i^j}{\overline{P}}_i\left(x\right)dx=\sum _{j\in \Lambda }{\int }_0^{{\sigma }_i^j\left(z\right)}{P}_i^j\left(x\right)dx.\end{array}$$

It follows that,

$$u_i(t_i;s_{-i})={\int }_0^z{\theta }_i^{\prime }\left(x\right)dx-{\sigma }_i\circ {\int }_0^z{\overline{P}}_i\left(x\right)dx.$$

Suppose $\exists s_i=(d_i,p_i)$ such that $u_i^j(s_i;s_{-i})>u_i^j(t_i;s_{-i})+ϵ$. Propositions 5 and 3, define the coordinated bid, ${\nu }_i=({\zeta }_i,p_i)$, using (27) and (28), for each $j\in \Lambda$, ${\sigma }_i^j\left(a_i^j({\nu }_i;s_{-i})\right)={\zeta }_i^j$, then clearly $u_i({\nu }_i,s_{-i})\ge u_i(s_i,s_{-i})\Rightarrow u_i(t_i;s_{-i})-u_i(s_i;s_{-i})>ϵ$. Denoting ${\zeta }_i^j$ (fixed) as $\zeta$,

$${\int }_z^{\zeta }{{\theta }_i}^{\prime }\left(x\right)dx-{\int }_z^{\zeta }{\overline{P}}_i\left(x\right)dx>ϵ.$$

For concave valuation functions, the first-order derivative of $\theta$ at point 0 gives the maximum slope of the valuation function, and so the factor $ϵ/{\theta }^{\prime }\left(0\right)$ guarantees that new bids will differ by at least $ϵ$, and as such, buyer i will remain in any local auction with reserve price determined by (20). We therefore verify that,

$${\displaystyle {\int }_z^{z+ϵ/{\theta }_i^{\prime }\left(0\right)}{\theta }_i^{\prime }\left(x\right)dx\le ϵ,}$$

and as $P_i^j\ge 0$, we have that, from the construction of $\zeta$,

$${\displaystyle {\int }_{z+ϵ/{\theta }_i^{\prime }\left(0\right)}^{\zeta }{\theta }_i^{\prime }\left(x\right)dx-{\int }_{z+ϵ/{\theta }_i^{\prime }\left(0\right)}^{\zeta }{\overline{P}}_i\left(x\right)dx>0.}$$

If $\zeta >z+ϵ/{\theta }_i^{\prime }\left(0\right)$, then for some $\delta >0$, ${\theta }_i(z+ϵ/{\theta }_i^{\prime }\left(0\right)+\delta )>P_i^j(z+ϵ/{\theta }_i^{\prime }\left(0\right)+\delta )$, contradicting (35). Now, if $\zeta \le z$, then ${\theta }_i^{\prime }(z+ϵ/{\theta }_i^{\prime }\left(0\right))<P_i^j(z+ϵ/{\theta }_i^{\prime }\left(0\right))$, also a contradiction of (35), and so buyer $s_i$ cannot exist. Finally, as we may consider $\Delta \subset \mathcal{I}$ to be a multi-auction game, our user strategies form a “truthful” local game with strategy space restricted to $ϵ$-best replies from buyers $\in \lambda$. Therefore we have that a fixed point in the “truthful” game is a fixed point for the auction. □

In linear analysis, we may determine a Nash equilibrium by finding a local optima of the potential function. Additionally, as the potential function also iterates, it may be used in an analysis of convergence. The convergence of a Nash equilibrium results from the progression of $ϵ$-best replies, where each subsequent bid is a unilateral improvement, provided that $t_i$ is continuous in opponent profiles. From the original proof by [3], we observe that the collection of unconstrained truthful bids may be a subset of the collection of $ϵ$-best replies, i.e., $T_i\subset S_i^{ϵ}$.

Now, the strategy space is comprised of a collection of bid, or “strategy”, vectors that together, may be represented as a collection of potential functions, where change in buyer i’s utility, resulting from a change in strategy, equals the change in the local market objective of each seller $j\in {\mathcal{I}}_i$. These local objectives are known as potential functions, and are formulated by mapping the incentives of all users in a local auction to a single function. The goal of our analysis is to therefore construct a global potential function that encompasses all local markets, and show that this space adheres to the construction described in our proof. The conditions of convexity, connectedness and continuity must apply to the global market space in order for a global equilibrium to exist.

In order to address continuity in a global sense, we must again demonstrate continuity in the construction of our model. We will show that our global market holds a differentiable topology, where our opt-out function $\sigma$ extends to an injective, differentiable map. We show that locally, the connectivity of our market subspace $\Delta$ provides a linearization, or approximation of a linear map, and so continuity holds in the global sense. We construct an extension and determine the existence and uniqueness of a global market objective by mathematical correspondence. We begin with the definition of correspondence,

Definition 3

(Correspondence). A correspondence is mathematically defined as an ordered triple $(X,Y,R)$, where R is a relation from X to Y, i.e., any subset of the Cartesian product $X\times Y$.

In an economic model, a correspondence $(S_i,S_{-i},R)$ defines a map from $S_i$ to the power set $S_{-i}$, where R is a binary relation, i.e., $R\subset S_i\times S_{-i}$. The classic example of a correspondence in our model is the buyers’ best response $B_i^{ϵ}$, where, for the multi-auction, $S_i$ and $S_{-i}$ are built by repeatedly using the Cartesian product over bid profiles. The power set $S_{-i}={\Pi }_j({\Pi }_{k\ne i}{S}_i^j)$ arises naturally from the product of ordered sets. The binary equality relation $i\sim j$ naturally occurs in the strategy space, and is both an equivalence relation and a partial order, and therefore is reflexive, transitive, symmetric and anti-symmetric. We use the the axiom of set equality based on first-order logic, which states that, $\forall i\in \mathcal{I},\forall j\in \mathcal{I},(i\in {\mathcal{I}}^j\iff j\in {\mathcal{I}}_i)\Rightarrow i\sim j$, and follows from (22). Given any set of buyers ${\mathcal{I}}_i\in \Lambda$ where we have an allocation from some $j\in {\lambda }_i$, Given a subset B of a set A, the injection f:B->A defined by f(b) = b for all b in B is called the inclusion map. $1_{\lambda }(S_i,S_{-i}):\lambda \to \Lambda \in S/\sim$, and so is a canonical mapping as well as an inclusion map. The product topology of the strategy space is preserved, and the set of all indicator functions on S forms the power set $\mathcal{P}\left(S\right)=S_i\times S_{-i}$ on S defines a quotient space, and forms the partition $\left\{s^j\in S:s^j\sim s_i\right\}$ of S. Now, $\Delta \subset \mathcal{P}\left(S\right)$ is the result of the correspondence map, and we have that set of users in an auction is uniquely determined by its members where sellers have fixed market prices; all users who are not changing their bids are considered equal. Therefore each seller $j\in \mathcal{I}$ is equivalent to some buyer $i\in \mathcal{I}$; buyer i’s utility constraint is satisfied in auction j if and only if seller j’s utility constraint is also satisfied.

The best response is a reaction correspondence defined by the mixed-strategy game. Denoting $T_i^{ϵ}=T_i\cap B_i^{ϵ}$, we have the set of truthful $ϵ$-best replies in opponent bid profiles $S_{-i}$. A natural induced topology of this space is the product topology, e.g., the canonical map $S_i\to {\Pi }_{j\in \mathcal{I}}{S}^j$. Now, in order to find a fixed point in the mixed strategy space, we must have a continuous mapping, i.e., ${\Lambda }^j\iff {\lambda }_i,\forall i,j\in \Delta$. The data-sharing market consists of inter-dependent sets of multi-auction games around possible fixed points. Clearly, the union of all possible sets ${\bigcup }_{j\in \mathcal{I}}{\Delta }^j$ covers $\mathcal{I}$. We claim that the shared buyers between the different subsets $\Delta$ form a sufficiently connected set, so that Proposition 1 holds. We have the following Lemma.

Lemma 6

(Continuity of $ϵ$-best reply on $\Delta$). Let Δ be defined as in Proposition (1). For any buyer $i\in {\lambda }^j$, the collection of bids $B_i$ is continuous in $S_{-i}$.

Proof. 

Define ${\sigma }_i\circ \overline{P}={max}_{i\in {\mathcal{I}}^j}{\theta }_i^{\prime }\left(0\right)$, and ${\overline{P}}_i(z,s_i)=\underline{P}=ϵ-\varrho$, where $ϵ$ is the bid fee, and $\varrho$ is i’s liability estimate for auction $j\in \mathcal{I}$. We observe that ${\sigma }_i\circ B_i^{ϵ}$ is simply $B_i^{ϵ}$ restricted to seller pool ${\mathcal{I}}_i$, i.e., ${\sigma }_i\circ B_i^{ϵ}\equiv B_i^{ϵ}{|}_{{\mathcal{I}}_i}$. Thus, we have ${\sigma }_i\circ T_i=({[0,D^k]}_{k\in {\mathcal{I}}^j}\times {[0,{\sigma }_i\circ \overline{P}]}^{|{\mathcal{I}}^j|})$ is a product of closed subsets of compact sets. Now, we have that a closed subset of a compact set is compact and the resulting product topology gives Tychonoff’s theorem, i.e., every product of a compact space is compact, we have ${\sigma }_i\circ B_i^{ϵ}$ is compact subset of $B_i^{ϵ}$. Now, letting $\overline{P}={max}_{i\in {\lambda }^j}{\theta }_i^{\prime }\left(0\right)$, and we have by definition of $\Delta$ and the product,

$${\sigma }_i\circ S_i\left(s_{-i}\right)\equiv {\sigma }_i{|}_{{\Lambda }^j}:S_i\mapsto T_i\subset S_i$$

$$\begin{array}{cc}\hfill & \Rightarrow \left(\bigcup _{i\in {\mathcal{I}}^j}{[0,D^k]}_{k\in {\mathcal{I}}_i},[0,\overline{P}]\right)=\bigcup _{i\in {\mathcal{I}}^j}\left({[0,D^k]}_{k\in {\mathcal{I}}_i}\times [0,\overline{P}]\right)\hfill \\ \hfill & =({[0,D^k]}_{k\in {\Lambda }^j},[0,\overline{P}])\in {\Lambda }^j\times {\lambda }^j\subset T.\hfill \end{array}$$

The result follows from the fact that $t_i$ is continuous in $s_i$, as was proven in [12], and as a finite union of compact sets is a compact set. □

We have proven that buyers will submit bids according to their marginal valuations. We have that all bids represent $ϵ$-best replies, and, as was proven in [3]. The sellers’ positive reserve price implies that bids are truthful. Finally, by properties determined by the construction of a mixed strategy symmetric game with a two-dimensional message space, we may now restrict our analysis to the set of continuous, truthful, $ϵ$-best replies, $T^{ϵ}$. In mathematics, the notion of the continuity of functions is not immediately extensible to multivalued mappings; we show the correspondences between the two sets $\lambda$ and $\Lambda$. The correspondence between i and j forms the set $\lambda \sim \Lambda$. We note that due to the binary relation, the set of all possible $ϵ$-best replies,

$${\Delta }^{ϵ}{=\{(i,j)\in \lambda \times \Lambda \}|}_{T^{ϵ}},$$

is well-posed by [15] Definition (4.3) and Corollary (4.4). We show that our bidding strategy results in (at least one), Nash equilibrium, where again the sellers reserve prices are fixed.

Lemma 7

(${\Delta }^{ϵ}$-Nash Equilibrium). Let Δ be defined as in Proposition (1), and suppose that auction $j\in \Delta$ is not in a transient state, e.g., $t={\tau }^j$. Fix all $s_i^k,k\ne j$. Using the rules of the data auction mechanism, along with type-based strategic moves, j converges to an ϵ-Nash equilibrium. The proof follows closely that of [12].

Proof. 

As auction j is at equilibrium, and since ${\theta }_i^{\prime }$ is continuous, as was shown in Lemma 2, and $t=\{\left[t_i^j\right]\in {\lambda }^j\times {\Lambda }^j\}$ is continuous in s on $T_k={\Pi }_{k\in {\lambda }^j}{T}_k^j$. Now, t represents a continuous mapping of ${[0,{\displaystyle \sum _{k\in {\lambda }^j}}{D}^k]}_{i\in {\Lambda }^j}$ onto itself and we may use Brouwer’s fixed point theorem, as in [12], which states that the continuous mapping of a convex compact set into itself has at least one fixed point. Therefore, ∃ some $k\ne i$ such that $z^{*}={\sigma }^{*}\left(z\right)\in {[0,D_k]}_{i\in {\Lambda }^j}$. Then, given that $s^{*}=(z^{*},{\theta }^{\prime }\left(z^{*}\right))$, we have that $s^{*}=t\left(s^{*}\right)\in T$. □

The rules of the PSP multi-auction drive market mutations that evolve and are regulated by the user strategies. As a result of user behavior, and subsequent strategies, we determine that the data-exchange market behaves in a predictable way. We point out the need for better management of data on the consumer level. It is obvious that there is profit to be made by supplying data to the data-driven consumer. Mathematically, we have shown that if truthfulness holds locally for both buyers and sellers, i.e., $p_i={{\theta }_i}^{\prime },\forall j\in {\mathcal{I}}_i$ and $p^j={{\theta }^j}^{\prime },\forall i\in {\mathcal{I}}^j$, then, in the absence of market shifts, there exists an $ϵ$-Nash equilibrium extending over a subset of connected local markets. However, each auction may be played on the same or on a different scale in valuation, time and quantity, and so the rate at which market fluctuations occur is impossible to predict. This presents a problem, as in our linear analysis we rely on the stability of the market equilibrium at a fixed time to find a convergent sequence of $ϵ$-best replies within any auction j, whereas in the global market discontinuities may occur when we have ${\mathcal{I}}_i\cap {\mathcal{I}}^j=Ø$. In this case, we must address the market using a non-linear analysis. Up to this point, we have constructed our proofs around connected local markets, such as in Proposition 1, where we defined connectivity via a set of influencing users $\Lambda$ and $\lambda$. The result was the existence of a sequence of vector-valued functions on the union of the influencing sets, $\Delta$, allowing for the requirements of differentiability and therefore continuity to hold, resulting in a fully connected subset of local auctions.

For each $\Delta$, the Kuhn–Tucker optimality conditions imply that $s_i$ is the optimal response of player i to $s_{-i}$ if and only if there exists a Lagrange multiplier ${\rho }_i$ such that:

$${\rho }_i={\theta }^{\prime }\left(s_i^j\right),\mathrm{if}{s}_i^j>0,j\in \Delta$$

(36)

$${\rho }_i\le {\theta }^{\prime }\left(s_i^j\right),\mathrm{if}{s}_i^j=0,j\in \Delta$$

(37)

$$\sum _{j\in \Delta }{s}_i^j=a_i,s_i^j\ge 0,i\in \Delta .$$

(38)

where $\rho$ turns out, in fact, to be the (stable) marginal price [16]. Without loss of generality, we will consider adding data in such a way that the ordering of the sets $\lambda$ and $\Lambda$ is preserved. That is, the buyers bids are such that $s_1\ge s_2\ge \cdots \ge s_I$. We may even define a function $\mathcal{N}:\Delta \to {\mathbb{R}}^S$ that assigns each $s\in S_{\Delta }$ the Nash equilibrium $\mathcal{N}\left(s\right)$ of its respective game. Each assignment induces a game with a unique Nash equilibria. We consider disjoint sets $\{\Delta \}$, we construct an extension so that for any influencer $i\in {\Delta }^{ϵ}$, there is an extension such that for $k\in {\Delta }^k$ such that the dominant strategy for $i\in {\Delta }^{j\times k}$.

We construct our extension in the form of a new user type, a broker type. A broker type fills the space between ${\Delta }^j$ and ${\Delta }^k$ by purchasing data from one auction subset and selling it in the other. This user performs the function of connecting two fully-connected auction subsets ${\Delta }^j$ and ${\Delta }^k$ by supplying additional data from one auction (${\Delta }^j$) to the ordered set ${\mathcal{I}}^j$ of each seller in each auction $j\in {\Delta }^k$. We show that this additional broker type preserves the optimality of the set ${\Delta }^j\cup {\Delta }^k$. Suppose that the broker assumes that there is an infinite amount of data available to buy and creates bids on the assumption that a market $\Delta$ will be available to fill the data request. The broker may create orders that are not feasible in the actual market, causing buyers in $\Delta$ to shift their bids according to the (presumed) available data. In this way, the broker may actually plan the data requirements, overage or underage, based on some finite scheduling scheme. This concept is beyond the scope of our current research, but merits some future consideration. In this case, the broker can only add data $\delta$ to $\Delta$ from the set $\{d\in {\mathbb{R}}_{+}^I:s_1\ge \cdots \ge s_I;({\delta }_i,·)\ge (d_i,·);\sum (d_i-{\delta }_i)\le \delta \}$. We are presented with the problem of how to add additional data to $\Delta$ that is optimal with respect to its Nash equilibrium ${\mathcal{N}}_{\Delta }$, as in [17]. For each optimal strategy s, the unique Nash equilibria ${\mathcal{N}}_{\Delta }\left(s\right)$ describes the allocations of data $D^j$ from each seller j in $\Delta$.

We begin by examining the addition of data to a single market subset. We will show that this strategy, which we will call $s^{*}$, is therefore userwise price optimal for the entire space $\mathcal{N}\left(s\right)\forall s\in S$. We show that, under certain conditions, the transfer of data happens in an “ordered” way, so that the natural price ordering of the space is preserved and thus, the Nash equilibrium. In particular, there exists a Lagrange multiplier ${\rho }^{*}$ such that (36)–(38) hold.

Theorem 1

(${\Delta }_{ϵ}^{*}$-Nash Equilibrium). Let ${\Delta }^{*}={\Delta }^j\cup {\Delta }^k$ be a union of market subsets at equilibria. Let ${\mathcal{A}}_{\Delta }^{*}\left(s\right)$ be an allocation where a bids $\widehat{s^j}=(p^j,\widehat{d^j})$, are augmented such that $\widehat{d^j}=d^j-{\delta }_i$ and ${\delta }_i$ is such that ${\sum }_{j\in {\Delta }^j}\widehat{a_i^j}={\sum }_{k\in {\Delta }^k}{a}_i^k$. Then,

$${\widehat{p}}_{*}^j<p_{*}^j\in \Lambda ,$$

(39)

and,

$${\widehat{p}}_i^{*}>p_i^{*}\mathrm{for}\mathrm{all}i\in \lambda .$$

(40)

The transfer of data δ from influencing set ${\Lambda }^j$ to ${\Lambda }^k$ preserves the ordering ${\widehat{p}}_{*}^j\le {\widehat{p}}_l^{*}<{\widehat{p}}_{*}^k\le {\widehat{p}}_i^{*}$ for all users $k,j\in {\mathcal{I}}_i$, $i,l\in {\mathcal{I}}^j$, $i\in {\mathcal{I}}^k$ such that $l\in {\Lambda }^k,l\ni {\mathcal{I}}^k$.

Proof. 

We speculate that two things are going to happen with this change in allocation. 1. Buyers in ${\Delta }^j$ will no longer have enough data to satisfy the bid requirement of their current auction, and will increase their reserve price. 2. Sellers in ${\Delta }^k$ will have additional data to sell, and so will lower their reserve price. We determine the influence of the modified allocation by (25) and (20). Without loss of generality, suppose that a broker purchases data from auction $j\in {\Delta }^j$, selling it in as auction $k\in {\Delta }^k$. This may happen for any pair of auctions in which the sellers reserve prices differ by more than $ϵ$, that is $p_{*}^k\ge p_{*}^j+ϵ$ for some $k\in {\Delta }^k$ and for some $j\in {\Delta }^j$. In this way the broker may make a profit. We have that ${\widehat{p}}_{*}^j>p_{*}^j\in {\Lambda }^j$ as the losing buyer with the highest bid price changes; less data in auction j will push buyers out of the auction, as seller j increases it’s price according to (20). We will call this set of buyers $\widehat{I}$. Now buyers in $\widehat{I}$ are making consistent bids, and so must increase their bid uniformly. The set ${\Lambda }^j$ does not have enough data to satisfy the demands of all the sellers ${\lambda }^j$, and so bids must be made that include sellers from ${\Lambda }^k$, making ${\Delta }^{*}$ a connected set (noting the allocation restriction of two sets in the premise). The sets ${\Delta }^j$ and ${\Delta }^k$ must be connected through auction $\widehat{k}$, as buyers in $\widehat{\mathcal{I}}$ will need to bid in auction $\widehat{k}$ in order to satisfy their data requirement. This, in effect, adds auction $\widehat{k}$ to ${\Delta }^j$, along with the corresponding influencers. As buyers bid consistently, buyers from $\widehat{\mathcal{I}}$ will bid the same in all auctions from ${\Delta }^j$, now including auction $\widehat{k}$.

We address the buyer side. The bid price of buyer $i\in {\mathcal{I}}^j$ is determined by $p_i^{*}={max}_{j\in {\mathcal{I}}_i}\left(p_{*}^j\right)$. For some buyer $i\in {\mathcal{I}}^j$, and then for some seller $k\in {\mathcal{I}}_i$, we have a buyer $\widehat{l}\in {\mathcal{I}}^k$. By (22), $i,\widehat{l}\in {\mathcal{I}}^k$, and so the reserve price $p_{*}^k\le min({\widehat{p}}_l^{*},p_i^{*})$, and $k,j\in {\mathcal{I}}_i\Rightarrow p_i^{*}\ge max(p_{*}^k,p_{*}^j)$. With the addition data to auction k, we now have that ${\widehat{p}}_i^{*}\ge max({\widehat{p}}_{*}^k,{\widehat{p}}_{*}^j)$, and ${\widehat{p}}_i^{*}>p_i^{*}$ by (39). Seller k, now adding data to ${\Delta }^k$, must bring new buyers in, changing its reserve price according to (20). Seller k will choose its reserve price to compete with sellers ${\Lambda }^k$. As ${\Delta }^k$ is a fully connected set at equilibrium, as defined in Proposition 1, the reserve price for auction $\widehat{k}$ must be set to ${max}_{j\in {\Lambda }^k}\left(p_{i^{*}}^j\right|{\sum }_{i\in I^k}{a}_i^k=D^k)$. As we assume that the broker would not act without gaining a profit, we must have that the reserve price of auction $\widehat{k}$ is at least $ϵ$ higher than that of auction j. Again, for all $i\in \widehat{I}$, ${\widehat{p}}_i^{*}>p_i^{*}$.

Now suppose that $\widehat{l}\ni \widehat{\mathcal{I}}\iff \widehat{k}\ni {\mathcal{I}}_l$, the valuation of buyer $\widehat{l}$ does not impact auction $\widehat{k}$ and vice versa, i.e., ${\theta }_l^k=0$. We must have that ${\widehat{p}}_l^{*}\ge p_j^{*}$ and ${\widehat{p}}_l^{*}<{\widehat{p}}_{*}^k$. Since $l\in {\mathcal{I}}^j$, $p_l^{*}\ge p_{*}^j\Rightarrow p_{*}^j<{\widehat{p}}_{*}^k$, and $i\in {\mathcal{I}}^k\Rightarrow p_i^{*}\ge {\widehat{p}}_{*}^k$. Therefore, we have that the ordering implied by (23) holds, and,

$${\widehat{p}}_{*}^j\le {\widehat{p}}_l^{*}<{\widehat{p}}_{*}^k\le {\widehat{p}}_i^{*},$$

(41)

for any buyer $\widehat{l}\in {\lambda }^k$ such that $\widehat{l}\ni {\mathcal{I}}^k$. Market shifts will occur due to the new reserve prices chosen in auction $\widehat{k}$ according to Proposition 1 until the market reaches equilibrium, and so (41) holds ⇒ (39) holds. In effect, the transfer of data has forced the reserve prices of ${\Lambda }^j$ and ${\Lambda }^k$ to “squeeze” together, with the broker profiting off of the difference. Sellers in ${\Lambda }^j$ lower their reserve prices, according to the lower demand. At the same time, buyers in ${\lambda }^k$ lower their bid prices according to the increased supply of data. The sets ${\Lambda }^k$ and ${\Lambda }^j$ are connected via auction $\widehat{k}$, and so the reserve price determined in auction $\widehat{k}$ will affect ${\Lambda }^j$ through the bid price of buyers in $\widehat{\mathcal{I}}$. We have, by transfer of data, for all $i\in {\Delta }^{*}$,

$${\displaystyle {\int }_0^{{\sigma }_i^j\left(a\right)}{\theta }_i^{\prime }\left(x\right)dx-{\int }_0^{{\sigma }_i^j\left(a\right)-{\widehat{\sigma }}_i^k\left(a\right)}{\overline{P}}_i\left(x\right)dx<ϵ,}$$

and,

$${\displaystyle {\int }_0^{{\sigma }_i^k\left(a\right)}{\theta }_i^{\prime }\left(x\right)dx-{\int }_0^{{\sigma }_i^k\left(a\right)+{\widehat{\sigma }}_i^k\left(a\right)}{\overline{P}}_i\left(x\right)dx<ϵ.}$$

Using Proposition 1, we may conclude that equilibrium is achieved and so (36)–(38) hold for the sets ${\Delta }^j$ and ${\Delta }^k$ connected through auction $\widehat{k}$, and we have the existence of at least one Nash equilibrium in ${\Delta }^{*}$. □

In this scenario, the presence of a broker causes the two sets ${\Delta }^j$ and ${\Delta }^k$ to become connected, arriving at a Nash equilibrium for ${\Delta }^{*}={\Delta }^k\cup {\Delta }^j$. These connected sets are defined by the influencing users around the auctions k and j, and are dynamically defined as such. This complicates the analysis and makes it difficult to determine stability in time. By restricting the transfer of data to two auctions within two auction subsets, we manage to create some sort of structure in the underlying market dynamics that is intuitively simple, however analytically difficult to describe.

6. Conclusions and Future Work

Mathematically, we have shown that if truthfulness holds locally for both buyers and sellers, i.e., $p_i={{\theta }_i}^{\prime },\forall j\in {\mathcal{I}}_i$ and $p^j={{\theta }^j}^{\prime },\forall i\in {\mathcal{I}}^j$, then, in the absence of market shifts, there exists an $ϵ$-Nash equilibrium extending over a subset of connected local markets. We have provided the analysis for a network that is operated according to a game theoretic paradigm, so that its Nash equilibrium upholds the requirements of a second price auction, showing characteristics of efficiency, truthfulness and rationality with respect to certain system-wide criteria. We have focused on Nash equilibria whose uniqueness has been established, such as those for users with consistent bids [12]. We show that ${s|}_{\Delta }$ represents a continuous mapping ${\displaystyle {[0,\sum _{k\in {\lambda }^j}{D}^k]}_{i\in {\Lambda }^j}}$ onto itself, and that the continuous mapping of the convex compact set $s_{*}$ into itself ($s^{*}$) has at least one fixed point. We show that the symmetry built into strategy space provides built-in conditions for convergence and stability of a $ϵ$-Nash equilibrium over pairwise connected subsets ${\Delta }^{*}$.

The dynamics of the system with the inclusion of brokers provides an interesting direction for future research. We speculate that certain network-wide objectives may be achieved (such as stability, bandwidth regulation, throttling) through the use of brokers. The brokers would exercise a type of feedback control, both a priori (in the static analysis) or in time, in order to maintain a desired network topology; one with a stable network-wide equilibrium. Here, we have examined the relation between two connected auction subsets under allocation constraints. We expect that with the addition of more players the strategy space will begin to suffer “the curse of dimensionality”, rendering the analytic techniques we have used here (based on order and continuity) ineffective.

We would like to begin real-world simulations of the results presented in this paper, and extend our theory to include some practical, statistical analysis. In particular, we would like to add queueing theory and an underlying Poisson arrival process or Brownian motion [12], in order to add practical structure and timing to our game. This practical experience may give us insight as to the breadth and variation of the game according to the user strategy of truthfulness. An alternative method to determining Nash equilibria in the higher-dimensional strategy space (with more users) could be found, and the nature of the space could be described using simulated results.