This dissertation builds a model of information exchange, where the information is skills. A two-sided matching market for skills is employed that includes two distinct sides, skilled and unskilled agents, and the matches that connect these agents. The unskilled agents wish to purchase skills from the skilled agents, who each possess one valuable and unique skill. Skilled agents may match with many unskilled agents, while each unskilled agent may match with only one skilled agent. Direct interaction is necessary between the agents to teach and learn the skill. Thus, there must be mutual consent for a match to occur and the skill to be exchanged. In this market for skills, a discrete, simultaneous move game is employed where all agents announce their strategies at once, every skilled agent announcing a price and every unskilled agent announcing the skill she wishes to purchase. First, both Nash equilibria and a correlated equilibrium are determined for an example of this skills market game. Next, comparative statics are employed on this discrete, simultaneous move game through computer simulations. Finally, a continuous, simultaneous move game is studied where all agents announce their strategies at once, every skilled agent announcing a price and every unskilled agent announcing a skill and price pair. For this game, an algorithm is developed that if used by all agents to determine their strategies leads to a strong Nash equilibrium for the game. / Economics

O principal objetivo deste trabalho é mostrar que uma convenção social está fortemente relacionada com o conceito de equilíbrio correlacionado. Através da interação de longo prazo e do aprendizado, os agentes podem chegar a um acordo, mesmo com suposições pouco restritivas e que possibilitem uma interpretação mais natural e realista do conceito de equilíbrio em Teoria dos Jogos. Inicialmente a suposição de conhecimento comum é apresentado de maneira formal e informal. O conceito de equilíbrio correlacionado é apresentado com exemplos. Finalmente, a relação entre o equilíbrio correlacionado e a convenção social é analisada. / The main purpose of this dissertation is to show that a convention can be related to a correlated equilibrium. Through the long run interaction and learning, the players can reach an agreement, even if we relax the traditional assumptions of Game Theory, and we can find a more natural and plausible interpretation of equilibrium. Initially the common knowledge assumption is presented in a formal and informal way. The correlated equilibrium is presented with examples. Finally, the relation between correlated equilibrium and convention is analyzed.

O principal objetivo deste trabalho é mostrar que uma convenção social está fortemente relacionada com o conceito de equilíbrio correlacionado. Através da interação de longo prazo e do aprendizado, os agentes podem chegar a um acordo, mesmo com suposições pouco restritivas e que possibilitem uma interpretação mais natural e realista do conceito de equilíbrio em Teoria dos Jogos. Inicialmente a suposição de conhecimento comum é apresentado de maneira formal e informal. O conceito de equilíbrio correlacionado é apresentado com exemplos. Finalmente, a relação entre o equilíbrio correlacionado e a convenção social é analisada. / The main purpose of this dissertation is to show that a convention can be related to a correlated equilibrium. Through the long run interaction and learning, the players can reach an agreement, even if we relax the traditional assumptions of Game Theory, and we can find a more natural and plausible interpretation of equilibrium. Initially the common knowledge assumption is presented in a formal and informal way. The correlated equilibrium is presented with examples. Finally, the relation between correlated equilibrium and convention is analyzed.

O principal objetivo deste trabalho é mostrar que uma convenção social está fortemente relacionada com o conceito de equilíbrio correlacionado. Através da interação de longo prazo e do aprendizado, os agentes podem chegar a um acordo, mesmo com suposições pouco restritivas e que possibilitem uma interpretação mais natural e realista do conceito de equilíbrio em Teoria dos Jogos. Inicialmente a suposição de conhecimento comum é apresentado de maneira formal e informal. O conceito de equilíbrio correlacionado é apresentado com exemplos. Finalmente, a relação entre o equilíbrio correlacionado e a convenção social é analisada. / The main purpose of this dissertation is to show that a convention can be related to a correlated equilibrium. Through the long run interaction and learning, the players can reach an agreement, even if we relax the traditional assumptions of Game Theory, and we can find a more natural and plausible interpretation of equilibrium. Initially the common knowledge assumption is presented in a formal and informal way. The correlated equilibrium is presented with examples. Finally, the relation between correlated equilibrium and convention is analyzed.

Στην παρούσα μεταπτυχιακή διπλωματική εργασία χρησιμοποιούμε έννοιες και εργαλεία της Θεωρίας Παιγνίων με σκοπό να μελετήσουμε την απόδοση μηχανισμών κατανομής διαιρέσιμων πόρων εστιάζοντας κυρίως στον μηχανισμό αναλογικής κατανομής. Σύμφωνα με αυτόν τον μηχανισμό, ένα σύνολο χρηστών ανταγωνίζονται για ένα διαιρέσιμο πόρο -- όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού -- υποβάλλοντας προσφορές. Ο μηχανισμός κατανέμει σε κάθε χρήστη ένα μέρος του πόρου το οποίο είναι ανάλογο της προσφοράς του και συλλέγει ένα ποσό ίσο με την προσφορά αυτή ως πληρωμή. Οι χρήστες στοχεύουν στη μεγιστοποίηση της ωφέλειας τους και συμπεριφέρονται στρατηγικά αλλάζοντας τις προσφορές τους με σκοπό να το πετύχουν. Έτσι, ο μηχανισμός ορίζει ένα παιχνίδι αναλογικής κατανομής. Παρουσιάζουμε γνωστά αποτελέσματα από τη σχετική βιβλιογραφία καθώς και νέα βελτιωμένα φράγματα για το κόστος της αναρχίας ως προς το κοινωνικό όφελος για συσχετιζόμενες ισορροπίες στο μοντέλο πλήρους πληροφόρησης και για ισορροπίες κατά Bayes-Nash στο μοντέλο ελλιπούς πληροφόρησης. Πιο συγκεκριμένα, παρουσιάζουμε ένα κάτω φράγμα 1/2 για το κόστος της αναρχίας ως προς τις προαναφερθείσες έννοιες ισορροπίας, βελτιώνοντας σημαντικά το προηγούμενο καλύτερο κάτω φράγμα 26.8% που πρόσφατα απέδειξαν οι Syrgkanis και Tardos (STOC 2013). Επίσης, μελετάμε για πρώτη φορά τη περίπτωση όπου οι χρήστες διαθέτουν περιορισμένους προϋπολογισμούς και παρουσιάζουμε ένα κάτω φράγμα περίπου 36% και ένα άνω φράγμα 50% για το κόστος της αναρχίας χρησιμοποιώντας ως αντικειμενική συνάρτηση το αποτελεσματικό όφελος το οποίο λαμβάνει υπόψη προϋπολογισμούς. / In this thesis, we use notions and techniques from Game Theory in order to analyze the performance of divisible resource allocation mechanisms focusing mainly on the proportional allocation mechanism. According to this mechanism, a set of users are competing for a divisible resource -- such as bandwidth of a communication link -- by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to the user's bid and collects an amount equal to the bid as payment. Users aim to maximize their individual utility and act strategically in order to achieve their goal. Hence, the mechanism defines a proportional allocation game. We cover previously known results from the related literature and present new bounds on the price of anarchy with respect to the social welfare over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In particular, we prove a lower bound of $1/2$ for the price of anarchy over both equilibrium concepts, significantly improving the previously best known lower bound, presented by Syrgkanis and Tardos (STOC 2013). Furthermore, we study for the first time the scenario where users have budget constraints and present lower bounds on the price of anarchy using the effective welfare (which takes budgets into account) as an objective function.

Game theory has become very powerful tool for modelling decision-making situations of rational players. However, practical applications are strongly limited by the size of particular game, which is connected to the computational power of computers nowadays. Aim of this master's thesis is to design and implement a library, which would be able to find correlated equilibria in as complex non-cooperative games as possible.

The multi-target tracking problem essentially involves the recursive joint estimation of the state of unknown and time-varying number of targets present in a tracking scene, given a series of observations. This problem becomes more challenging because the sequence of observations is noisy and can become corrupted due to miss-detections and false alarms/clutter. Additionally, the detected observations are indistinguishable from clutter. Furthermore, whether the target(s) of interest are point or extended (in terms of spatial extent) poses even more technical challenges. An approach known as random finite sets provides an elegant and rigorous framework for the handling of the multi-target tracking problem. With a random finite sets formulation, both the multi-target states and multi-target observations are modelled as finite set valued random variables, that is, random variables which are random in both the number of elements and the values of the elements themselves. Furthermore, compared to other approaches, the random finite sets approach possesses a desirable characteristic of being free of explicit data association prior to tracking. In addition, a framework is available for dealing with random finite sets and is known as finite sets statistics. In this thesis, advanced signal processing techniques are employed to provide enhancements to and develop new random finite sets based multi-target tracking algorithms for the tracking of both point and extended targets with the aim to improve tracking performance in cluttered environments. To this end, firstly, a new and efficient Kalman-gain aided sequential Monte Carlo probability hypothesis density (KG-SMC-PHD) filter and a cardinalised particle probability hypothesis density (KG-SMC-CPHD) filter are proposed. These filters employ the Kalman- gain approach during weight update to correct predicted particle states by minimising the mean square error between the estimated measurement and the actual measurement received at a given time in order to arrive at a more accurate posterior. This technique identifies and selects those particles belonging to a particular target from a given PHD for state correction during weight computation. The proposed SMC-CPHD filter provides a better estimate of the number of targets. Besides the improved tracking accuracy, fewer particles are required in the proposed approach. Simulation results confirm the improved tracking performance when evaluated with different measures. Secondly, the KG-SMC-(C)PHD filters are particle filter (PF) based and as with PFs, they require a process known as resampling to avoid the problem of degeneracy. This thesis proposes a new resampling scheme to address a problem with the systematic resampling method which causes a high tendency of resampling very low weight particles especially when a large number of resampled particles are required; which in turn affect state estimation. Thirdly, the KG-SMC-(C)PHD filters proposed in this thesis perform filtering and not tracking , that is, they provide only point estimates of target states but do not provide connected estimates of target trajectories from one time step to the next. A new post processing step using game theory as a solution to this filtering - tracking problem is proposed. This approach was named the GTDA method. This method was employed in the KG-SMC-(C)PHD filter as a post processing technique and was evaluated using both simulated and real data obtained using the NI-USRP software defined radio platform in a passive bi-static radar system. Lastly, a new technique for the joint tracking and labelling of multiple extended targets is proposed. To achieve multiple extended target tracking using this technique, models for the target measurement rate, kinematic component and target extension are defined and jointly propagated in time under the generalised labelled multi-Bernoulli (GLMB) filter framework. The GLMB filter is a random finite sets-based filter. In particular, a Poisson mixture variational Bayesian (PMVB) model is developed to simultaneously estimate the measurement rate of multiple extended targets and extended target extension was modelled using B-splines. The proposed method was evaluated with various performance metrics in order to demonstrate its effectiveness in tracking multiple extended targets.