Logical methods for design and analysis of choice models

L. A. Sholomov

Prikladnaâ diskretnaâ matematika, no. 1 (2009), pp. 38-71.

Résumé

The logical methods use representations of choice functions and choice models by means of formulas of some logic language. The design and research problems for choice models are reduced to formal transformations and analysis of the presentations. The logical methods make it possible to solve a wide range of constructive problems associated with a design, an analysis, simplifications, and estimations of complexity for formal choice models. They allow to use to choice models the Shannon–Yablonsky–Lupanov methodology developed for investigation of computing systems. The article systematizes obtained at different times and published in different editions the author's results on a study of choice models by logical methods. Results of other authors concerning the topics are brought, also.

Bibliographie

[1] Murakami Y., Logic and cocial choice, Routledge Kegan Paul Ltd., London, Dover Publication Inc., New York, 1968

[2] Sholomov L. A., Logicheskie metody v zadachakh soglasovannogo vybora, Preprint, VNII sistemnykh issledovanii, M., 1978

[3] Berezovskii B. A., Baryshnikov Yu. M., Borzenko V. I., Kempner L. M., Mnogokriterialnaya optimizatsiya: matematicheskie aspekty, Nauka, M., 1989 | MR

[4] Makarov I. M., Vinogradskaya T. M., Rubchinskii A. M., Sokolov V. B., Teoriya vybora i prinyatiya reshenii, Nauka, M., 1982 | MR

[5] Levchenkov V. S., Algebraicheskii podkhod v teorii gruppovogo vybora, Nauka, M., 1990 | MR | Zbl

[6] Aleskerov F. T., Vladimirov A. V., “Hierarchical voting”, Information sciences, 39 (1986), 41–86 | DOI | MR | Zbl

[7] Sholomov L. A., Logicheskie metody issledovaniya diskretnykh modelei vybora, Nauka, M., 1989 | MR | Zbl

[8] Aizerman M. A., Volskii V. I., Litvakov B. M., Elementy teorii vybora. Psevdokriterii i psevdokriterialnyi vybor, Neftyanik, M., 1994

[9] Volskii V. I., Lezina Z. M., Golosovanie v malykh gruppakh: protsedury i metody sravnitelnogo analiza, Nauka, M., 1991

[10] Sholomov L. A., Primenenie logicheskikh metodov v zadachakh posledovatelnogo vybora, Preprint, VNII sistemnykh issledovanii, M.

[11] Sholomov L. A., Logicheskie metody kompozitsii funktsii vybora, Preprint, VNII sistemnykh issledovanii, M., 1981

[12] Sholomov L. A., “Otsenka slozhnostnykh kharakteristik odnogo mekhanizma vybora s uchastiem neskolkikh lits”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1985, no. 2, 3–13 | MR | Zbl

[13] Sholomov L. A., Yudin D. B., “Slozhnost mnogoshagovykh skhem obobschennogo matematicheskogo programmirovaniya”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1988, no. 1, 13–22 | MR | Zbl

[14] Sholomov L., “Context-independent choice: description and analysis by means of first-order logic”, Logic, Game theory and Social choice, Proceedings of the Intern. Conference LGS' 99, Tilburg University Press, 1999, 549–559

[15] Litvakov B. M., “Approksimatsiya funktsii vybora”, Avtomatika i telemekhanika, 1984, no. 9, 138–146 | MR | Zbl

[16] Sholomov L. A., “O slozhnosti zadach minimizatsii i szhatiya modelei posledovatelnogo vybora”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 6:3 (1999), 87–109 | MR | Zbl

[17] Stockmeyer L. J., The set-basis problem is NP-complete, Report No RC-5431, IBM Research Center, Yorctown Heights, New York, 1975

[18] Sholomov L. A., “O slozhnosti realizatsii funktsii vybora sistemoi otnoshenii chastichnogo poryadka”, Problemy kibernetiki, 41, Nauka, M., 1984, 111–116 | MR

[19] Sholomov L. A., “Funktsionalnye vozmozhnosti i slozhnost mekhanizmov vybora, osnovannykh na isklyuchenii khudshikh variantov”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1987, no. 1, 10–17 | MR

[20] Yudin D. B., Sholomov L. A., “Mnogoshagovye skhemy obobschennogo matematicheskogo programmirovaniya i funktsii vybora”, Dokl. AN SSSR, 282:5 (1985), 1066–1069 | MR | Zbl

[21] Arrow K. J., “Difficulty in the concept of social welfare”, J. Political Economy, 58 (1950), 326–346 | DOI

[22] Arrow K. J., Social Choice and Individual Values, 2nd ed, Yale University Press, New Haven–London, 1963 | MR

[23] Aizerman M. A., Aleskerov F. T., Vybor variantov: osnovy teorii, Nauka, M., 1990 | MR | Zbl

[24] Fishbern P., Teoriya poleznosti dlya prinyatiya reshenii, Nauka, M., 1978 | MR

[25] Sholomov L. A., “Operatory nad otnosheniyami, sokhranyayuschie tranzitivnost”, Diskretnaya matematika, 10:1 (1998), 28–45 | DOI | MR | Zbl

[26] Sholomov L. A., “Issledovanie otnoshenii v kriterialnykh prostranstvakh i sintez operatorov gruppovogo vybora”, Matematicheskie voprosy kibernetiki, 5, Fizmatlit, M., 1995, 109–143

[27] Sholomov L. A., “Agregirovanie lineinykh poryadkov v zadachakh gruppovogo vybora”, Avtomatika i telemekhanika, 1998, no. 2, 113–122 | MR | Zbl

[28] Sholomov Lev A., “Explicit form of neutral social decision rules for basic rationality conditions”, Mathematical Social Sciences, 39:1 (2000), 81–107 | DOI | MR | Zbl

[29] Morkyalyunas A., “Gruppovoi vybor pri nezavisimosti i slaboi simmetrii alternativ”, Matematicheskie metody v sotsialnykh naukakh, 18, In-t matematiki i kibernetiki AN LitSSR, Vilnyus, 1985, 57–60 | Zbl

[30] Danilov V. I., “Modeli gruppovogo vybora”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1983, no. 1, 143–164 | MR | Zbl

[31] Vladimirov A. V., Issledovanie protsedur postroeniya kollektivnykh reshenii, Avtoref. dis. $\dots$ kand. tekhn. nauk, In-t problem upravleniya, M., 1987 | Zbl

[32] Sholomov L. A., “O slozhnosti realizatsii binarnykh otnoshenii putem teoretiko-mnozhestvennykh operatsii nad otnosheniyami lineinogo poryadka”, Problemy kibernetiki, 41, Nauka, M., 1984, 101–109 | MR

[33] Sholomov L. A., “O predstavlenii binarnogo otnosheniya naborom kriteriev”, Izv. AN SSSR. Tekhnicheskaya kibernetika, 1984, no. 1, 6–14 | MR | Zbl

[34] Hiraguchi T., “On the dimension of partially ordered sets”, Sci Rep. Kanazawa University, 1:2 (1951), 77–94 | MR | Zbl

[35] Ore O., Teoriya grafov, Nauka, M., 1980 | MR

[36] Trotter W. T., “Embedding finite posets in cubes”, Discrete Math., 12:2 (1975), 165–172 | DOI | MR | Zbl

[37] Erdős P., Moser L., “On the representation of directed graphs as unions orderings”, Magyar tud. akad. Mat. kutató int. közl, 9:1–2 (1964), 125–132 | MR | Zbl

[38] Sholomov L. A., “Dekompozitsiya otnoshenii v zadachakh vybora: vpolne razdelimye otnosheniya i nezavisimost ot puti”, Avtomatika i telemekhanika, 2001, no. 11, 154–164 | MR | Zbl

[39] Sholomov L. A., “Analiz ratsionalnosti modeli posledovatelnogo vybora”, Avtomatika i telemekhanika, 2000, no. 5, 124–132 | MR | Zbl

[40] Sholomov L. A., “Predstavlenie i issledovanie poryadkovykh modelei vybora sredstvami logiki pervogo poryadka”, Matematicheskie voprosy kibernetiki, 7, Nauka, Fizmatlit, M., 1998, 169–202 | MR

[41] Maltsev A. I., Algebraicheskie sistemy, Nauka, M., 1970 | MR

[42] Bulos Dzh., Dzheffri R., Vychislimost i logika, Mir, M., 1994

[43] Sholomov L. A., “Slozhnost raspoznavaniya svoistv poryadkovykh otnoshenii v $n$-mernykh prostranstvakh”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 9:4 (2002), 82–105 | MR | Zbl

[44] Podinovskii V. V., “Mnogokriterialnye zadachi s odnorodnymi ravnotsennymi kriteriyami”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 15:2 (1975), 130–141 | MR

[45] Podinovskii V. V., “Mnogokriterialnye zadachi s uporyadochennymi po vazhnosti kriteriyami”, Avtomatika i telemekhanika, 1976, no. 11, 118–127 | MR | Zbl

[46] Sholomov L. A., “Sintez tranzitivnykh poryadkovykh otnoshenii, soglasovannykh s informatsiei o sile kriteriev”, Sibirskii zhurnal issledovaniya operatsii, 1:4 (1994), 64–92 | MR | Zbl

[47] Sholomov L. A., “Metod interpretatsii v zadache sinteza operatorov gruppovogo vybora”, Algebra i teoriya modelei, 6, NGTU, Novosibirsk, 2007, 96–110

[48] Sholomov L. A., “Logicheskie metody issledovaniya otnoshenii v kriterialnykh prostranstvakh s poryadkovymi shkalami proizvolnogo vida”, Avtomatika i telemekhanika, 2004, no. 5, 120–130 | MR

[49] Sholomov L. A., “Raspoznavanie svoistv poryadkovykh otnoshenii v diskretnykh prostranstvakh”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 11:3 (2004), 88–110 | MR

[50] Sholomov L. A., “Teoretiko-modelnyi podkhod k opisaniyu poryadkovykh otnoshenii v konechnoznachnykh prostranstvakh”, Sintaksis i semantika logicheskikh sistem, Materialy Rossiiskoi shkoly-seminara, posvyaschennoi Yu. E. Shishmarevu, Dalnauka, Vladivostok, 2008, 28–29