Koalisyon Oluşturma Oyunları: İçsel Kararlılık
Coalition Formation Games: Inner Stability
Yazar: SEÇKİN ÖZBİLEN
Danışman: DOÇ. DR. ALİ ERCENGİZ
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Mühendisliği Ana Bilim Dalı / Matematik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2018
Konu: Matematik = Mathematics

Özet:
Bu tezde İşbirlikçi (kooperatif) Oyun Teorisi'nin bir alt kolu olan Hedonik Koalisyon
Oluşturma Oyunları çalışılacaktır. Bir hedonik koalisyon oluşturma oyununda sonlu
sayıda birey yer almaktadır. Her bireyin sadece kendisinin içinde yer aldığı altkümeler
(koalisyonlar) üzerine yansıyan, anti-simetrik, karşılaştırılabilir ve geçişken tercih
bağıntısı vardır. Tüm bireylerin tercih bağıntıları düşünüldüğünde bir hedonik
koalisyon oluşturma oyununun çözümü birey kümesinin partisyonlara (koalisyon
yapısı) ayrılmasıdır.
Çözümlerin analizi ve sınıflandırılması kararlılık kavramları göz önünde bulundurularak
yapılmaktadır. Bir koalisyon yapısının kararlı olması bireysel veya grup halinde
herhangi bir tür harekete imkan sağlamaması ile alakalıdır. Literatürde üzerinde
çalışma yapılan birçok kararlılık kavramı mevcuttur. Kararlılık kavramları arasında
bugüne kadar en çok çalışılanları Çekirdek Kararlılık ve Nash Kararlılık kavramlarıdır.
Genel olarak yapılan analizler bu kararlı koalisyon yapılarının hangi tanım kümeleri
üzerinde var ve tek olduğu üzerinedir. En geniş tanım kümesi, tüm hedonik koalisyon
oluşturma oyunları, düşünüldüğünde çekirdek kararlı veya Nash kararlı koalisyon
yapıları her zaman var olamamaktadır. Bu kararlılık kavramlarını ayrı ayrı sağlayan
koalisyon yapılarının en geniş tanım kümesinde olamamasının en temel sebebi bireysel
ya da grup halinde yer değiştirme (bloke etme) kavramlarının çok kolay olması,
dolayısıyla bloke edilemeyen koalisyon yapılarının neredeyse hiç bir şekilde var
olmamasıdır. Diğer bir deyişle, bu kararlılık kavramlarının var olamamasının sebebi
var olmak için talep ettiklerinin çok çok fazla olmasıdır. Bu kavramlar en geniş
tanım kümesinin sadece bazı özel altkümelerinde var olabilmektedirler. Literatürde
de genel olarak bu özel altkümelerin varlığı araştırılmakta, bu özel altkümelerde
analiz ve karakterizasyon yapılabilmektedir. Ancak, çok özel altkümelerde kararlılık
analizi çalışıldığında tüm bireylerin tüm olası tercihleri göz ardı edilmekte, bireyler
sadece özel tercih kalıpları içine sokulmuş olmaktadır. Böyle durumlarda ortaya çıkan
partisyon (koalisyon yapısı) da doğal değildir.
Bu tezde yukarıda bahsedilen aksaklıkların giderilmesine yönelik olarak içsel kararlılık
kavramı çalışılacaktır. İçsel kararlı koalisyon yapıları tüm hedonik oyunlar kümesinde
her zaman vardır. İçsel kararlılık bu yönüyle çekirdek kararlılık ve Nash kararlılık
kavramlarına göre temsiliyet yeteneği daha yüksektir. Bireylerin tercihlerinin hiçbir
şekilde kısıtlanmasına gerek olmadığı için koalisyon yapılarının analizini içsel
kararlılık kavramı ile yapmak hem daha fazla seçenek hem de daha fazla serbestiyet
sağlamaktadır.
Birinci ünitede hedonik koalisyon oluşturma oyunlarının genel modeli ve kararlılık
kavramları tanıtılacaktır. Daha sonra teorik literatür anlatılacak, kısaca hesaplama
karmaşıklığı literatüründen de bahsedilecektir. İkinci ünitede içsel kararlılık kavramı
tanıtılacaktır. İçsel kararlılık kavramının popüler kararlılık kavramları ile ilişkisi
açıklanacaktır. Daha sonra içsel algoritma tanıtılacaktır. Herhangi bir hedonik
koalisyon oluşturma oyununda içsel algoritmanın ürettiği tüm koalisyon yapıları içsel
kararlıdır. Son ünitede sonuçlar özetlenecek, ileriye yönelik araştırma sorularından
bahsedilecektir. Ekler kısmında tüm hedonik koalisyon oluşturma oyunlarının bazı
özel altkümeleri tanıtılacak, daha sonra da hedonik koalisyon oluşturma oyunlarının
gündelik hayatta karşımıza çıkan örnekleri uygulama olarak aktarıcaktır.

Abstract:
In this theses, we study a special topic from Cooperative Game Theory which
is Hedonic Coalition Formation Games. In a hedonic coalition formation game,
there exists finite number of individuals. Every individual only cares about which
individuals are in her coalition, but does not care how other individuals are grouped.
Every individual has reflexive, anti symmetric, complete, and transitive preferences
over the coalitions of which she is a member. The duple, finite set of individuals and
preferences of individuals, is called as hedonic coalition formation game, or simply
hedonic game. The solution of a hedonic game is partitioning of individuals into
disjoint coalitions. The solution is called as coalition structure.
When analyzing, comparing, and classifying coalition structures, stability concepts
are used. A coalition structure is called stable if and only if no individual or no group
of individuals engage in coalition change. There exist several stability concepts in
the literature. Most of the study in the literature is about finding the domains (set of
hedonic games) in which stable coalition structures exist or unique. Nash stability and
core stability are the most predominantly studied stability concepts. However, they
do not exist in the full domain, that is the set of all hedonic games. The main reason
of the non-existence is, they require a lot from a coalition structure to become stable.
In the full domain, they require that a coalition structure should not be blocked by
an individual or a group of individuals. When we consider the complement of the
domain in which coalition structures are either blocked by an individual or a group of
individuals, we find the sub-domain which guarantees the existence of stable coalition
structures. However, the complement sub-domain is very tiny. Studying with tiny
sub-domains are not satisfactory because we ignore the generality of preferences of
individuals. Thus, incoming coalition structures in sub-domains are not representative
and natural.
In this thesis, we study a new stability concept called inner stability. This stability
concept is proposed in order to cure the deficiencies of the core stability and the Nash
stability. A coalition structure is called inner stable if and only if there exists no
coalition in the given coalition structure and no proper subset of that coalition such
that individuals of the proper subset strictly prefer being in that proper subset to being
in the coalition.
Inner stable coalition structures exist for all hedonic games. Thus, we do not need
to restrict preferences of individuals. As a result, stability analyzes become more
representative than Nash stability or core stability.
In the first chapter, we introduce the model of hedonic game and stability concepts.
Then we present the theoretical literature. In addition, we briefly analyze the
computational complexity literature. In the second chapter, we introduce the inner
stability. We explain the relation of inner stability with other stability concepts. Then,
we study the inner algorithm. We give the proof of our main result: In the domain
of all hedonic coalition formation games, every coalition structure which is brought
out by inner algorithm is always inner stable. In addition, we briefly talk about the
computational complexity of the inner algorithm. In the last chapter, we conclude and
present some open research questions for future. Lastly, in the appendix, we touch
on the domain restrictions that we present in the first chapter. Additionally, we study
some real life applications of hedonic games.