Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
5 results
Search Results
Item Learning and Robustness With Applications To Mechanism Design(2022) Curry, Michael Jeremiah; Dickerson, John P; Goldstein, Thomas; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The design of economic mechanisms, especially auctions, is an increasingly important part of the modern economy. A particularly important property for a mechanism is strategyproofness -- the mechanism must be robust to strategic manipulations so that the participants in the mechanism have no incentive to lie. Yet in the important case when the mechanism designer's goal is to maximize their own revenue, the design of optimal strategyproof mechanisms has proved immensely difficult, with very little progress after decades of research. Recently, to escape this impasse, a number of works have parameterized auction mechanisms as deep neural networks, and used gradient descent to successfully learn approximately optimal and approximately strategyproof mechanisms. We present several improvements on these techniques. When an auction mechanism is represented as a neural network mapping bids from outcomes, strategyproofness can be thought of as a type of adversarial robustness. Making this connection explicit, we design a modified architecture for learning auctions which is amenable to integer-programming-based certification techniques from the adversarial robustness literature. Existing baselines are empirically strategyproof, but with no way to be certain how strong that guarantee really is. By contrast, we are able to provide perfectly tight bounds on the degree to which strategyproofness is violated at any given point. Existing neural networks for auctions learn to maximize revenue subject to strategyproofness. Yet in many auctions, fairness is also an important concern -- in particular, fairness with respect to the items in the auction, which may represent, for instance, ad impressions for different protected demographic groups. With our new architecture, ProportionNet, we impose fairness constraints in addition to the strategyproofness constraints, and find approximately fair, approximately optimal mechanisms which outperform baselines. With PreferenceNet, we extend this approach to notions of fairness that are learned from possibly vague human preferences. Existing network architectures can represent additive and unit-demand auctions, but are unable to imposing more complex exactly-k constraints on the allocations made to the bidders. By using the Sinkhorn algorithm to add differentiable matching constraints, we produce a network which can represent valid allocations in such settings. Finally, we present a new auction architecture which is a differentiable version of affine maximizer auctions, modified to offer lotteries in order to potentially increase revenue. This architecture is always perfectly strategyproof (avoiding the Lagrangian-based constrained optimization of RegretNet) -- to achieve this goal, however, we need to accept that we cannot in general represent the optimal auction.Item Conic Economics(2016) Raissi, Maziar; Madan, Dilip; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Modern general equilibria under uncertainty are modeled based on the recognition that all risks cannot be eliminated, perfect hedging is not possible, and some risk exposures must be tolerated. Therefore, we need to define the set of acceptable risks as a primitive of the financial economy. This set will be a cone, hence the word conic. Such a conic perspective challenges classical economics by introducing finance into the economic models and enables us to rewrite major chapters of classical micro- and macro-economics textbooks.Item Revenue Efficient Mechanisms for Online Advertising(2015) Khani, Mohammad Reza; Hajiaghayi, Mohammad; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Online advertising is an essential part of Internet and the main source of revenue for lots of web-centric companies such as search engines, news websites, Internet social networks, and other types of publishers. Online advertising happens in different settings and includes many challenges and constraints. A key component in each setting is the mechanism which selects and prices the set of winning ads. In this thesis, we consider the mechanism related issues arises in online advertising and propose candidate solutions with a special focus on the revenue aspect. Generalized Second Price (GSP) auction (the current mechanism of choice in online advertising) has appealing properties when ads are simple (text based and identical in size). But GSP does not generalize to richer ad settings, whereas truthful mechanisms, such as VCG do. Hence there are incentives for search platforms to migrate to truthful mechanisms, but a straight switch from GSP to VCG either requires all bidders instantly bid truthfully or incurs significant revenue loss. We propose a transitional mechanism which encourages advertisers to update their bids to their valuations, while mitigating revenue loss\footnote{It is the candidate mechanism to make the transition from GSP to VCG in Microsoft's Bing.}. The mechanism is equivalent to GSP when nobody has updated her bid, is equivalent to VCG when everybody has updated, and it has the same allocation and payments of the original GSP if bids were in the minimum symmetric Nash equilibrium. In settings where both GSP ads and truthful ads exist, it is easier to propose a payment function than an allocation function. We give a general framework for these settings to characterize payment functions which guarantee incentive compatibility of truthful ads, by requiring that the payment functions satisfy two properties. Next, we discuss about revenue monotonicity (revenue should go up as the number of bidders increases) of truthful mechanisms in online advertising. This natural property comes at the expense of social welfare - one can show that it is not possible to get truthfulness , revenue monotonicity, and optimal social welfare simultaneously. In light of this, we introduce the notion of Price of Revenue Monotonicity (\porm) to capture the loss in social welfare of a revenue monotone mechanism. We design truthful and revenue monotone mechanisms for important online advertising auctions with small \porm{} and prove a matching lower bound. Finally, we study how to measure revenue of mechanisms in the prior free settings. One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high values for the goods and a {\em competitive} outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to `block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of {\em core} in cooperative game theory where designing {\em core-selecting auctions} is well studied \cite{AM02,AM06,DM08,DC12}. While these auctions are known for having good revenue properties, they lack incentive-compatibility property desired for online advertising. Towards this, we define a notion of {\em core-competitive} auctions. We say that an incentive-compatible auction is $\alpha$-core-competitive if its revenue is at least $1/\alpha$ fraction of the minimum revenue of a core-outcome. We study designing core-competitive mechanisms for a famous online advertising scenario.Item Regulation of Systemic Risk Through Contributory Endogenous Agent-Based Modeling(2013) Bristor, Aurora; Fu, Michael; Barnes, Sean; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The Financial Stability Oversight Council (FSOC) was created to identify and respond to emerging threats to the stability of the United States financial system. The research arm of the FSOC, the Office of Financial Research (OFR), has begun to explore agent-based models (ABMs) for measuring the emergent threat of systemic risk. We propose an ABM-based regulatory structure that incentivizes the honest participation and data contribution of regulated firms while providing clarity into the actions of the firms as endogenous to the market and driving emergent behavior. We build this scheme onto an existing ABM of a single-asset market to examine whether the structure of the scheme could provide its own benefits to market stabilization. We find that without regulatory intervention, markets acting within this proposed structure experience fewer bankruptcies and lower leverage buildup while returning larger profits for the same amount of risk.Item MECHANISM DESIGN WITH GENERAL UTILITIES(2012) Alaei, Saeed; Khuller, Samir; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis studies mechanism design from an optimization perspective. Our main contribution is to characterize fundamental structural properties of optimization problems arising in mechanism design and to exploit them to design general frameworks and techniques for efficiently solving the underlying problems. Not only do our characterizations allow for efficient computation, they also reveal qualitative characteristics of optimal mechanisms which are important even from a non-computational standpoint. Furthermore, most of our techniques are widely applicable to optimization problems outside of mechanism design such as online algorithms or stochastic optimization. Our frameworks can be summarized as follows. When the input to an optimization problem (e.g., a mechanism design problem) comes from independent sources (e.g., independent agents), the complexity of the problem can be exponentially reduced by (i) decomposing the problem into smaller subproblems, each one involving one input source, (ii) simultaneously optimizing the subproblems subject to certain relaxation of coupling constraints, and (iii) combining the solutions of the subproblems in a certain way to obtain an (approximately) optimal solution for the original problem. We use our proposed framework to construct optimal or approximately optimal mechanisms for several settings previously considered in the literature and to improve upon the best previously known results. We also present applications of our techniques to non-mechanism design problems such as online stochastic generalized assignment problem which itself captures online and stochastic versions of various other problems such as resource allocation and job scheduling.