[pt] Este trabalho propõe um modelo de implementação de um leilão bidimensional para concessões de serviços públicos. O desenho do leilão é feito pelo governo através de uma regra de pontuação quase-linear que valora o preço cobrado e o tempo para iniciar a prestação de serviços. Este modelo aplica-se ao conjunto de serviços públicos que geram grandes benefícios quando começam a ser prestado em uma data limite reduzida. Os potenciais compradores possuem informação privada sobre seus custos de produção e redução do tempo. A regra de pontuação reduz a dimensionalidade dos lances tornando-os unidimensionais para os participantes, o maior lance resulta em uma obrigação contratual ao vencedor. O modelo auxilia na elaboração do design do leilão de forma a maximizar as preferências do governo dado o comportamento estratégico dos compradores. / [en] In this thesis we propose a model for a two-dimensional auction of public service concession agreements. The government design of the auction involves an almost linear scoring rule that evaluates the price charged and the time to start providing the services. The model applies to the public services that improve social welfare by reducing the delivery time of services. Suppliers have private information about their costs and time reduction offer. The proposed scoring rule of each supplier reduces the dimensionality of the bids submitted to a single dimension. The winner is committed to his bid and obliges to provide the required services. The model assists in preparing the design of the auction in order to maximize the preferences of the government given to the strategic behavior of buyers.

Coordination is a desirable feature in many multi-agent systems, such as robotic, social and economic networks, allowing the execution of tasks that would be impossible by individual agents. This thesis addresses two problems in stochastic coordination where each agent make decisions strategically, taking into account the decisions of its neighbors over a regular network. In the first problem, we study the coordination in a team of strategic agents choosing to undertake one of the multiple tasks. We adopt a stochastic framework where the agents decide between two distinct tasks whose difficulty is randomly distributed and partially observed. We show that a Nash equilibrium with a simple and intuitive linear structure exists for textit{diffuse} prior distributions on the task difficulties. Additionally, we show that the best response of any agent to an affine strategy profile can be nonlinear when the prior distribution is not diffuse. Then, we state an algorithm that allows us to efficiently compute a data-driven Nash equilibrium within the class of affine policies. In the second problem, we assume that the payoff structure of the coordination game corresponds to a single task allocation scenario whose difficulty is perfectly observed. Since there are multiple Nash equilibria in this game, the agents must use a distributed stochastic algorithm know as textit{log linear learning} to play it multiple times. First, we show that this networked coordination game is a potential game. Moreover, we establish that for regular networks, the convergence to a Nash equilibrium depends on the ratio between the task-difficulty parameter and the connectivity degree according to a threshold rule. We investigate via simulations the interplay between rationality and the degree of connectivity of the network. Our results show counter-intuitive behaviors such as the existence of regimes in which agents in a network with larger connectivity require less rational agents to converge to the Nash equilibrium with high probability. Simultaneously, we examined the characteristics of both regular graphical coordination games and non-regular graphical games using this particular bi-matrix game model. / Master of Science / This thesis focuses on addressing two problems in stochastic coordination among strategic agents in multi-agent systems, such as robotic, social, and economic networks. The first problem studies the coordination among agents when they need to choose between multiple tasks whose difficulties are randomly distributed and partially observed. The thesis shows the existence of a Nash equilibrium with a linear structure for certain prior distributions, and presents an algorithm to efficiently compute a data-driven Nash equilibrium within a specific class of policies. The second problem assumes a single task allocation scenario, whose difficulty is perfectly observed, and investigates the use of a distributed stochastic algorithm known as log-linear learning to converge to a Nash equilibrium. The thesis shows that the convergence to a Nash equilibrium depends on the task-difficulty parameter and the connectivity degree of the network, and explores the influence of rationality of the agents and the connectivity of the network on the learning process. Overall, the thesis provides insights into the challenges and opportunities in achieving coordination among strategic agents in multi-agent systems.

Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη. Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας GSP (γενικευμένος μηχανισμός δεύτερης τιμής) σε αυτό το πλαίσιο. Για την ακρίβεια, ορίζουμε παραλλαγές του μηχανισμού δημοπρασίας GSP που δίνουν καλές εγγυήσεις εσόδων. Στη συνέχεια εξετάζουμε το πρόβλημα του σχεδιασμού της βέλτιστης δημοπρασίας ενός αντικειμένου. Αποδεικνύουμε ένα υπολογίσιμο φράγμα δυσκολίας στην προσέγγιση για την περίπτωση με τρεις παίχτες. Επίσης, αποδεικνύουμε ότι υπάρχει αξιοσημείωτη διαφορά ανάμεσα στα έσοδα που προκύπτουν από ντετερμινιστικούς φιλαλήθεις μηχανισμούς και πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις κατά μέσο όρο. / In this dissertation we consider auction markets and examine their properties and how these are affected by the way the participants act. An auction may refer to any mechanism or set of rules governing a resource allocation process. Designing such a mechanism is not an easy task and this is partly due to their vulnerability to strategic manipulation by the participants. Our goal is to examine the theoretical properties of auction mechanisms in order to predict, explain, or even adjust their behavior in practice in terms of some desired features. We focus on sponsored search auctions, which constitute the leading procedure in Internet advertising. We adopt a game-theoretic approach and provide Price of Anarchy bounds in order to measure the efficiency loss due to the strategic behavior of the players. Moreover, we prove revenue guarantees to bound the suboptimality of GSP (generalized second price mechanism) in that respect. Ιn particular, we define variants of the GSP auction mechanism that yield good revenue guarantees. We also consider the problem of designing an optimal auction in the single-item setting. We prove a strong APX-hardness result that applies to the 3-player case. We furthermore give a separation result between the revenue of deterministic and randomized optimal auctions.