Search

We conduct a series of Cournot duopoly market experiments with a high number of repetitions and fixed matching. Our treatments include markets with (a) complete cost symmetry and complete information, (b) slight cost asymmetry and complete information, and (c) varying cost asymmetries and incomplete information. For the case of complete cost symmetry and complete information, our data confirm the well-known result that duopoly players achieve, on average, partial collusion. However, as soon as any level of cost asymmetry or incomplete information is introduced, observed average individual quantities are remarkably close to the static Bayes-Nash equilibrium predictions.

We conduct a series of Cournot duopoly market experiments with a high number of repetitions and fixed matching. Our treatments include markets with (a) complete cost symmetry and complete information, (b) slight cost asymmetry and complete information, and (c) varying cost asymmetries and incomplete information. For the case of complete cost symmetry and complete information, our data confirm the well-known result that duopoly players achieve, on average, partial collusion. However, as soon as any level of cost asymmetry or incomplete information is introduced, observed average individual quantities are remarkably close to the static Bayes-Nash equilibrium predictions.

We conduct a series of Cournot duopoly market experiments with a high number of repetitions and fixed matching. Our treatments include markets with (a) complete cost symmetry and complete information, (b) slight cost asymmetry and complete information, and (c) varying cost asymmetries and incomplete information. For the case of complete cost symmetry and complete information, our data confirm the well-known result that duopoly players achieve, on average, partial collusion. However, as soon as any level of cost asymmetry or incomplete information is introduced, observed average individual quantities are remarkably close to the static Bayes-Nash equilibrium predictions.

We conduct a series of Cournot duopoly market experiments with a high number of repetitions and fixed matching. Our treatments include markets with (a) complete cost symmetry and complete information, (b) slight cost asymmetry and complete information, and (c) varying cost asymmetries and incomplete information. For the case of complete cost symmetry and complete information, our data confirm the well-known result that duopoly players achieve, on average, partial collusion. However, as soon as any level of cost asymmetry or incomplete information is introduced, observed average individual quantities are remarkably close to the static Bayes-Nash equilibrium predictions.

In this paper, we study N-player Colonel Blotto games with incomplete information about battlefield valuations. Such games arise in job markets, research and development, electoral competition, security analysis, and conflict resolution. For M Ï N + 1 battlefields, we identify a Bayes-Nash equilibrium in which the resource allocation to a given battlefield is strictly monotone in the valuation of that battlefield. We also explore extensions such as heterogeneous budgets, the case M È N, full-support type distributions, and network games. Revised version, February 2021

Ovaj diplomski rad je obradio temu dizajna mehanizma koja je temeljena na teoriji igara, podijeljenu obzirom na broj igrača. Za početak, obrađujemo mehanizme između jednog prodavača i jednog kupca. Prvo se bavimo davanjem cijene nerazdvojivom dobru gdje je prodavač dizajner mehanizma. Intuitivnim pristupom procjenjujemo da je prodavaču najbolje da na temelju procjene kupčevog tipa, koja je dana funkcijom distribucije, postavi cijenu te maksimizira očekivani profit. Zanima nas postoji li bolji mehanizam. Uvodimo pojam direktnog mehanizma te ograničenja poticajne kompatibilnosti i individualne racionalnosti koje su nužne za lakšu analizu problema. Olakotna okolnost je što se ispostavilo (za sva poglavlja) da za svaki indirektni mehanizam gdje kupac ne mora prijavljivati istinit tip, postoji odgovarajući direktni mehanizam (princip otkrivenja). Nadalje, karakteriziramo svojstva takvih mehanizama koja su potrebna u potrazi za optimizirajućim mehanizmom. Na kraju se ispostavilo da je početna intuitivna strategija bila najbolji izbor pošto je prodavačeva objektivna funkcija linearna jer nema rizika. Nakon toga prelazimo na nelinearno davanje cijena, tj. davanje cijene razdvojivom dobru, primjerice šećeru. Problem je malo kompleksniji te rezultat nije toliko trivijalan jer korisnost kupca više nije linearna zbog dodatno definirane funkcije ν koja nam omogućuje manipuliranje. Na temelju pretpostavke da je distribucija slučajne varijable prijavljenog tipa regularna, dobijemo efektivan način za zadavanje mehanizma koji maksimizira profit. Na kraju poglavlja obrađujemo primjer u kojem vidimo da nam je uvedena funkcija ν dala popust na količinu. Drugo poglavlje obrađuje Bayesove mehanizme gdje u igri tražimo Bayes-Nash ravnotežu između igrača. Poglavlje počinje promatranjem aukcije jednog nerazdvojivog dobra gdje kupac daje na aukciju dobro za \(N \geq 2\) agenata. Definiramo analogone već spomenute funkcije distribucije, direktnog mehanizma, principa otkrivenja, samo sada u slučaju problema više varijabli. Stoga, primorani smo definirati dodatne funkcije vjerojatnosti prodaje, očekivanog transfera i korisnosti koje ovise samo o prijavljenom tipu jednog agenta. Većina posljedica karakterizacije svojstava je analogna. Sličnom analizom kao u prethodnom poglavlju, dobijemo da dobro prodajemo kupcu s najvećom pozitivnom vrijednošću funkcije \(\psi\), inače ne prodajemo. Na kraju obrađujemo primjer koji pokazuje kako se intuitivno raspoređuje vjerojatnost prodaje dobra kupcima. Zadnja tema kojom se bavimo su javna dobra. Imamo zajednicu od \(N \geq 2\) ljudi koji moraju odlučiti hoće li proizvoditi neko nerazdvojivo dobro. Odluka se donosi na temelju troška proizvodnje i iznosa transfera koji plaćaju agenti. Uz već dobro znane pojmove, definiramo i svojstvo ex ante i ex post budžetske ravnoteže, koje u suštini govore da ukupni transfer mora biti veći od troška proizvodnje. Prije svega zaključujemo da su to zapravo dva ekvivalentna pojma, stoga možemo birati koje ćemo koristiti. Prvo maksimiziramo blagostanje zajednice. Intuicija nas navodi na tzv. prvi najbolji mehanizam koji kaže da će se dobro proizvoditi ako je ukupna suma tipova veća od cijene proizvodnje. Nažalost se ispostavi da se poticajno kompatibilan individualno racionalan mehanizam može konstruirati samo u trivijalnim slučajevima. Koristeći Kuch-Tucherov teorem dobijemo drugi najbolji mehanizam za netrivijalne slučajeve. Sličnom analizom dobijemo i optimizirajući mehanizam za maksimizaciju profita. This thesis processed mechanism design topic which is based on game theory, divided due to the number of players. At the beginning we analyze mechanisms between a seller and a buyer. First we deal with giving prices to single indivisible good where the seller is a mechanism designer. With intuitive approach we estimate that the best for the seller to do is based on assessments of the buyer’s type, which is given by distribution function, to set the price and maximizes expected profit. We are interested in whether there is better mechanism. We introduce the concept of direct mechanism and incentive compatibility and individual rationality constraints that are necessary for easier analysis of the problem. Mitigating circumstance is that it turned out (for all chapters) that for any indirect mechanism where the buyer does not have to report true type, there is appropriate direct mechanism (revelation principle). Furthermore, we bring characterizations of mechanisms that were necessary in pursuit of optimizing mechanism. At the end it turned out that the beginning strategy was the best choice because the seller’s objective function is linear because there is no risk. After that, we have moved to nonlinear pricing i.e., pricing divisible good, for example sugar. The outcome of this complex problem isn’t so trivial because buyer’s utility is no longer linear because of further defined function ν which enables us to manipulate. Based on assumptions that distribution of random variable for reported type is regular, we have got effective way for setting mechanism that maximizes profit. At the end of the chapter we have processed an example that shows that the introduced function ν gave as a discount on the amount. The second chapter process Bayesian mechanism where in the game we look for Bayes-Nash equilibrium between players. Chapter starts with observing an auction of one indivisible good where the buyer gives his good on an auction for \(N > 2\) agents. Then we define analogues of already mentioned distribution function, direct mechanism, revelation principle, only now in a case with multiple variables. Thus, we have to define additional probability function of the sale, expected transfer and utility that depends only on reported type of one agent. Most of the consequences of the characterization of properties is analog. With a similar analysis as in the previous chapter, we get that we will sell the good to the buyer with the largest positive value of the function “psi”, otherwise we won’t sell. At the end we have an example that shows how to distribute the likelihood of the sale of goods to customers. The last topic that we are dealing with are public goods. We have a community \(N \geq 2\) of people who have to decide whether they will produce some indivisible good. Decision is made on the basis of cost of production and the amount of transfers that agents pay. We also define the property ex ante and ex post of budget balance, which essentially says that overall transfers must be greater than the cost of production. We conclude that these are two equivalent concepts, therefore we can choose whichever we want to use. First we maximize welfare of the community. Intuition leads us to first best mechanism which tells us that the good will be produce if the total sum of the types is greater than the cost of production. Unfortunately, it turns out that incentive compatible, individually rational mechanism can be built only in trivial cases. Using Kuch-Tucherov theorem we get second best mechanism for non-trivial cases. With a similar analysis we get optimizing mechanism for profit maximization. By observing the example we can see that profit maximization requires bigger types of agents from that one that maximizes the welfare.

Στην παρούσα μεταπτυχιακή διπλωματική εργασία χρησιμοποιούμε έννοιες και εργαλεία της Θεωρίας Παιγνίων με σκοπό να μελετήσουμε την απόδοση μηχανισμών κατανομής διαιρέσιμων πόρων εστιάζοντας κυρίως στον μηχανισμό αναλογικής κατανομής. Σύμφωνα με αυτόν τον μηχανισμό, ένα σύνολο χρηστών ανταγωνίζονται για ένα διαιρέσιμο πόρο -- όπως το εύρος ζώνης ενός τηλεπικοινωνιακού καναλιού -- υποβάλλοντας προσφορές. Ο μηχανισμός κατανέμει σε κάθε χρήστη ένα μέρος του πόρου το οποίο είναι ανάλογο της προσφοράς του και συλλέγει ένα ποσό ίσο με την προσφορά αυτή ως πληρωμή. Οι χρήστες στοχεύουν στη μεγιστοποίηση της ωφέλειας τους και συμπεριφέρονται στρατηγικά αλλάζοντας τις προσφορές τους με σκοπό να το πετύχουν. Έτσι, ο μηχανισμός ορίζει ένα παιχνίδι αναλογικής κατανομής. Παρουσιάζουμε γνωστά αποτελέσματα από τη σχετική βιβλιογραφία καθώς και νέα βελτιωμένα φράγματα για το κόστος της αναρχίας ως προς το κοινωνικό όφελος για συσχετιζόμενες ισορροπίες στο μοντέλο πλήρους πληροφόρησης και για ισορροπίες κατά 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.

In this paper, we develop a hierarchical Bayesian game framework for automated dynamic offset selection. Users compete to maximize their throughput by picking the best locally serving radio access network (RAN) with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. In particular, we investigate the properties of a Stackelberg game, in which the base station is a player on its own. We derive analytically the utilities related to the channel quality perceived by users to obtain the equilibria. We study the Price of Anarchy (PoA) of such system, where the PoA is the ratio of the social welfare attained when a network planner chooses policies to maximize social welfare versus the social welfare attained in Nash/Stackeleberg equilibrium when users choose their policies strategically. We show by means of a Stackelberg formulation, how the operator, by sending appropriate information about the state of the channel, can configure a dynamic offset that optimizes its global utility while users maximize their individual utilities. The proposed hierarchical decision approach for wireless networks can reach a good trade-off between the global network performance at the equilibrium and the requested amount of signaling. Typically, it is shown that when the network goal is orthogonal to user's goal, this can lead the users to a misleading association problem., 12 pages, 3 figures, technical report. arXiv admin note: text overlap with arXiv:1002.3931, arXiv:0903.2966 by other authors

International audience; This paper addresses a Bayesian game theoretic framework for determining the association rules that decide to which cell a given mobile user should associate in LTE two-tier Heterogeneous Networks (HetNets). Users are assumed to compete to maximize their throughput by picking the best locally serving cell with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. In particular, we investigate the properties of a hierarchical game, in which the macro-cell BS is a player on its own. We derive analytically the utilities related to the channel quality perceived by users to obtain the equilibria. We show by means of a Stackelberg formulation, how the operator, by dynamically choosing the offset about the state of the channel, can optimize its global utility while end-users maximize their individual utilities. The proposed hierarchical decision approach for wireless networks can reach a good trade-off between the global network performance at the equilibrium and the requested amount of signaling. Typically, it is shown that when the network goal is orthogonal to user's goal, this can lead the users to a misleading association problem. Numerical results validate the expectation from the theoretical analysis and illustrate the advantages of the proposed approach.

International audience; —It has been known that the throughput of the 802.11 WLAN is much smaller than the nominal bit rate offered when attempting to connect to an access point. A user may discover the quality of service offered by an access point only after taking the decision of which of the access points to connect to. In fact, the actual throughput of a user is a function of not only his channel state but also of that of the other connected users. This could likely lead to congestion and overload conditions in the Access Point (AP) in question (which offers the best signal strength) and all users would lose. The information available to users attempting to connect to an AP is thus misleading. In this paper, we develop a Nash-Bayesian game framework where users compete to maximize their throughput by picking the best locally serving radio access network (RAN) with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. We derive analytically the utilities perceived by users to obtain the equilibria. In particular, it is shown that equilibria strongly depend on the channel quality indicator.

We examine the implementation of efficient decisions about accepting a special order with asymmetric information by means of a dual transfer pricing mechanism based on Ronen and McKinney (1970). The model is designed in a simple fashion, two vertically related divisions within a firm (manufacturing and distribution) process a special order of a single product. Each division manager has private information about the divisional parameters (production costs and profit margin) and both report simultaneously to the other manager. The reports mutually affect the managers' payoffs by determining the transfer payments which are payed to both divisions. Subsequently, based on the reports, the principal decides if the special order will be accepted. The outcome of this model is that cheating is a Bayes-Nash equilibrium and is Pareto-efficient, but truth-telling is a dominant strategy incentive-compatible equilibrium and strongly risk-dominates cheating. When adding an additional stage to the game, the accounting stage, it becomes clear that the incentives are inverse to those in Ronen and McKinney (1970) as the incentives to cheat disappear. The reason is that the managers only receive the 'award' from cheating if they indicate the true information in the accounting stage. If they choose to report untruthfully then they suffer a loss as they need to pay the difference between the true and the incorrectly accounted value out of their own pocket. It follows that this model design is more robust against cheating than the introduction of a penalty, as studied by Ronen (1992). Therefore, dual transfer prices are able to implement the first-best solution. These results also clearly disprove the main results of Wagenhofer (1994).

We extend the well-known fictitious play (FP) algorithm to compute pure-strategy Bayesian-Nash equilibria in private-value games of incomplete information with finite actions and continuous types (G-FACTs). We prove that, if the frequency distribution of actions (fictitious play beliefs) converges, then there exists a pure-strategy equilibrium strategy that is consistent with it. We furthermore develop an algorithm to convert the converged distribution of actions into an equilibrium strategy for a wide class of games where utility functions are linear in type. This algorithm can also be used to compute pure ϵ-Nash equilibria when distributions are not fully converged. We then apply our algorithm to find equilibria in an important and previously unsolved game: simultaneous sealed-bid, second-price auctions where various types of items (e.g., substitutes or complements) are sold. Finally, we provide an analytical characterisation of equilibria in games with linear utilities. Specifically, we show how equilibria can be found by solving a system of polynomial equations. For a special case of simultaneous auctions, we also solve the equations confirming the results obtained numerically.