Analysis and Design of a Distributed kWTA With Application in Sealed-Bid Auctions With Bidding Price Privacy Protection.

Abstract

This article presents a distributed k-winner-take-all (kWTA) with application in sealed-bid auctions with bidding price privacy protection. The proposed kWTA is in essence a distributed network of n agents which are arbitrarily connected. Let $\aleph _{i}$ be the set of neighbor agents of the ith agent, $u_{i}$ , $x_{i}$ , and $z_{i}$ are, respectively, its input, state variable, and output. The dynamics of the ith agent is given by $ ((dx_{i}(t))/dt) = \tau \left \{{{ z_{i}(x_{i}(t)) - (k/n) - \beta \sum _{j\in \aleph _{i}} (x_{i}(t) - x_{j}(t)) }}\right \}, z_{i}(x_{i}(t)) = h(u_{i}-x_{i}(t)), \text {for}~i = 1, \ldots , n$ where $\beta \gt 0$ , k is the number of winners and $h(\cdot)$ is the Heaviside function. By the theory of discontinuous dynamic systems, it is shown that the state equation for $d{\mathbf {x}}(t)/dt$ could be formulated as a gradient differential inclusion which minimizes the following nonsmooth convex function. $V({\mathbf {x}}) = \sum _{i=1}^{n} \max \{0, u_{i} - x_{i}\} + (k/n) \sum _{i=1}^{n} x_{i} + (\beta /2){\mathbf {x}}^{T} {\mathbf {L}} {\mathbf {x}}$ where ${\mathbf {x}} = (x_{1}, \ldots , x_{n})^{n}$ and ${\mathbf {L}} \in R^{n\times n}$ is the graph Laplacian matrix. A sufficient condition for $\beta $ is derived for the kWTA giving correct output and the condition is then applied in showing that ${\mathbf {z}}(t)$ converges to the correct output in finite-time. If $\beta \rightarrow \infty $ and $x_{1}(0) = \cdots = x_{n}(0)$ , we further show that $x_{1}(t) = \cdots = x_{n}(t)$ for $t \geq 0$ , and both ${\mathbf {z}}(t)$ and ${\mathbf {x}}(t)$ converge in finite-time. Besides, $x_{i}$ converges to $u_{\pi _{n-k+1}}$ (resp. $u_{\pi _{n-k}}$ ) if $x_{i}(0) \gg 1$ (resp. $x_{i}(0) = 0)$ for $i = 1, \ldots , n$ . If the input $u_{i}$ is set to be the bid price of the ith bidder and $k = 1$ , the proposed kWTA is able to determine both the winners and the clearing price for a sealed-bid first (resp. second) price auction in a distributed manner. Once ${\mathbf {z}}(t)$ and ${\mathbf {x}}(t)$ converge, each bidder can reveal from: 1) $z_{i}$ if he/she is a winner and 2) $x_{i}$ the clearing price. As bidders do not have to disclose their bidding prices during the winner (resp. the clearing price) determination process, the loosing (resp. winning) bidding price privacy can be protected in a sealed-bid first (resp. second) price auction. It is insofar the first application of an kWTA beyond the winner's determination.