Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

elemi valószínűségelmélet, nagy számok legegyszerűbb gyenge törvényei, elemi diszkrét matematika, (irányított) gráfelmélet, szeparációs tételek véges dimenzióban.

A tantárgy célja, hogy bevezesse a hallgatóságot a társadalmi választás elméletének legfontosabb területeibe, alapvető szempontjaiba, módszereibe, főleg diszkrét matematikai eszközöket használva. Körüljárjuk, hogy mit lehet és mit nem lehet megvalósítani a meglévő diszkrét modell keretei között, megállapítjuk néhány adott szavazási rendszer előnyös és előnytelen tulajdonságait

1. hét. Többségi szavazás, McGarvey tétele a többségi reláció alakjáról, Erdős tétele

2. bajnokságok aciklikus részhalmazainak nagyságáról, l-többségi bajnokságok.

3. hét. Elégséges feltételek a többségi reláció kvázitranzitivitására; egycsúcsú preferenciák, utakon és fagráfokon, preferenciák aciklikus halmazai.
4. hét. Szükséges és elegendő feltétel arra, hogy egy egészértékű vektor valamely bajnokság tabellája legyen.
5. hét. Bajnokságok győzteseinek megkeresése. Az Erdős - féle -tulajdonság. Smith - konzisztencia, a felső kör, a lefedetlen halmaz, a Copeland halmaz.
6. hét. Bajnokságok győzteseinek megkeresése. A minimális fedő halmaz, a Banks – féle halmaz.
7. hét. Egymásutáni páronkénti összehasonlításokon alapuló szavazások. A Shepsle-Weingast tétel. Őszinte és stratégiai szavazások.
8. hét. Összjóléti függvények. May tétele a kétalternatívás többségi szavazásról. Arrow lehetetlenségi tétele. Lehetetlenségi tételek diktátorokról és oligarchiákról.
9. hét. Szavazási szabályok manipulálhatósága. A Gibbard-Satterthwaite tétel és annak variánsai.
10. hét. Az Arrow tétel általánosításai és variánsai.
11. hét. A Gibbard-Satterthwaite tétel általánosításai és variánsai.
12. hét. Egyszerű koalíciós játékok. A játékosok erősségi relációja. Súlyozott egyszerű játékok.
13. hét. Implementációelmélet. Nash – egyensúlyi állapotok, Maskin tétele.
14. hét. Igen-nem szavazás bizonytalan preferenciák esetén.
15. hét. Condorcet – konzisztens szavazási szabályok.
16. hét. A Borda – féle összjóléti függvény

(előadás, gyakorlat, laboratórium):

heti 2 óra előadás

3. Elővizsga: nincs

feladatok megoldásainak beadása a vizsgaidőszak első hetében is lehetséges.

havonta egy alkalom

1. Moon, J.W., Topics on Tournaments, Holt, Rinehart and Winston, 1968
2. Mala, J., On l -majority voting paradoxes, Mathematical Social Sciences, 37 (1999) 39-44.
3. Demange, G., Single-peaked preferences on a tree, Mathematical Social Sciences, 3

4. (1982) 389-396.

5. Fishburn, P. C., Acyclic sets of linear orders, Social Choice and welfare, 14 (1997) 113-124.
6. Reid, K.B., Tournaments: scores, kings, generalizations and special topics, Congressus Numerantium 115 (1996) 171-211.
7. Laslier, J-F., Tournament Solutions and Majority Voting, Springer-Verlag, Berlin-Heidelberg, 1997.
8. Shepsle, K., Weingast, B., Uncovered sets and sophisticated voting outcomes, with implications for agenda institutions, American Journal of Political Science, 28 (1) 49-75.
9. Reid, K.B., Majority tournaments: sincere and sophisticated voting decisions under amendment procedure, Mathematical Social Sciences, 21 (1991) 1-19.
10. May, K., A set of independent necessary and sufficient conditions for simple majority decision, Econometrica, 20 (1952) 680-684.
11. Campbell, D. E., Kelly, J.S., Impossibility theorems in the Arrovian framework, in Handbook of Social Choice and Welfare, Volume 1, Elsevier, 2002.
12. Gibbard, A.F., Hylland A., Weymark J.A., Arrows theorem with a fixed feasible alternative, Social Choice and Welfare, 4 (1987) 105-115.
13. Shapley, L.S., Simple games: an outline of the descriptive theory, Behavioral Science, 7 (1962) 59-66.
14. Taylor, A.D., Zwicker, W.S., Quasi-weightings, trading, and Desirability relations in simple games, Games and Economic Behavior, 16 (1996) 331-346.
15. Maskin, E., Sjöström, T., Implementation theory, in Handbook of Social Choice and Welfare, Volume 1, Elsevier, 2002
16. Nitzan S., Paroush, J., Optimal decision rules in uncertain dichotomous choice situations,, International Economic Review, 23 (2) (1982) 289-297.
17. Hoeffding, W., On the distribution of the number of successes in independent trials, Ann. Math. Statist., 27 (1956) 713-721.
18. Young, H.P., An axiomatization of Borda’s rule, Journal of Economic Theory, 9 (1974) 43-52.

(a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):