Electrical & Computer Engineering Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2765
Browse
6 results
Search Results
Item Learning in Large Multi-Agent Systems(2024) Kara, Semih; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we study a framework of large-scale multi-agent strategic interactions. The agents are nondescript and use a learning rule to repeatedly revise their strategies based on their payoffs. Within this setting, our results are structured around three main themes: (i) Guaranteed learning of Nash equilibria, (ii) The inverse problem, i.e. estimating the payoff mechanism from the agents' strategy choices, and (iii) Applications to the placement of electric vehicle charging stations. In the traditional setup, the agents' inter-revision times follow identical and independent exponential distributions. We expand on this by allowing these intervals to depend on the agents' strategies or have Erlang distributions. These extensions enhance the framework's modeling capabilities, enabling it to address problems such as task allocation with varying service times or multiple stages. We also explore a third generalization, concerning the accessibility among strategies. Majority of the existing literature assume that the agents can transition between any two strategies, whereas we allow only certain alternatives to be accessible from certain others. This adjustment further improves the framework's modeling capabilities, such as by incorporating constraints on strategy switching related to spatial and informational factors. For all of these extensions, we use Lyapunov's method and passivity-based techniques to find conditions on the revision rates, learning rule, and payoff mechanism that ensure the agents learn to play a Nash equilibrium of the payoff mechanism. For our second class of problems, we adopt a multi-agent inverse reinforcement learning perspective. Here, we assume that the learning rule is known but, unlike in existing work, the payoff mechanism is unknown. We propose a method to estimate the unknown payoff mechanism from sample path observations of the populations' strategy profile. Our approach is two-fold: We estimate the agents' strategy transitioning probabilities, which we then use - along with the known learning rule - to obtain a payoff mechanism estimate. Our findings regarding the estimation of transitioning probabilities are general, while for the second step, we focus on linear payoff mechanisms and three well-known learning rules (Smith, replicator, and Brown-von Neumann-Nash). Additionally, under certain assumptions, we show that we can use the payoff mechanism estimate to predict the Nash equilibria of the unknown mechanism and forecast the strategy profile induced by other rules. Lastly, we contribute to a traffic simulation tool by integrating electric vehicles, their charging behaviors, and charging stations. This simulation tool is based on spatial-queueing principles and, although less detailed than some microscopic simulators, it runs much faster and accurately represents traffic rules. Using this tool, we identify optimal charging station locations (on real roadway networks) that minimize the overall traffic.Item Age of Information and Energy Efficiency in Communication Networks(2015) Dutra da Costa, Maice; Ephremides, Anthony; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation focuses on two important aspects of communication systems, namely energy efficiency and age of information. Both aspects have received much less attention than traditional performance metrics, such as throughput and delay. The need to improve the energy efficiency in communication networks is apparent, given the high demand for power consuming applications to be implemented in devices with limited energy supplies. Additionally, improvements in energy efficiency are encouraged by possible reductions in network operation costs, and by the increasing awareness of the environmental impact caused by the information and communication technologies. In this dissertation, energy efficiency is studied in the context of a cognitive wireless network, in which users have different priorities to access the network resources, possibly interfering and cooperating among themselves. A new parametrization is proposed to characterize performance trade-offs associated with energy efficiency for non-cooperative and cooperative network models. Additionally, a game theoretic model is proposed to study resource allocation in a cooperative cognitive network, accounting for energy efficiency in the utility functions. Age of information is a relatively new concept, which aims to characterize the timeliness of information. It is relevant to any system concerned with timeliness of information, and particularly relevant when information is used to make decisions, but the value of the information is degraded with time. This is the case in many applications of communications and control systems. In this dissertation, the age of information is first investigated for status update communication systems. The status updates are samples of a random process under observation, transmitted as packets, which also contain the time stamp to identify when the sample was generated. The age of information at the destination node is the time elapsed since the last received update was generated. The status update systems are modeled using queuing theory. We propose models for status update systems capable of managing the packets before transmission, aiming to avoid wasting network resources with the transmission of stale information. In addition to characterizing the average age, we propose a new metric, called peak age, which provides information about the maximum value of the age, achieved immediately before receiving an update. We also propose a new framework, based on the concept of age of information, to analyze the effect of outdated Channel State Information (CSI) on the performance of a communication link in which the source node acquires the CSI through periodic feedback from the destination node. The proposed framework is suitable to analyze the trade-off between performance and timeliness of the CSI, which is a fundamental step to design efficient adaptation functions and feedback protocols.Item Interaction between a Service Provider and Content Providers and Social Efficiency(2014) ElDelgawy, Ramy; La, Richard J.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)It is unclear how the introduction of "fast lanes" would affect the evolution of the Internet. While this is with no doubt an important issue, we do not aim to address this question. Instead, in this work we study the interaction between an internet service provider and one or more content providers when such fast lanes are allowed. Each entity is considered a player in a game, and it is assumed that these players are both rational and selfish, i.e., they aim to maximize their own gains. Clearly, their objectives are different, and their bargaining powers may vary. We examine how they may reach an agreement and how their interaction affects the resulting quality-of-service on the fast lanes. To get a better understanding of the kind of contract these entities may be willing to sign we look at two cases: (i) a monopoly market that has one internet service provider and one content provider and (ii) one where an extra content provider enters the market. Our findings show that, in the case of a monopoly market, an efficient contract can be reached in Stackelberg games, which maximizes the aggregate payoff of both the providers. Similarly, when another content provider enters the market, the entity with the strongest bargaining power chooses a contract that maximizes the aggregate payoff of all providers.Item On the Design and Analysis of Incentive Mechanisms in Network Science(2014) Gao, Yang; Liu, K. J. Ray; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)With the rapid development of communication, computing and signal processing technologies, the last decade has witnessed a proliferation of emerging networks and systems, examples of which can be found in a wide range of domains from online social networks like Facebook or Twitter to crowdsourcing sites like Amazon Mechanical Turk or Topcoder; to online question and answering (Q&A) sites like Quora or Stack Overflow; all the way to new paradigms of traditional systems like cooperative communication networks and smart grid. Different from tradition networks and systems where uses are mandated by fixed and predetermined rules, users in these emerging networks have the ability to make intelligent decisions and their interactions are self-enforcing. Therefore, to achieve better system-wide performance, it is important to design effective incentive mechanisms to stimulate desired user behaviors. This dissertation contributes to the study of incentive mechanisms by developing game-theoretic frameworks to formally analyze strategic user behaviors in a network and systematically design incentive mechanisms to achieve a wide range of system objectives. In this dissertation, we first consider cooperative communication networks and propose a reputation based incentive mechanism to enforce cooperation among self-interested users. We analyze the proposed mechanism using indirect reciprocity game and theoretically demonstrate the effectiveness of reputation in cooperation stimulation. Second, we propose a contract-based mechanism to incentivize a large group of self-interested electric vehicles that have various preferences to act coordinately to provide ancillary services to the power grid. We derive the optimal contract that maximizes the system designer's profits and propose an online learning algorithm to effectively learn the optimal contract. Third, we study the quality control problem for microtask crowdsourcing from the perspective of incentives. After analyzing two widely adopted incentive mechanisms and showing their limitations, we propose a cost-effective incentive mechanism that can be employed to obtain high quality solutions from self-interested workers and ensure the budget constraint of requesters at the same time. Finally, we consider social computing systems where the value is created by voluntary user contributions and understanding how user participate is of key importance. We develop a game-theoretic framework to formally analyze the sequential decision makings of strategic users under the presence of complex externality. It is shown that our analysis is consistent with observations made from real-word user behavior data and can be applied to guide the design of incentive mechanisms in practice.Item Multimedia Social Networks: Game Theoretic Modeling and Equilibrium Analysis(2011) Chen, Yan; Liu, K. J. Ray; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Multimedia content sharing and distribution over multimedia social networks is more popular now than ever before: we download music from Napster, share our images on Flickr, view user-created video on YouTube, and watch peer-to-peer television using Coolstreaming, PPLive and PPStream. Within these multimedia social networks, users share, exchange, and compete for scarce resources such as multimedia data and bandwidth, and thus influence each other's decision and performance. Therefore, to provide fundamental guidelines for the better system design, it is important to analyze the users' behaviors and interactions in a multimedia social network, i.e., how users interact with and respond to each other. Game theory is a mathematical tool that analyzes the strategic interactions among multiple decision makers. It is ideal and essential for studying, analyzing, and modeling the users' behaviors and interactions in social networking. In this thesis, game theory will be used to model users' behaviors in social networks and analyze the corresponding equilibria. Specifically, in this thesis, we first illustrate how to use game theory to analyze and model users' behaviors in multimedia social networks by discussing the following three different scenarios. In the first scenario, we consider a non-cooperative multimedia social network where users in the social network compete for the same resource. We use multiuser rate allocation social network as an example for this scenario. In the second scenario, we consider a cooperative multimedia social network where users in the social network cooperate with each other to obtain the content. We use cooperative peer-to-peer streaming social network as an example for this scenario. In the third scenario, we consider how to use the indirect reciprocity game to stimulate cooperation among users. We use the packet forwarding social network as an example. Moreover, the concept of ``multimedia social networks" can be applied into the field of signal and image processing. If each pixel/sample is treated as a user, then the whole image/signal can be regarded as a multimedia social network. From such a perspective, we introduce a new paradigm for signal and image processing, and develop generalized and unified frameworks for classical signal and image problems. In this thesis, we use image denoising and image interpolation as examples to illustrate how to use game theory to re-formulate the classical signal and image processing problems.Item Medium Access Control and Network Coding for Wireless Information Flows(2007-08-03) Sagduyu, Yalin Evren; Ephremides, Anthony; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation addresses the intertwined problems of medium access control (MAC) and network coding in ad hoc wireless networks. The emerging wireless network applications introduce new challenges that go beyond the classical understanding of wireline networks based on layered architecture and cooperation. Wireless networks involve strong interactions between MAC and network layers that need to be jointly specified in a cross-layer design framework with cooperative and non-cooperative users. For multi-hop wireless networks, we first rediscover the value of scheduled access at MAC layer through a detailed foray into the questions of throughput and energy consumption. We propose a distributed time-division mechanism to activate dynamic transmitter-receiver assignments and eliminate interference at non-intended receivers for throughput and energy-efficient resource allocation based on stable operation with arbitrary single-receiver MAC protocols. In addition to full cooperation, we consider competitive operation of selfish users with individual performance objectives of throughput, energy and delay. We follow a game-theoretic approach to evaluate the non-cooperative equilibrium strategies at MAC layer and discuss the coupling with physical layer through power and rate control. As a cross-layer extension to multi-hop operation, we analyze the non-cooperative operation of joint MAC and routing, and introduce cooperation stimulation mechanisms for packet forwarding. We also study the impact of malicious transmitters through a game formulation of denial of service attacks in random access and power-controlled MAC. As a new networking paradigm, network coding extends routing by allowing intermediate transmitters to code over the received packets. We introduce the adaptation of network coding to wireless environment in conjunction with MAC. We address new research problems that arise when network coding is cast in a cross-layer optimization framework with stable operation. We specify the maximum throughput and stability regions, and show the necessity of joint design of MAC and network coding for throughput and energy-efficient operation of cooperative or competitive users. Finally, we discuss the benefits of network coding for throughput stability in single-hop multicast communication over erasure channels. Deterministic and random coding schemes are introduced to optimize the stable throughput properties. The results extend our understanding of fundamental communication limits and trade-offs in wireless networks.