Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
15 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 Campaigning Via LPs: Solving Blotto and Beyond(2019) Seddighin, Saeed; Hajiaghayi, MohammadTaghi; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The competition between the Republican and the Democrat nominees in the U.S presidential election is known as Colonel Blotto in game theory. In the classical Colonel Blotto game -- introduced by Borel in 1921 -- two colonels simultaneously distribute their troops across multiple battlefields. The outcome of each battlefield is determined by a winner-take-all rule, independently of other battlefields. In the original formulation, the goal of each colonel is to win as many battlefields as possible. The Colonel Blotto game and its extensions have been used in a wide range of applications from political campaigns (exemplified by the U.S presidential election) to marketing campaigns, from (innovative) technology competitions, to sports competitions. For almost a century, there have been persistent efforts for finding the optimal strategies of the Colonel Blotto game, however it was left unanswered whether the optimal strategies are polynomially tractable. In this thesis, we present several algorithms for solving Blotto games in polynomial time and will discuss their applications in practice.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 Agent Modeling in Stochastic Repeated Games(2014) Cheng, Kan Leung; Nau, Dana S.; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)There are many situations in which two or more agents (e.g., human or computer decision makers) interact with each other repeatedly in settings that can be modeled as repeated games. In such situations, there is evidence that agents sometimes deviate greatly from what conventional game theory would predict. There are several reasons why this might happen, one of which is the focus of this dissertation: sometimes an agent's preferences may involve not only its own payoff (as specified in the payoff matrix), but also the payoffs of the other agent(s). In such situations, it is important to be able to understand what an agent's preferences really are, and how those preferences may affect the agent's behavior. This dissertation studies how the notion of Social Value Orientation (SVO), a construct in social psychology to model and measure a person's social preference, can be used to improve our understanding of the behavior of computer agents. Most of the work involves the life game, a repeated game in which the stage game is chosen stochastically at each iteration. The work includes the following results: * Using a combination of the SVO theory and evolutionary game theory, we studied how an agent's SVO affects its behavior in Iterated Prisoner's Dilemma (IPD). Our analysis provides a way to predict outcomes of agents playing IPD given their SVO values. * In the life game, we developed a way to build a model of agent's SVO based on observations of its behavior. Experimental results demonstrate that the modeling technique works well. * We performed experiments showing that the measured social preferences of computer agents have significant correlation with that of their human designers. The experimental results also show that knowing the SVO of an agent's human designer can be used to improve the performance of other agents that interact with the given agent. * A limitation of the SVO model is that it only looks at agents' preferences in one-shot games. This is inadequate for repeated games, in which an agent's actions may depend on both its SVO and whatever predictions it makes of the other agent's behavior. We have developed an extension of the SVO construct called the behavioral signature, a model of how an agent's behavior over time will be affected by both its own SVO and the other agent's SVO. The experimental results show that the behavioral signature is an effective way to generalize SVO to situations where agents interact repeatedly.Item Generation and Analysis of Strategies in an Evolutionary Social Learning Game(2013) Carr, James Ryan; Nau, Dana; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)An important way to learn new actions and behaviors is by observing others, and several evolutionary games have been developed to investigate what learning strategies work best and how they might have evolved. In this dissertation I present an extensive set of mathematical and simulation results for Cultaptation, which is one of the best-known such games. I derive a formula for measuring a strategy's expected reproductive success, and provide algorithms to compute near-best-response strategies and near-Nash equilibria. Some of these algorithms are too complex to run quickly on larger versions of Cultaptation, so I also show how they can be approximated to be able to handle larger games, while still exhibiting better performance than the current best-known Cultaptation strategy for such games. Experimental studies provide strong evidence for the following hypotheses: 1. The best strategies for Cultaptation and similar games are likely to be conditional ones in which the choice of action at each round is conditioned on the agent's accumulated experience. Such strategies (or close approximations of them) can be computed by doing a lookahead search that predicts how each possible choice of action at the current round is likely to affect future performance. 2. Such strategies are likely to prefer social learning most of the time, but will have ways of quickly detecting structural shocks, so that they can switch quickly to individual learning in order to learn how to respond to such shocks. This conflicts with the conventional wisdom that successful social-learning strategies are characterized by a high frequency of individual learning; and agrees with recent experiments by others on human subjects that also challenge the conventional wisdom.Item Essays on Information Flows and Auction Outcomes in Business-to-Business Market: Theoretical and Empirical Evidence(2013) Pilehvar, Ali; Elmaghraby, Wedad; Gopal, Anandasivam; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, I have three separate essays in the context of Business-to Business (B2B) auctions; in each I introduce a complex problem regarding the impact of information flows on auction's performance which has not been addressed by prior auction literature. The first two essays (Chapter 1 and 2) are empirical studies in the context of online secondary market B2B auctions while the third essay (Chapter 3) is a theoretical investigation and will contribute to the B2B procurement auction literature. The findings from this dissertation have managerial implications of how/when auctioneers can improve the efficiency or success of their operations. B2B auctions are new types of ventures which have begun to shape how industries of all types trade goods. Online B2B auctions have also become particularly popular for industrial procurement and liquidation purposes. By using online B2B auctions companies can benefit by creating competition when auctioning off goods or contracts to business customers. B2B Procurement auctions− where the buyer runs an auction to procure goods and services from suppliers− have been documented as saving firms millions of dollars by lowering the cost of procurement. On the other hand, B2B auctions are also commonly used by sellers in `secondary market' to liquidate the left-over goods to business buyers in a timely fashion. In order to maximize revenues in either both industrial procurement or secondary market settings, auctioneers should understand how the auction participants behave and react to the available market information or auction design. Auctioneers can then use this knowledge to improve the performance of their B2B auctions by choosing the right auction design or strategies. In the first essay, I investigate how an online B2B secondary market auction environment can provide several sources of information that can be used by bidders to form their bids. One such information set that has been relatively understudied in the literature pertains to reference prices available to the bidder from other concurrent and comparable auctions. I will examine how reference prices from such auctions affect bidding behavior on the focal auction conditioning on bidders' types. I will use longitudinal data of auctions and bids for more than 4000 B2B auctions collected from a large liquidator firm in North America. In the second essay, I report on the results of a field experiment that I carried out on a secondary market auction site of another one of the nation's largest B2B wholesale liquidators. The design of this field experiment on iPad marketplace is directly aimed at understanding how (i) the starting price of the auction, and (ii) the number of auctions for a specific (model, quality), i.e., the supply of that product, interact to impact the auction final price. I also explore how a seller should manage the product differentiation so that she auctions off the right mix and supply of products at the reasonable starting prices. Finally, in the last essay, I study a norm used in many procurement auctions in which buyers grant the `Right of First Refusal' (ROFR) to a favored supplier. Under ROFR, the favored supplier sees the bids of all other participating suppliers and has the opportunity to match the (current) winning bid. I verify the conventional wisdom that ROFR increases the buyer's procurement cost in a single auction setting. With a looming second auction in the future (with the same participating suppliers), I show that the buyer lowers his procurement cost by granting the ROFR to a supplier. The analytical findings of this essay highlights the critical role of information flows and the timing of information-release in procurement auctions with ROFR.Item Essays on Auction Theory(2012) Burkett, Justin Ellis; Ausubel, Lawrence M; Economics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation studies two features of high-value auctions that are not explicitly captured by the standard models in the auction theory literature. The first is that bidders in auctions for valuable assets sometimes have binding budget constraints. Standard models of auctions assume that bidders can submit any bid up to their valuation (or willingness to pay). An existing literature has developed models where bidders may face binding budget constraints and from these models has concluded that the presence of budget constraints has important implications for the relative performance of different auction formats, and as a consequence argues that the presence of budget constraints should be an important factor used in choosing an auction format. Chapters 2 and 3 develop and study a model of budget constraints where the budget constraint is chosen explicitly in the model in response to a principal-agent problem between each bidder and a corresponding principal. In previous literature, the budget constraint is assumed to be given by some exogenous procedure, and hence is not affected by changes in the auction rules. The model presented here, however, allows the choice of budget constraint to depend on the auction rules, and the main result of Chapter 2 shows that allowing for this effect leads to outcomes that closely resemble the classic results from the auction literature without budget constraints. Chapter 3 investigates the theoretical predictions of Chapter 2 in an experiment involving undergraduate students at the University of Maryland. The experiment is designed to evaluate the decisions made by the subjects acting as the person responsible for deciding on a budget for the bidder. We perform treatments where the bidding behavior is simulated by computerized agents and ones where half the subjects in each session play the role of the bidder. Our results indicate that the subjects take the auction rules into account when deciding on their respective bidder's budget, and the direction of the response in the data agrees with the theoretical predictions. Chapter 4 studies a separate feature of high-value auctions that is not captured by the standard auction models. That is, the bidders in the auction may have valuations for the auctioned item that depend on the the identities of the other winning bidders. If the auction determines the structure of the market the bidders will compete in after the auction, the bidders' values for the items will be affected by who participates in that market. The typical notion of efficiency in the auction literature corresponds to maximization of producer surplus in this model, but the auctioneer may also be concerned with total surplus in this environment. The main results show that these two notions of efficiency do not agree in this model, and that a sequential auction favors maximization of producer surplus, while a sealed-bid auction can favor maximization of total surplus. The key distinction between the two is that the sequential auction is assumed to reveal the identity of early winners to the later winners, while the sealed-bid auction reveals no information to the participants until the auction concludes.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.