Multicast Mechanism Design With Optimization Of Payments

Multicast is a type of one-to-many communication method where data trans-mission is addressed to a group of destination nodes simultaneously.The problem of multicast mechanism design is about designing a mechanism,in which a source and a set of client nodes should be connected by edges.Multicast can save bandwidth resources and transmit data more efficiently.Therefore,the study of multicast mechanism design is of great significance.The difficulty of multicast mechanism design problem lies in optimizing the payments of multicast mech-anism while ensuring that the mechanism has good incentive properties.This paper studies multicast mechanism design from the perspective of Bayesian game and cooperative game.First,this paper considers nodes as selfish agents and models the auction as a single-parameter auction in a Bayesian setting.This pa-per proposes optimal truthful mechanism which is computationally intractable,and gives several incentive compatible mechanisms which are computationally tractable and approximately optimal.Second,this paper considers the edges in the multicast network as selfish agents and studies the problem from the per-spective of cooperative game.This paper designs false-name-proof mechanisms to solve shill bidding problem,where the VCG mechanism is vulnerable to shill bidding and causes overpayment.Simulation results show that the mechanisms proposed in this paper have lower payment than the VCG mechanism.The main work of this paper is as follows:1.For the setting where nodes are considered as selfish agents,this pa-per proposes the optimal mechanism for the multicast auction using a Bayesian method.The optimal mechanism is proven to be individually rational,incentive compatible,cost-optimal and computationally inefficient.2.To solve the problem of computationally inefficiency of optimal mechanism for the Bayesian multicast routing problem,several approximation mechanisms are proposed in this paper,which are proven to be individually rational,incentive compatible,approximately optimal and computationally efficient.Experiments show that the e-1/2-RRM mechanism is more frugal than other approximation mechanisms proposed in this paper.3.For the setting where agents hold edges,the paper proves that VCG mechanism is vulnerable to shill bidding and causes high overpayment,and that core-selecting multicast mechanisms pay less than VCG mechanism and are robust against shill bidding.This paper analyzes the core constraints and give equivalent form of core constraints which significantly reduce the number of constraints.4.Based on the analysis of equivalent core constraints,this paper proposes MMRV mechanism which is a type of core-selecting mechanism and can mini-mize the regret for bidders bidding truthfully.The proposed MMRV mechanism improves significantly over the VCG method in terms of the cost of constructed multicast tree.The MMRV mechanism is implemented with Core Constraint Generation algorithm.