Explorations to refine Aizerman Malishevski's representation for path independent choice rules

Bu çalışma yoldan bağımsız seçim kuralları için Aizerman Malishevski'nin temsilinin araştırıldığı üç ana kısımdan oluşmaktadır. Yoldan bağımsız her seçim kuralının, belirli bir öncelik sıralaması kümesi sayesinde, verilen her seçim kümesi için elimizdeki öncelik sıramalarındaki en iyi elemanların kümesi olarak göstermemizi sağlayacak bir en-iyileri-biriktiren (EB) temsilinin olduğu bilinmektedir (Aizerman and Malishevski, 1981). İlk kısımda bütün yoldan bağımsız seçim kurallarını inceliyoruz. Bu seçim kurallarının mümkün bütün EB temsillerini bulmak için maksimal ve asal küme kavramlarını tanımlıyoruz. Daha sonra asal kümelerin en geniş anti-zincirinin büyüklüğünün mümkün EB temsilleri arasında en kısasının büyüklüğünü verdiğini gösteriyoruz. İkinci kısımda q-(kapasite) dolduran ve yoldan bağımsız seçim kurallarına odaklanıyoruz. En küçük asal kümeleri asal atomlar olarak tanımlayıp, bu kuralların en kısa EB temsilinin tam olarak asal atomların sayısı kadar sıralama içerdiğini gösteriyoruz. Bu sonucu kullanarak, q-(sıralamaya) duyarlı seçim kurallarının en kısa EB gösteriminin bütün q-(kapasite) dolduran ve yoldan bağımsız seçim kuralları arasında mümkün olabilecek en uzun gösterimi olduğunu gösteriyoruz. Üçüncü kısımda q-(sıralamaya) duyarlı seçim kurallarını genellemek amacıyla (sıralamaya) duyarlılığı bir seçim beliti olarak tanımlıyoruz. Yoldan bağımsız ve (sıralamaya) duyarlı seçim kuralları için ağırlıklı (sıralamaya) duyarlı seçim kuralları olarak isimlendirdiğimiz yeni bir temsil tanımlayıp bu yeni temsilin ağırlıklar üzerindeki ek bir kısıt altında bütün (sıralamaya) duyarlı ve yoldan bağımsız seçim kuralları kümesine denk olduğunu gösteriyoruz. Dördüncü kısımda ise atama problemine odaklandık. Bu problemde Eşit Hızla Yedirme algoritmasının her zaman olasılıksal-verimli ve olasılıksal-kıskançlıksız bir dağıtım verdiği bilinmektedir. Biz de biricik olasılıksal-verimli ve olasılıksal-kıskançlıksız dağılımın olduğu tercih profillerini belirlemek için yeterli ve neredeyse gerekli bir koşul getirdik.