×

zbMATH — the first resource for mathematics

Non-reversible betting games on fuzzy events: complexity and algebra. (English) Zbl 1237.91064
Summary: A bad bet is a bet for which we can find an alternative system of bets over the same class of events ensuring to the bettor a strictly better payoff, independently on the truth values of the events involved. In this paper we study the computational complexity for the problem of deciding whether a book arranged on fuzzy events avoids bad bets or not. Call admissible a book that avoids bad bets. Following the approach initiated by Mundici and pursued by Flaminio and Bova for reversible betting situations, we settle the complexity of the admissibility-problem to be NP-complete. We also present a variety of algebras, and an algebraizable modal logic, that allow us to characterize admissible books in terms of 1-satisfiability of suitable defined theories. Studying the computational complexity for the 1-satisfiability problem of a formula in this variety, we provide a second, algebraic-based, NP algorithm to check admissible books.

MSC:
91A60 Probabilistic games; gambling
68Q25 Analysis of algorithms and problem complexity
60A86 Fuzzy probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Blok, W.; Pigozzi, D., Algebraizable logics, Mem. am. math. soc., 396, 77, (1989), (Am. Math Soc. Providence) · Zbl 0664.03042
[2] Bova, S.; Flaminio, T., The coherence of łukasiewicz assessment is NP-complete, Int. J. approximate reason., 51, 294-304, (2010) · Zbl 1201.68117
[3] Burris, S.; Sankappanavar, H.P., A course in universal algebra, (1981), Springer-Velag New York · Zbl 0478.08001
[4] Chang, C.C., Algebraic analysis of many-valued logics, Trans. am. math. soc., 88, 467-490, (1958) · Zbl 0084.00704
[5] Cignoli, R.; D’Ottaviano, I.M.L.; Mundici, D., Algebraic foundations of many-valued reasoning, (2000), Kluwer · Zbl 0937.06009
[6] M. Fedel, K. Keimel, F. Montagna, W. Roth, Imprecise probabilities, bets and functional analytic methods in Łukasiewicz logic, 2010, under review. \(\langle\)http://www.mathematik.tu-darmstadt.de/∼keimel/publications.html⟩. · Zbl 1266.06011
[7] M. Fedel, Uncertainty, indeterminacy and fuzziness: a probabilistic approach, in: H. Hosni, F. Montagna (Eds.), Probability, Uncertainty and Rationality, Publications of the Scuola Normale Superiore, CRM Series, Springer, 2010. · Zbl 1206.03023
[8] Flaminio, T.; Montagna, F., MV-algebras with internal states and probabilistic fuzzy logics, Int. J. approximate reason., 50, 138-152, (2009) · Zbl 1185.06007
[9] T. Flaminio, F. Montagna, Models for Many-valued Probabilistic Reasoning. J. Logic Comput., doi:10.1093/logcom/exp013. · Zbl 1237.06005
[10] Hájek, P., Metamathematics of fuzzy logic, (1998), Kluwer · Zbl 0937.03030
[11] Hájek, P., Complexity of fuzzy probabilistic logics II, Fuzzy sets and systems, 158, 23, 2605-2611, (2007) · Zbl 1124.03008
[12] Kühr, J.; Mundici, D., De Finetti theorem and Borel states in [0, 1]-valued algebraic logic, Int. J. approximate reason., 46, 3, 605-616, (2007) · Zbl 1189.03076
[13] McNaughton, R., A theorem about infinite-valued sentential logic, J. symb. log., 16, 1-13, (1951) · Zbl 0043.00901
[14] Mundici, D., Averaging the truth-value in łukasiewicz logic, Studia logica, 55, 1, 113-127, (1995) · Zbl 0836.03016
[15] Mundici, D., Tensor products and the loomis – sikorski theorem for MV-algebras, Adv. appl. math., 22, 227-248, (1999) · Zbl 0926.06004
[16] Mundici, D., Bookmaking over infinite-valued events, Int. J. approximate reason., 43, 223-240, (2006) · Zbl 1123.03011
[17] Paris, J.B., The uncertain Reasoner’s companion—A mathematical perspective, (1994), Cambridge University Press · Zbl 0838.68104
[18] Schrijver, A., Theory of linear and integer programming, (1998), Wiley · Zbl 0970.90052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.