Browsing by Subject "Mechanism design"
Now showing 1 - 9 of 9
- Results Per Page
- Sort Options
Item Algorithm and mechanism design with nonlinear preferences(2018-08) Yang, Ger; Nikolova, Evdokia; Dimakis, Georgios-Alex; Shakkottai, Sanjay; Tran, Ngoc; de Veciana, GustavoIn real life, many combinatorial and economic problems have nonlinear objectives and constraints, where the nonlinearities typically arise from different risk preferences, non-rationality, etc. Solving these problems is often computationally hard but can be beneficial by providing more revenue or welfare. In this thesis, I am going to investigate three problems: route planning with a nonlinear objective, dynamic mechanism design with agents of bounded rationality, and economic mechanism design with risk-loving buyers.Item Algorithms and hardness results for resource allocation and facility location problems(2021-05-12) Sinha, Vaibhav Birendrakumar; Plaxton, C. GregMany real-life scenarios involve making decisions based on agent preferences, for example, electing leaders, developing public facilities, and allocating resources in market. In this thesis, we consider two such problems where we want to make decisions based on agent preferences. In our first problem, we study a variant of the classic housing markets model. Each agent is initially assigned a unique house, and the houses form a graph. Each agent has strict preferences over the houses. Two agents can swap houses if the swap is Pareto-improving and the houses are adjacent. We study three reachability questions in the context of various graph structures. In our second problem, we study a variant of the facility location game. In this setting, a central planner has to build a set of heterogeneous facilities. Every agent reports the set of facilities that they consider "obnoxious". The goal is to design strategyproof and group-strategyproof mechanisms that maximize either the total utility of agents or the minimum utility of agents.Item Approximation algorithms and mechanism design for power systems(2021-04-02) Khodabakhsh, Ali; Nikolova, Evdokia; de Veciana, Gustavo; Shakkottai, Sanjay; Zhu, Hao; Gupta, SwatiIn real life, many combinatorial optimization problems are solved by simple algorithms (e.g., greedy, local search, thresholding, etc.) without any provable guarantees on the performance of the returned solution compared to the optimal one. Even though theoretical computer scientists have established strong results for the performance of such algorithms in diverse settings, it is not always easy to match the real life application to one of those well-studied problems. That said, we also have power systems which is a rich source of combinatorial optimization problems. The combinatorial nature arises whether it is turning switches on or off, assigning generation to different sources, scheduling charging or discharging of electric vehicles, splitting loads between different phases, or installing equipment at certain locations of the grid. On top of the combinatorial nature, these applications usually entail another level of complexity due to the nonlinearity of their objective and/or constraints. In this Ph.D. dissertation, I will try to bridge theoretical computer science and power systems by utilizing tools from approximation algorithms and mechanism design to provide rigorous guarantees for three problems in power systems. Contributing to the intersection of these two fields is important to both push the state-of-the-art approximation algorithms by introducing new problems that cannot be solved with existing techniques, as well as provide methods for both scalable and rigorous solutions to problems arising in real-world power systems. In the first problem, the goal is to minimize the power loss in a distribution network via changing the on/off status of switches in the network. Bringing to bear recent advances in submodular optimization, we derive performance bounds for a simple local-search algorithm that has been used in practice for a long time. We then focus on special properties of the grid that let us develop tailored algorithms with improved performance guarantees. Finally, we use our insights from our theoretical analysis to propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. In the second problem, we propose a novel way to use electric vehicles as dynamic energy storage for supporting the power grid, by discharging them at designated times and locations of need. We show that the underlying scheduling problem is NP-hard and propose various approximation algorithms with different performance guarantees. Finally in the last problem, we study a mechanism design problem for a system operator who wants to optimally assign the demand to different energy generators. We study this as a dynamic procurement auction, in which the generators may go out of business if they are not frequently picked. Since this will increase the electricity price in the long term, the system operator has to design a mechanism that minimizes the overall cost via selecting different sources frequent enough to maintain the competition. We show how to obtain optimal thresholding mechanisms via a greedy approach.Item Essays on certification mechanism design in strategic communications(2010-08) Xu, Hong, doctor of information, risk, and operations management; Stinchcombe, Maxwell; Whinston, Andrew B.; Mote, John; Wiseman, Thomas; Gu, BinCertifiers have a crucial role in facilitating effective communication in the online and the traditional world. As a way of generating statistically meaningful information, certification has been adopted in financial statements evaluation and more recently in various online communities as well. This dissertation examines three related issues along this common theme: online reputation market, moderation in user-generated content, and strategic communications in the market for certifications, and consists of three essays. The first essay analyzes the impact of various dispute mechanisms on online identity trading. Online identities with a good reputation profile is a valuable and tradable asset. However, with free identity creation, there is room for low quality sellers to free-ride high quality sellers. When there is a lack of incentive for sellers to maintain a good reputation, identity trading becomes ineffective. This essay focuses on the role of an auditing system, such as eBay dispute center, and shows that even a small amount of objective information from the auditors can reverse the negative result and sustain reliable reputation and identity trading. The second essay investigates the impact of moderation on the quality of information in an user-generated content (UGC) environment. In most UGC communities, content contributors have incentive to publish biased or false information. For example, companies hire people to write positive reviews about themselves. This essay establishes a framework for the mechanism design of moderation, and provides insight on how to optimally allocate moderation resource. The third essay examines a market for certification and certifiers' strategic reporting behaviors. The central question is how to induce certifiers to provide statistically meaningful information to investors when they are paid by their client firms. We provide insights on how certifier competition plays an role in firms' certifier choice, how certifiers degrade their accuracies to achieve maximum profit, and how the legal environment impacts the information quality.Item Essays on experimentation in agency models(2019-05-01) Sun, Yiman; Bhaskar, V. (Venkataraman); Thomas, Caroline, (Caroline Désirée); Wiseman, Thomas E.; Hatfield, John W.This dissertation consists of three chapters in microeconomic theory with a focus on dynamic games and learning. It has applications in political economy, contracts, and industrial organization. In the first chapter, I study censorship in a dynamic game between an informed agent and an uninformed evaluator. Two types of public news are informative about the agents ability -- a conclusive good news process and a bad news process. However, the agent can censor bad news, at some cost, and will censor it if and only if this secures her a significant increase in tenure. Thus, the evaluator faces a bandit problem with an endogenous news process. When bad news is conclusive, the agent always censors when the public belief is sufficiently high, but below a threshold, she either stops censoring or only censors with some probability, depending on the information structure. The possibility of censorship hurts the evaluator and the good agent, and it may also hurt the bad agent. However, when bad news is inconclusive, I show that the good agent censors bad news more aggressively than the bad agent does. This improves the quality of information, and may benefit all players -- the evaluator, the bad agent, and the good agent. The second chapter examines the nature of contracts that optimally reward innovations in a risky environment, when the innovator is privately informed about the quality of her innovation and must engage an agent to develop it. I model the innovator as a principal who has private but imperfect information about the quality of her project: the project might be worth exploring or not, but even a project of high quality may fail. I characterize the best equilibrium for the high type principal, which is either a separating equilibrium or a pooling one. Due to the interaction between the signaling incentives of the principal and dynamic moral hazard of the agent, the best equilibrium induces inefficiently early termination of the high quality project. The high type principal is forced to share the surplus – with the agent in the separating equilibrium, or the low type principal in the pooling equilibrium. A mediator, who offers a menu of contracts and keeps the agent uncertain about which contract will be implemented, can increase the payoff of the high type principal to approximate her full information surplus. In the third chapter, I study how competition between platforms affects the process of social learning. Especially, how product differentiation affects that process. Che and Hörner (2018) show that a monopolistic platform may want to over-recommend consumers in the early phase to gather and learn information for the sake of future consumers. I show that when platforms do not differentiate their products, duopoly competition dramatically reduces the early experimentation, and the Full Transparency policy is the unique equilibrium strategy for both platforms. When platforms differentiate their products, I show that the equilibrium strategy is in between the Full Transparency policy and the optimal policy in the monopolistic case, and depends on how differentiated the products areItem Essays on information and mechanism design(2014-05) Taneva, Ina Angelova; Stinchcombe, Maxwell; Mathevet, LaurentMy dissertation studies the optimal design of institutions and information structures for different objectives of a designer or a social planner. The questions addressed are interesting both from a theoretical point of view, and in terms of their real-life applications. The first chapter of the dissertation focuses on supermodular mechanism design in environments with arbitrary finite type spaces and interdependent valuations. In these environments, the designer may have to use Bayesian equilibrium as a solution concept, because ex post implementation may not be possible. We propose direct Bayesian mechanisms that are robust to certain forms of bounded rationality while controlling for equilibrium multiplicity. In quasi-linear environments with informational and allocative externalities, we show that any Bayesian mechanism that implements a social choice function can be converted into a supermodular mechanism that also implements the original decision rule. The proposed supermodular mechanism can be chosen in a way that minimizes the size of the equilibrium set, and we provide two sets of sufficient conditions to this effect: for general decision rules and for decision rules that satisfy a certain requirement. This is followed by conditions for supermodular implementation in unique equilibrium. The second chapter looks at the incentives of a revenue-maximizing seller (designer) who discloses information to a number of interacting bidders (agents). In particular, the designer chooses the level of precision with which agents can infer the quality of a common-value object from their privately observed signals. We restrict attention to the second-price sealed-bid auction format. If the seller has perfect commitment power and can choose the precision level before observing the quality of the object, in the presence of any small cost to precision it is ex ante optimal for her to choose completely uninformative signals. For the case when the seller chooses the precision level after observing the quality of the object, we characterize pooling, partial pooling, and separating equilibria. We show that in this setting the cost associated with precision can be viewed as a form of commitment device: if costs are too low, the best pooling equilibrium ceases to exist as the high type seller is too tempted to separate. Thus, the seller ends up with a lower ex ante expected payoff than in the case when cost parameters are above a certain threshold. The third chapter of this dissertation studies the optimal choice of information structure from the perspective of a designer maximizing a certain objective function. Generally speaking, there are two ways of creating incentives for interacting agents to behave in a desired way. One is by providing appropriate payoff incentives, which is the subject of mechanism design. The other is by choosing the information that agents observe, which we refer to as information design. We consider a model of symmetric information where a designer chooses and announces the information structure about a payoff relevant state. The interacting agents observe the signal realizations, update their beliefs, and take actions which affect the welfare of both the designer and the agents. We characterize the general finite approach to deriving the optimal information structure --- the one that maximizes the designer's ex ante expected utility subject to agents playing a Bayes Nash equilibrium. We then apply the general approach to a symmetric two state, two agent, and two actions environment in a parameterized underlying game and fully characterize the optimal information structure. It is never strictly optimal for the designer to use conditionally independent private signals. The optimal information structure may be a public signal, or may consist of correlated private signals. Finally, we examine how changes in the underlying game affect the designer's maximum payoff. This exercise provides a joint mechanism/information design perspective.Item Essays on mechanism design, safety, and crime(2014-05) Shoukry, George Fouad Nabih; Abrevaya, Jason; Stinchcombe, MaxwellThis dissertation uses theoretical and empirical tools to answer applied questions of design with an emphasis on issues relating to safety and crime. The first essay incorporates safety in implementation theory and studies when and how safe mechanisms can be designed to obtain socially desirable outcomes. I provide general conditions under which a social choice rule can be implemented using safe mechanisms. The second essay is an empirical study of how criminals respond to changing profitability of crime, a question that informs the policy debate on the most effective crime fighting methods. I find that the price elasticity of theft is about 1 in the short term and increases to about 1.2 over a seven-month horizon, suggesting that policies that directly affect crime profitability, such as policies that shut down black markets or those that reduce demand for illegal goods, can be relatively effective. The third essay shows that any standard implementation problem can be formulated as a question about the existence of a graph that solves a graph coloring problem, establishing a connection between implementation theory and graph theory. More generally, an implementation problem can be viewed as a constraint satisfaction problem, and I propose an algorithm to design simple mechanisms to solve arbitrary implementation problems.Item Essays on pricing under uncertainty and heterogeneity in the finance-trade-growth nexus(2013-08) Yousefi, Seyed Reza; Whinston, Andrew B.My dissertation consists of empirical and theoretical essays on Microeconomic Theory and International Economics. The first chapter discusses the existence and characterization of a model that determines producer's optimal pricing and allocation rule as a preannounced markdown schedule. The mechanism focuses on pricing and operational implications of allotting scarce resources when customers are heterogeneous in their valuations and sensitivities towards availability of product. The proposed mechanism suggests that a carefully designed multistep markdown pricing could achieve optimal revenue when selling a single unit. However, to sell multiple units, monopolist should modify the implementation of markdown pricing by either hiding the number of available products or selling them via contingent contracts and upfront payments. In the second essay, we study the heterogeneity of finance and growth nexus across countries. Our paper contributes to the literature by investigating whether this impact differs across regions and types of economy. Using a rich dataset, cross-section and dynamic panel estimation results suggest that the beneficial effect of financial deepening on economic growth in fact displays measurable heterogeneity; it is generally smaller in oil exporting countries; in certain regions, such as the Middle East and North Africa (MENA); and in lower-income countries. Further analysis suggests that these differences might be driven by regulatory/supervisory characteristics and related to differing performance on financial access for a given level of depth. The third chapter analyzes contraction of exports in the aftermath of severe financial crises and tests for its heterogeneity across different industries and based on their credit conditions. It provides a theoretical framework to provide insight on why sectors are hit disproportionately during and in the aftermath of severe financial distresses, and confirms most of them with empirical estimations. The findings suggest that industries with greater reliance on outside financing and fewer shares of tangible assets experience greater contractions in export volumes in the years following a severe financial crisis.Item Unit-demand auctions : bridging theory and practice(2011-12) Krishnappa, Chinmayi; Plaxton, C. Greg; Gal, Anna; Klivans, Adam; Stone, Peter; Vishwanath, SriramUnit-demand auctions have been well studied with applications in several areas. In this dissertation, we discuss new variants of the unit-demand auction that are motivated by practical applications. We design mechanisms for these variants that have strong properties related to truthfulness, efficiency, scalability, and privacy. The main contributions of this dissertation can be divided into two parts. In the first part, we introduce a new variant of the classic sealed-bid unit-demand auction in which each item is associated with a put option; the put option of an item gives the seller the right to sell the item at a specified strike price to a specified bidder, regardless of market conditions. We motivate our unit-demand auction setting by discussing applications to the reassignment of leases, and to the design of multi-round auctions. For the classic sealed-bid unit-demand framework, the VCG mechanism provides a truthful auction with strong associated guarantees, including efficiency and envy-freedom. For an item in our auction, the strike price of the associated put imposes a lower bound on the auction price. Due to these lower bound constraints on auction prices, we find that the VCG mechanism is not suitable for our setting. Instead, our work draws on two fundamental techniques, one from the realm of mechanism design for numerical preferences -- the dynamic unit-demand approximate auction of Demange, Gale, and Sotomayor -- and one from the realm of mechanism design for ordinal preferences -- the Top Trading Cycles algorithm -- to obtain a natural auction that satisfies the lower bound constraints on auction prices. While we cannot, in general, achieve either efficiency or envy-freedom in our setting, our auction achieves suitably relaxed versions of these properties. For example, this auction is envy-free for all bidders who do not acquire an item via the exercise of a put. We provide a polynomial time implementation of this auction. By breaking ties in an appropriate manner, we are able to prove that this auction is truthful. In the second part, we specify rules for a dynamic unit-demand auction that supports arbitrary bid revision. In each round, the dynamic auction takes a tentative allocation and pricing as part of the input, and allows each bidder -- including a tentatively allocated bidder -- to submit an arbitrary unit-demand bid. Each round of our dynamic auction is implemented via a single application of the sealed-bid unit-demand auction proposed in the first part. We show that our dynamic auction satisfies strong properties related to truthfulness and efficiency. Using a certain privacy preservation property of each round of the auction, we show that the overall dynamic auction is highly resistant to shilling. We present a fast algorithm for implementing the proposed auction. Using this algorithm, the amortized cost of processing each bidding operation is upper bounded by the complexity of solving a single-source shortest paths problem on a graph with nonnegative edge weights and a node for each item in the auction. We also propose a dynamic price adjustment scheme that discourages sniping by providing bidders with incentives to bid early in the auction.