Combinatorial auctions without money

摘要: Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer selfish agents involved. This is principally because in absence of money, very little can be done enforce truthfulness. However, certain applications, money unavailable, morally unacceptable or might simply at odds with the objective mechanism. For example, Combinatorial Auctions (CAs), paradigmatic problem area, we aim solutions maximum social welfare, but still charge society ensure We focus on design incentive-compatible CAs without general setting k-minded bidders. trade observation that mechanism detect lies bidders: i.e., study truthful verification money. In this setting, characterize class mechanisms give a host upper lower bounds approximation ratio obtained either deterministic randomized mechanisms. Our results provide an almost complete picture truthfully approximating multi-dimensional