Loading...
Please wait, while we are loading the content...
Similar Documents
On the computational complexity of the bargaining set and the kernel in compact coalitional games (810).
| Content Provider | CiteSeerX |
|---|---|
| Author | Malizia, Enrico Palopoli, Luigi Scarcello, Francesco |
| Abstract | This paper deals with the complexity of cooperative solution concepts, notably, the bargaining set and the kernel, for coalitional games in compact form. In [4], Deng and Papadimitriou have left open a number of issues regarding those concepts which this paper provides a thorough answer to. Open issues (and correspondent answers we provide) are as follows. Given a graph game G and an imputation x: (a) it was conjectured that checking for x to belong to the bargaining set BSG of G is ΠP 2-complete—the conjecture will be shown to hold; (b) it was conjectured that checking for x to belong to the kernel KG of G is NP-hard—the conjecture will be shown to hold, in particular, by proving the tighter bound that it is in fact ∆P 2-complete; (c) it was asked for the complexity of checking x to belong to either BSG or KG (membership, as the hardness are immediately implied by (a) and (b) above) for games G in general compact form, where the game is given implicitly by an algorithm for computing v(S) 1 —we formally define such general compact games and prove that those complexities are in ΠP 2 and ∆P 2, resp., provided that the worth-computing algorithm runs in non-deterministic polynomial time. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Bargaining Set Computational Complexity Compact Coalitional Game Correspondent Answer Non-deterministic Polynomial Time Compact Form General Compact Game Graph Game Coalitional Game Cooperative Solution Concept Thorough Answer Kernel Kg Tighter Bound Worth-computing Algorithm Run General Compact Form |
| Content Type | Text |
| Resource Type | Article |
