The fundamental motivation for the work in this thesis is the study of decentralized dynamical decision systems and their optimization properties. The design of competitive markets to substitute for traditional centralized regulation has been considered in many domains and a key feature of the decentralized decision mechanisms of competitive markets is that, subject to certain hypotheses, they maximize social welfare. Progressive auctions constitute a highly developed form of such market mechanisms and hence in this thesis we construct and analyze them as paradigm examples of decentralized dynamical decision making systems.In the work of Lazar and Semret (1999), a so-called Progressive Second Price auction mechanism (PSP) was proposed for both dynamic market-pricing and allocation of variable-size resources. In this thesis, three quantized versions of the PSP auction are developed. First, a so-called Quantized - PSP (Q-PSP) auction algorithm is analyzed where the agents have similar private demand functions and submit bids synchronously. It is shown that the nonlinear dynamics induced by this algorithm are such that the prices bid by the various agents and the quantities allocated to these agents converge in at most five iterations or oscillate indefinitely, with all prices converging to one price for all agents or to a limit cycle on just two prices for all agents. This behaviour is not only independent of the number of agents involved but is also independent of the number of quantization levels. Second, the Aggressive-Defensive Quantized - PSP (ADQ-PSP) auction algorithm is presented which improves upon the performance of the Q-PSP auction. For the ADQ-PSP auction applied to agent populations with randomly distributed demand functions, it is shown that the states of the corresponding dynamical systems rapidly converge with high probability to a quantized (Nash) equilibrium with a common price for all agents. Third, the Unique-limit Quantized - PSP (UQ-PSP) auction algorithm is developed as a modification of the ADQ-PSP; for this algorithm, (i) the limit price of all system trajectories is independent of the initial data, and (ii) modulo the quantization level, the limiting resource allocation is efficient (i.e., the corresponding social welfare function, or summed individual valuation functions, is optimal up to a quantized level).These quantized auction algorithms are, first, extended to supply auctions, that is to say, competitive markets where only sellers are assumed to exist, and then, second, extended to double-sided auctions where auctions are defined between both sellers and buyers separately and which interact in a well defined way. Finally, network based auctions are considered; this is motivated by the fact that agents in communication networks or social networks may not be able to access the bid information of all other agents or resource information over such networks and hence must make decisions based solely upon local information. In particular, a two-level network-based auction is developed and is formulated as a consensus UQ-PSP auction where suppliers in the upper network recursively follow consensus dynamics to allocate quantities which are the subject of UQ-PSP auctions at each network node. This configuration solves the corresponding discrete-time weighted-average consensus problem, converges to a unique network wide price and achieves social efficiency for the whole network. / La motivation première du travail accompli dans cette thèse est l'étude des systèmes dynamiques de décisions décentralisées et leurs propriétés d'optimisation. La conception des marchés compétitifs dans le but de remplacer la réglementation centralisée traditionnelle a été envisagée dans plusieurs domaines. L'élément clé des mécanismes de décisions décentralisés est que sous certaines hypothèses, ils maximisent le bien-être social. Les enchères progressives constituent une forme extrêmement développée de ces types de mécanismes de marchés. Cette thèse les construit et les analyse donc comme étant des exemples paradigmatiques de systèmes dynamiques de prise de décision décentralisés.Le travail de Lazar et Semret (1999), un mécanisme d'enchères au second prix progressif (PSP), ainsi nommé, a été envisagé pour la tarification en fonction des marchés ainsi que pour l'allocation des ressources de format variable. Dans cette thèse, trois versions quantifiées des enchères au second prix progressif ont été développées.Premièrement, un algorithme d'enchère PSP-quantifié ainsi nommé (Q-PSP) est analysé là où les agents ont des fonctions de demande privée similaires et font des offres simultanément. Il est démontré que la dynamique non linéaire causée par cet algorithme est tel que les offres faites par divers agents et les quantités allouées à ces agents convergent en cinq itérations au plus ou oscillent indéfiniment, tandis que tous les prix convergent vers un seul prix pour tous les agents ou vers un cycle limite de deux prix pour tous les agents. Ce comportement n'est pas seulement indépendant du nombre d'agents en jeu, mais est aussi indépendant du nombre de niveaux de quantification. Deuxièmement, l'algorithme de l'enchère PSP quantifié agressif-défensif (ADQ-PSP) est présenté, ce qui améliore la performance de l'enchère Q-PSP. Pour l'enchère ADQ-PSP mis en pratique dans les populations d'agents dont la fonction de demande est distribuée de façon aléatoire, il est démontré que les états des systèmes dynamiques correspondants convergent rapidement avec une forte probabilité d'atteindre un équilibre (de Nash) quantifié, avec un prix commun pour tous les agents. Troisièmement, l'algorithme d'enchère quantifié à limite unique-PSP (UQ-PSP) est développé en tant que modification de l'ADQ-PSP. Pour cet algorithme, (i) le prix limite de toutes les trajectoires de systèmes est indépendant des données initiales, et (ii) modulo le niveau de quantification, l'allocation restrictive est efficace, c'est-à-dire que la fonction correspondante du bien-être social, ou l'addition des fonctions d'évaluation individuelles, est optimisée à un certain niveau de quantification près.L'utilisation de ces algorithmes d'enchère quantifiées est, en premier lieu, étendue aux enchères inversées, c'est-à-dire, des marchés compétitifs où l'on présume qu'il existe seulement des vendeurs, et ensuite, aux double enchères, où les enchères sont définies séparément entre les vendeurs et les acheteurs, qui communiquent d'une façon bien définie. Finalement, les enchères sur réseau sont considérées. Cette analyse est motivée par le fait que les agents dans les réseaux de communication ou les réseaux sociaux ne peuvent pas accéder aux renseignements concernant les offres de tous les autres agents ou aux informations à propos des ressources à travers de tels réseaux et doivent donc fonder leurs décisions seulement sur des renseignements locaux. En particulier, une enchère basée sur un réseau à deux niveaux est mise au point et formulée comme consensus d'enchère UQ-PSP dans lequel les fournisseurs faisant partie du réseau supérieur suivent récursivement la dynamique de consensus afin d'allouer des quantités qui sont sujettes à des enchères UQ-PSP à chaque nœud du réseau. Cette configuration résout le problème du consensus de la moyenne pondérée à temps discret, converge vers un prix unique pour tout le réseau et atteint l'utilité sociale pour le réseau en entier.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.97012 |
| Date | January 2011 |
| Creators | Jia, Peng |
| Contributors | Peter Edwin Caines (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (Department of Electrical and Computer Engineering) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.002 seconds