Computationally Manageable Combinational Auctions
分析组合拍卖中确定收入最大化不冲突投标集的计算复杂度问题，识别出几种可计算处理的投标结构，并指出某些结构无法保证计算可行性。
There is interest in designing simultaneous auctions for situations such as the recent FCC radio spectrum auctions, in which the value of assets to a bidder depends on which other assets he or she wins. In such auctions, bidders may wish to submit bids for combinations of assets. When this is allowed, the problem of determining the revenue maximizing set of nonconflicting bids can be difficult. We analyze this problem, identifying several different structures of permitted combinational bids for which computational tractability is constructively demonstrated and some structures for which computational tractability cannot be guaranteed.