Coalition Formation for Cooperative Service-based Message Sharing in Vehicular Ad Hoc Networks Reliable message delivery is a challenging task in Vehicular Ad Hoc Networks (VANETs). Current literature on VANETs generalize all messages and use the same strategy to transmit them. In this paper, we model the cooperative service-based message sharing problem in VANETs as a coalition formation game among nodes. Nodes associate with a coalition based on the type of servicemessage they process. In the proposed model, service-messages are distinguished from one another by their types. Nodes process different types of service-messages and form a coalition based on the type of messages they process at that time. Some nodes within a coalition can work as a relay, which is modeled as a network formation game to select exactly one relay among a group of potential relay nodes to improve efficiency of the network in terms of improved packet reception rate and reducing transmission delay. The nodes form independent disjoint coalitions and tree structure is formed with the relay nodes within a coalition by using the proposed algorithm, COMES. Simulation results show that COMES, which allows nodes to form independent coalitions among themselves, improves the networkperformance in terms of incentive received by players by at least 40% compared to a non-cooperative function.