Auctions are believed to be effective methods to solve the problem of wireless spectrum allocation. Existing spectrum auction mechanisms are all centralized and suffer from several critical drawbacks of the centralize...
详细信息
Auctions are believed to be effective methods to solve the problem of wireless spectrum allocation. Existing spectrum auction mechanisms are all centralized and suffer from several critical drawbacks of the centralized systems, which motivates the design of distributed spectrum auction mechanisms. However, extending a centralized spectrum auction to a distributed one broadens the strategy space of agents from one dimension (bid) to three dimensions (bid, communication, and computation), and thus cannot be solved by traditional approaches from mechanismdesign. In this paper, we propose two distributed spectrum auction mechanisms, namely distributed VCG and FAITH. distributed VCG implements the celebrated Vickrey-Clarke-Groves mechanism in a distributed fashion to achieve optimal social welfare, at the cost of exponential communication overhead. In contrast, FAITH achieves sub-optimal social welfare with tractable computation and communication overhead. We prove that both of the two proposed mechanisms achieve faithfulness, i.e., the agents' individual utilities are maximized, if they follow the intended strategies. Besides, we extend FAITH to adapt to dynamic scenarios where agents can arrive or depart at any time, without violating the property of faithfulness. We implement distributed VCG and FAITH, and evaluate their performance in various setups. Evaluation results show that distributed VCG results in optimal allocation, while FAITH is more efficient in computation and communication.
Auctions are believed to be effective methods to solve the problem of wireless spectrum *** spectrum auction mechanisms are all centralized and suffer from several critical drawbacks of the centralized systems, which ...
详细信息
Auctions are believed to be effective methods to solve the problem of wireless spectrum *** spectrum auction mechanisms are all centralized and suffer from several critical drawbacks of the centralized systems, which motivates the design of distributed spectrum auction ***, extending a centralized spectrum auction to a distributed one broadens the strategy space of agents from one dimension (bid) to three dimensions (bid,communication, and computation), and thus cannot be solved by traditional approaches from mechanism *** this paper, we propose two distributed spectrum auction mechanisms, namely distributed VCG and *** VCG implements the celebrated Vickrey-Clarke-Groves mechanism in a distributed fashion to achieve optimal social welfare, at the cost of exponential communication *** contrast,FAITH achieves sub-optimal social welfare with tractable computation and communication *** prove that both of the two proposed mechanisms achieve faithfulness, i.e., the agents' individual utilities are maximized, if they follow the intended *** also implement FAITH and evaluate its performance in various *** results show that FAITH achieves superior performance compared with the Nash equilibrium based approach.
We present a game-theoretic model that captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffi...
详细信息
We present a game-theoretic model that captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. The interaction between the agents is dynamic and complex-asynchronous, sequential, and based on partial information. Best-reply dynamics in this model capture crucial aspects of the de facto standard interdomain routing protocol, namely, the Border Gateway Protocol (BGP). We study complexity and incentive-related issues in this model. Our main results show that in realistic and well-studied settings, BGP is incentive-compatible. That is, not only does myopic behavior of all players converge to a "stable" routing outcome, but no player has motivation to unilaterally deviate from BGP. Moreover, we show that even coalitions of players of any size cannot improve their routing outcomes by collaborating. Unlike the vast majority of works in mechanismdesign, our results do not require any monetary transfers (to or by the agents).
We present a game-theoretic model that Captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffi...
详细信息
ISBN:
(纸本)9781605580470
We present a game-theoretic model that Captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. The interaction between the agents is dynamic and complex - asynchronous, sequential, and based on partial information. Best-reply dynamics in this model capture crucial aspects of the interdomain routing protocol de facto, namely the Border Gateway Protocol (BGP). We study complexity and incentive-related issues it) this model. Our main results are showing that in realistic and well-studied settings, BGP is incentive-compatible. Le., not only does myopic behaviour of all players converge to a "stable" routing outcome, but no player has motivation to unilaterally deviate front the protocol. Moreover, we show that even coalitions of players of any size cannot improve their routing outcomes by collaborating. Unlike the vast majority of works in mechanismdesign, our results do not;require any monetary transfers (to or by the agents).
algorithmicmechanismdesign focuses on Dominant Strategy Implementations. The main positive results are the celebrated Vickrey-Clarke-Groves (VCG) mechanisms and computationally efficient mechanisms for severely rest...
详细信息
ISBN:
(纸本)9781595930491
algorithmicmechanismdesign focuses on Dominant Strategy Implementations. The main positive results are the celebrated Vickrey-Clarke-Groves (VCG) mechanisms and computationally efficient mechanisms for severely restricted players ("single-parameter domains"). As it turns out, many natural social goals cannot be implemented using the dominant strategy concept [35, 32, 22, 20]. This suggests that the standard requirements must be relaxed in order to construct general-purpose *** observe that in many common distributed environments computational entities can take advantage of the network structure to collect and distribute information. We thus suggest a notion of partially informed environments. Even if the information is recorded with some probability, this enables us to implement a wider range of social goals, using the concept of iterative elimination of weakly dominated strategies. As a result, cooperation is achieved independent of agents' belief. As a case study, we apply our methods to derive Peer-to-Peer network mechanism for file sharing.
暂无评论