Sum John, Leung Chi-Sing, Chang Janet C C
IEEE Trans Neural Netw Learn Syst. 2025 Apr 15;PP. doi: 10.1109/TNNLS.2025.3554440.
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.
本文提出了一种分布式胜者全得（kWTA）机制，并将其应用于具有投标价格隐私保护的密封投标拍卖中。所提出的kWTA本质上是一个由n个任意连接的代理组成的分布式网络。设$\aleph {i}$为第i个代理的邻居代理集合，$u{i}$、$x_{i}$和$z_{i}$分别为其输入、状态变量和输出。第i个代理的动态方程为$ ((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))$，其中$i = 1, \ldots, n$，$\beta \gt 0$，k为获胜者数量，$h(\cdot)$为海维赛德函数。通过不连续动态系统理论表明，$d{\mathbf {x}}(t)/dt$的状态方程可表述为一个梯度微分包含，它使以下非光滑凸函数最小化。$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}}$，其中${\mathbf {x}} = (x_{1}, \ldots, x_{n})^{n}$，${\mathbf {L}} \in R^{n\times n}$是图拉普拉斯矩阵。推导了kWTA给出正确输出时$\beta$的充分条件，并将该条件应用于证明${\mathbf {z}}(t)$在有限时间内收敛到正确输出。如果$\beta \rightarrow \infty$且$x_{1}(0) = \cdots = x_{n}(0)$，我们进一步证明对于$t \geq 0$有$x_{1}(t) = \cdots = x_{n}(t)$，并且${\mathbf {z}}(t)$和${\mathbf {x}}(t)$都在有限时间内收敛。此外，如果对于$i = 1, \ldots, n$有$x_{i}(0) \gg 1$（分别地，$x_{i}(0) = 0$），则$x_{i}$收敛到$u_{\pi {n - k + 1}}$（分别地，$u{\pi {n - k}}$）。如果将输入$u{i}$设置为第i个投标人的投标价格且$k = 1$，则所提出的kWTA能够以分布式方式确定密封投标第一（分别地，第二）价格拍卖的获胜者和清算价格。一旦${\mathbf {z}}(t)$和${\mathbf {x}}(t)$收敛，每个投标人可以从以下方面得知：1）如果他/她是获胜者，则从$z_{i}$得知；2）从$x_{i}$得知清算价格。由于投标人在获胜者（分别地，清算价格）确定过程中不必披露其投标价格，所以在密封投标第一（分别地，第二）价格拍卖中可以保护失利（分别地，获胜）投标价格的隐私。就目前而言，这是kWTA在获胜者确定之外的首次应用。
