The cost of incentive compatibility in auction-based mechanisms for carrier collaboration

Collaboration has been one of the important trends in vehicle routing. A typical mechanism to enable carrier collaboration is to use combinatorial auctions, where requests are not traded individually but are combined into bundles. Previous literature on carrier collaboration has focused on issues such as bundle formation or winner determination, typically assuming truthfulness of all agents and absence of any strategic behavior. This article considers the interdependencies and problems that arise from bidders acting as buyers and sellers of requests at the same time. From standard auction theory, desirable properties of exchange mechanisms are identified as efficiency, incentive compatibility, individual rationality, and budget balance. It is shown that these desirable properties cannot be fulfilled at the same time. In particular, the properties efficiency and incentive compatibility induce that budget balance is violated, that is, an outside subsidy is required. We propose two incentive compatible exchange mechanisms. One is more closely related to the classical VCG approach, while the other one uses a more complicated concept for computing payments to participants. A numerical study investigates how frequently desired properties are violated. We show that both mechanisms can be acceptable in practical situations, but none of them can satisfy all desired properties.