Incentive mechanisms in user provided networks - Taşçi, Sinan Emre (My University, 2023)
Kullanıcı kaynaklı ağlar (KKA) son zamanlarda üzerinde çokça araştırma yapılan bir alan olmuştur. Bu alandaki araştırmalardan azımsanamayacak bir oranı Mobil Ağ Operatörlerinin (MAO) kullanıcılarının bant genişliği, pil enerjisi ve kota gibi kaynaklarını diğer kullanıcıların kullanımına sunmasını teşvik etme konusuna odaklanmıştır. Önerilen teşvik mekanizmaları genel olarak oyun teorisi tabanlı olup özellikle potansiyel oyun teorisinden faydalanmaktadırlar ve toplam indirilen veri miktarının iyileştirilmesini amaç edinmektedirler. Bu tezde daha evvelki çalışmalardan farklı olarak var olan bant genişliğinin kullanımının eniyilenmesi ve katılımcılarının veri hızlarının artırılması üzerine odaklanılmıştır. İlk olarak hiç İnternet erişimi olmayan ya da daha yüksek veri hızına ihtiyaç duyan bir ağ operatörü abonesinin etrafında var olan başka bir katılımcının kaynaklarını kullanarak İnternet erişimini sağlaması veya veri hızını artırması problemine odaklanılmıştır. Bu problem asli itibariyle KKA’lardaki en temel problemdir. Bu çalışmada bir enerji modellemesi önerilmiş ve bu modelleme ile Rubinstein pazarlık şeması temel alınarak bir pazarlık modeli geliştirilmiştir. Geliştirilen mekanizmanın etkinliği yapılan nümerik çalışmalarla veri hızı ve bit başına maliyet metrikleri çerçevesinde gösterilmiştir. Böylelikle KKA’ların en temel problemine bir çözüm sunulmuştur. Tezin ikinci aşamasında çoklu düğüm barındıran KKA’lar için bir teşvik mekanizması geliştirilmesi üzerinde çalışılmıştır. Bu aşamada aboneler arasında var olan bant genişliğinin eşitlikçi (egalitarian) paylaşılmasını öngören bir dağıtım fonksiyonu geliştirilmiştir. Bu dağıtım fonksiyonunu fayda fonksiyonu olarak temel alan bir oyun tanımlanmıştır. Bu oyun her bir abonenin kendi elde ettiği veri hızını maksimize etmeye çalıştığı denetimsiz bir ağ yapısını başka bir deyişle anarşinin olduğu en kötü durumu göstermektedir. Bu oyuna her bir kullanıcının sadece kendi lokal faydasını iyileştirmek istemesinden dolayı lokal oyun adı verilmiştir. Diğer taraftan, hem ağ operatörleri hem de aboneler açısından var olan bütün bant genişliğinden faydalanmayı ve bu bant genişliğini aboneler arasında adil dağıtmayı öngören global bir potansiyel fonksiyonun olduğu bir başka oyun önerilmiştir. Bu iki oyun birbirleri ile toplam kullanılabilen bant genişliği ve bant genişliğinin adil dağılımı metrikleri açısından kıyaslanmıştır. Tezimizin son aşamada bir önceki aşamada tanımlanan lokal oyun olarak isimlendirdiğimiz oyunun özel halini de kapsayan yeni bir oyun sınıfı modellenmiştir. Bu yeni tanımlanan oyun sınıfını dağıtım oyunları olarak adlandırdık. Dağıtım oyunlarında eşitlikçi dağıtım dışında talep oranlı bir dağıtım fonksiyonu tanımladık. Kullanılabilen bant genişliği açısından dağıtım oyunlarının hem eşitlikçi hem de talep oranlı dağıtım fonksiyonları kullanıldığında birer potensiyel oyun olduğunu ispatladık. Daha sonra dağıtım oyunlarında istikrarın bedeli (İB) ve anarşinin bedeli (AB) incelemelerini gerçekleştirdik. Nihai aşamada dağıtım oyunlarının ve onun genel sürümünün simülasyonlarını gerçekleştirdik. Simülasyonlar neticesinde dağıtım oyunları ve onun genel sürümünün kullanılabilen toplam bant genişliği ve bu bant genişliğinin adil paylaşımı noktasında etkinliğini gösterdik. Ayrıca dağıtım oyunlarının diğer oyunlara olan benzerliklerini ve farklılıklarını inceleyerek bu özgün oyun sınıfını oyun teorisine kazandırmış olduk. Dağıtım oyunlarının genel sürümünün bütün simülasyonlarda Nash dengesine ulaştığını görülmekle beraber genel sürümün her zaman Nash dengesine ulaştığının ispatı henüz yapılamamıştır. Bu tez çalışması bütünü itibariyle bakıldığında en temel KKA probleminden, en karmaşık olanına kadar oyun teorisi tabanlı bütüncül çözümler üretmiştir, bunu yaparken de oyun teorisine yeni oyunlar ve araştırmaya açık problemler sunmuştur.

User Provided Networks (UPN) is a recent and hot area of research. A substantial amount of research in this area is focused on incentivizing subscribers of Mobile Network Operators (MNO) to make resources such as bandwidth, battery energy and quota available to other subscribers. In general, proposed incentive mechanisms are based on game theory, in particular they heavily make use of potential game theory and aim to improve the total amount of data downloaded. In this thesis, unlike previous studies, we focus on optimizing the use of existing bandwidth and increasing the data rates of the participants. First of all we focus on providing Internet access or higher data rates to the mobile subscribers who have no Internet access or need higher data rates using the resources of neighboring participants. This problem is essentially the most fundamental problem in UPN. In this study, an energy modeling is proposed and a bargaining model is developed based on Rubinstein bargaining scheme. The effectiveness of the mechanism developed is demonstrated according to the metrics -data rate and price per bit- through numerical studies. Thus, a solution to the most basic problem of UPN is presented. In the second stage of the thesis, development of an incentive mechanism for UPN with multiple nodes is studied. At this stage, a distribution function is developed that aims the egalitarian sharing of the existing bandwidth among subscribers and then a game is introduced such that the utility function is based on that egalitarian distribution function. This game shows an uncontrolled network structure in which each subscriber tries to maximize her own data rate, in other words, this is the worst case which can be named the case of anarchy. We named this game the local game because each player is rational only to improve their local utility. Another game has also been proposed in which there is a global potential function that aims taking advantage of all available bandwidth for both network operators and subscribers and distributing that bandwidth fairly among subscribers. These two games are compared with each other in terms of total bandwidth exposed and fairness metrics. In the last stage of our thesis a new class of games is introduced which also include special version of the local game from the previous stage. We name this newly introduced class of games as distribution games. In distribution games, we propose a demand proportional distribution function as well as the egalitarian distribution function. In terms of bandwidth exposed, we prove that distribution games are potential games when both egalitarian and demand proportional distribution functions employed. We analyze the distribution games for the price of stability (PoS) and the price of anarchy (PoA). In the final stage, we simulate the distribution games and its generalized version. As a result of the simulations, we demonstrate the effectiveness of distribution games and its generalized version in terms of total bandwidth exposed and fair sharing of the exposed bandwidth. In addition, by proposing distribution games and examining the similarities and differences of distribution games with other games we contribute to game theory. Although the generalized version of distribution games seems to reach Nash equilibrium in all simulations, there is no proof that the generalized version always reaches Nash equilibrium. Thus, this is a new research problem which requires further investigation. This thesis provides holistic solutions based on game theory from the most basic UPN problem to the most complicated one, and while doing this, it contributes new class of games and open research problems to game theory.
Kullanıcı tabanlı ağlar için teşvik mekanizmaları
Keywords: Bargaining; Bilgisayar ağları; Bilgisayar mühendisliği; Computer engineering; Computer networks; Dağıtık Refah Oyunları; Distributed Welfare Games; Energy Modeling; Enerji Modelleme Congestion Games; Fayda Modelleme; Incentive Design; Internet (Copmputer networks); Internet users; İnternet (Bilgisayar ağları); İnternet kullanıcıları; Kullanıcı Tabanlı Ağlar; Pazarlık; Sıkışıklık Oyunları; Teşvik Tasarımı; User Provided Networks; Utility Modeling