124 research outputs found
Semantical and computational aspects of Horn approximations
No full textSelman and Kautz proposed a method, called Horn approximation, for speeding up inference in propositional Knowledge Bases. Their technique is based on the compilation of a propositional formula into a pair of Horn formulae: a Horn Greatest Lower Bound (GLB) and a Horn Least Upper Bound (LUB). In this paper we focus on GLBs and address two questions that have been only marginally addressed so far: (1) what is the semantics of the Horn GLBs? (2) what is the exact complexity of finding them? We obtain semantical as well as computational results. The major semantical result is: The set of minimal models of a propositional formula and the set of minimum models of its Horn GLBs are the same. The major computational result is: Finding a Horn GLB of a propositional formula in CNF is NP-equivalent, (C) 2000 Elsevier Science B.V. All rights reserved
Computing the Shapley Value in Allocation Problems: Approximations and Bounds, with an Application to the Italian VQR Research Assessment Program
No full textIn allocation problems, a given set of goods are assigned to agents in such a
way that the social welfare is maximised, that is, the largest possible global
worth is achieved. When goods are indivisible, it is possible to use money
compensation to perform a fair allocation taking into account the actual
contribution of all agents to the social welfare. Coalitional games provide a
formal mathematical framework to model such problems, in particular the Shapley
value is a solution concept widely used for assigning worths to agents in a
fair way. Unfortunately, computing this value is a -hard problem, so
that applying this good theoretical notion is often quite difficult in
real-world problems.
We describe useful properties that allow us to greatly simplify the instances
of allocation problems, without affecting the Shapley value of any player.
Moreover, we propose algorithms for computing lower bounds and upper bounds of
the Shapley value, which in some cases provide the exact result and that can be
combined with approximation algorithms.
The proposed techniques have been implemented and tested on a real-world
application of allocation problems, namely, the Italian research assessment
program, known as VQR. For the large university considered in the experiments,
the problem involves thousands of agents and goods (here, researchers and their
research products). The algorithms described in the paper are able to compute
the Shapley value for most of those agents, and to get a good approximation of
the Shapley value for all of them
Computing the shapley value in allocation problems: Approximations and bounds, with an application to the Italian VQR research assessment program
No full textIn allocation problems, a given set of goods are assigned to agents in such a way that the social welfare is maximized, that is, the largest possible global worth is achieved. When goods are indivisible, it is possible to use money compensation to perform a fair allocation taking into account the actual contribution of all agents to the social welfare. Coalitional games provide a formal mathematical framework to model such problems, in particular the Shapley value is a solution concept widely used for assigning worths to agents in a fair way. Unfortunately, computing this value is a #P-hard problem, so that applying this good theoretical notion is often quite difficult in real-world problems. In this paper, we first review the application of the Shapley value to an allocation problem that models the evaluation of the Italian research structures with a procedure known as VQR. For large universities, the problem involves thousands of agents and goods (here, researchers and their research products). We then describe some useful properties that allow us to greatly simplify many such large instances. Moreover, we propose new algorithms for computing lower bounds and upper bounds of the Shapley value, which in some cases provide the exact result and that can be combined with approximation algorithms. The proposed techniques have been tested on large real-world instances of the VQR research evaluation problem
On the complexity of core, kernel, and bargaining set
No full textCoalitional games model scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental issue of coalitional games is to single out the most desirable outcomes in terms of worth distributions, usually called solution concepts. Since decisions taken by realistic players cannot involve unbounded resources, recent computer science literature advocated the importance of assessing the complexity of computing with solution concepts. In this context, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonably compact form. The starting points of the investigation are the settings of graph games and of marginal contribution nets, where the worth of any coalition can be computed in polynomial time in the size of the game encoding and for which various open questions were stated in the literature. The paper answers these questions and, in addition, provides new insights on succinctly specified games, by characterizing the computational complexity of the core, the kernel, and the bargaining set in relevant generalizations and specializations of the two settings. Concerning the generalizations, the paper shows that dealing with arbitrary polynomial-time computable worth functions—no matter of the specific game encoding being considered—does not provide any additional source of complexity compared to graph games and marginal contribution nets. Instead, only for the core, a slight increase in complexity is exhibited for classes of games whose worth functions encode NP-hard optimization problems, as in the case of certain combinatorial games. As for specializations, the paper illustrates various tractability results on classes of bounded treewidth graph games and marginal contribution networks
Hard and Easy k-Typed Compact Coalitional Games: The Knowledge of Player Types Marks the Boundary
No full textNon-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
No full textCoalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions.
In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts
Constrained Coalitional Games: Formal Framework, Properties, and Complexity Results (Extended Abstract)
No full text- …
