We study the complexity of finding a Walrasian equilibrium in markets where the agents have $k$-demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its $k$-subsets' values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For $k=2$, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for $k=3$ the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.
翻译：我们研究了在代理商拥有K美元需求估值的市场中找到Walrasian平衡的复杂程度。这些估值是单位需求估值的延伸,在单位需求估值中,捆包的价值是美元子集价值的上限。对于单位需求代理,如果保证存在Walrasian平衡,我们表明问题在于准NC。对于美元=2美元,我们表明,即使估值为次模式,也很难决定是否存在Walrasian平衡,而对于美元=3美元,硬性则结转到预算追加估值。此外,我们为有2个需求单心估值或单位需求估值的市场提供多时算法。
相关内容
- Today (iOS and OS X): widgets for the Today view of Notification Center
- Share (iOS and OS X): post content to web services or share content with others
- Actions (iOS and OS X): app extensions to view or manipulate inside another app
- Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
- Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
- Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
- Custom Keyboard (iOS): system-wide alternative keyboards
Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
微信扫码咨询专知VIP会员