Search results for "Decision problem"
showing 2 items of 42 documents
Some Computational Aspects of DISTANCE-SAT
2007
In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones …
Evolution of impatience: The example of the Farmer-Sheriff game
2015
The literature on the evolution of impatience, focusing on one-person decision problems, often finds that evolutionary forces favor the more patient individuals. This paper shows that in games where equilibrium involves threat of punishment there are forces generating an evolutionary advantage to the impatient. In particular, it offers a two-population example where evolutionary forces favor impatience in one group while favoring patience in the other. Moreover, efficiency may also favor impatient individuals. In our example, it is efficient for one population to evolve impatience and for the other to develop patience. Yet, evolutionary forces move the opposite direction. Fil: Levine, David…