Browsing by Subject "Mechanism design"

Cremer and McLean 1985 shows that if buyers valuations are suciently correlated, there is a mechanism that allows the seller to extract the full surplus from the buyers. However, in practice, we do not see the Cremer-McLean mechanism employed. In this thesis, I demonstrate that one reason that the Cremer-McLean mechanism

is not implemented in practice is because the mechanism requires very precise assumptions about the underlying distributions of the buyers. I demonstrate that a small mis-estimation of the underlying distribution can have large and signicant effects on the outcome of the mechanism. I further prove that the Cremer-McLean mechanism cannot be approximated by a simple second price auction, i.e. there is no approximating factor when using a second price auction with reserve in either outcome or expectation for the Cremer-McLean mechanism. Further, I show that there is no mechanism that approximates the Cremer-McLean mechanism for bidders with

regular distributions in a single item auction if the correlation among buyers is not considered. Finally, I introduce a new mechanism that is robust to distribution mis-estimation and show empirically that it outperforms the Cremer-McLean mechanism on average in cases of distribution mis-estimation and I show that the mechanism can

be determined in polynomial time in the number of types of the buyers.

This dissertation studies coordination mechanism design for sustainable supply networks in a globalized environment, with the goal of achieving long-term profitability, environmental friendliness and social responsibility. We examine three different types of supply networks in detail.

The first network consists of one supplier and multiple retailers. The main issue is how to efficiently share a scarce resource, such as capacities for green technology, among all members with private information under dynamically changing environment. We design a shared surplus supply agreement among the members which can lead to both efficient private investments and efficient capacity allocation under unpredictable and unverifiable market conditions.

The second network is a serial supply chain. The source node provides critical raw material (like coffee cherries) for the entire chain and is typically located in an underdeveloped economy, the end node is a retailer serving consumer at a developed economy (like Starbucks Co.). We construct a dynamic supply agreement that takes into account the changing market and production conditions to ensure fair compensations so that the partners have the right incentives to work together to develop sustainable quality supply.

The third network is a stylized global production network of a multinational company consisting of a home plant and a foreign branch. The branch serves the foreign market but receives a key component from the home plant. The distinctive feature is that both facilities belong to the same company, governed by the headquarters, yet they each also have their own autonomies. We analyze the role of the headquarters in designing coordination mechanism to improve efficiency. We show the headquarters can delegate the coordination effort to the home plant, as long as it keeps veto power.

Inspired by various applications including ad auctions, matching markets, and voting, mechanism design deals with the problem of designing algorithms that take inputs from strategic agents and return an outcome optimizing a given objective, while taking the strategic behavior from the agents into account.

The focus of this thesis is to design mechanisms in dynamic environments that take into account rich constraints (e.g., budget constraints), features (e.g., robustness and credibility), and different types of agents (e.g., utility-maximizing agents and learning agents). Two main reasons why dynamic mechanism design is hard compared to mechanism design in a static environment are the need to make decisions in an online manner while the future might be unpredictable or even be chosen by an adversary arbitrarily, and the need to cope with strategic agents, who aim to maximize their cumulative utilities by looking into the future.

We propose a framework to design dynamic mechanisms with simple structures for utility-maximizing agents without losing any optimality, which facilitates both the design for the designer and the participation for the agents. Our framework enables the design of mechanisms achieving non-trivial performance guarantees relative to the optimal mechanism that has access to all future information in advance, even though our mechanisms are not equipped with any knowledge about the future. We further develop a class of dynamic mechanisms that are robust against estimation errors in agents' valuation distributions, a class of dynamic mechanisms that are credible so that the designer is incentivized to follow the rules, and a class of dynamic mechanisms for learning agents. In addition to dynamic mechanism design frameworks, we develop statistical tools to test whether a dynamic mechanism has correctly aligned the agents' incentives, and to measure the extent of the misalignment if it exists.

I characterize optimal long term contracts offered by a monopolist to a buyer whose private valuation evolves according to a branching process with privately known transition probability. The optimal contract can be implemented in a simple way, and presents the buyer with a tradeoff between a high initial fixed fee and low future prices. In an interaction with a long time horizon, the relationship will terminate prematurely with probability close to one. Optimal mechanisms are quite different from models in which the transition probability is known, and the buyer's private information is his initial valuation. Optimal contracts resemble the structure of term life insurance contracts, and have features similar to actual interactions between retailers and suppliers.

This dissertation uses game theoretic models to examine the effects of agent anonymity on markets for goods and for information. In open, anonymous settings, such as the Internet, anonymity is relatively easy to obtain --- oftentimes another email address is sufficient. By becoming anonymous, agents can participate in various mechanisms (such as elections, opinion polls, auctions, etc.) multiple times. The first chapter (joint work with Vincent Conitzer) studies elections that disincentivize voters from voting multiple times. A voting rule is false-name-proof if no agent ever benefits from casting additional votes. In elections with two alternatives, it is shown that there is a unique false-name-proof voting rule that is most responsive to votes. The probability that this rule selects the majority winner converges to 1 as the population grows large. Methods to design analogous rules for elections with 3 or more alternatives are proposed. The second chapter (also joint work with Vincent Conitzer) extends the analysis in the first chapter to broader mechanism design settings, where the goal is to disincentivize agents from participating multiple times. The cost model from the first chapter is generalized and revelation principles are proven. The third chapter studies a setting where firms are able to recognize their previous customers, and may use information about consumers' purchase histories to price discriminate (which may incentivize consumers to be anonymous). The formal model considers a monopolist and a continuum of heterogeneous consumers, where consumers are able to maintain their anonymity at some cost. It is shown that when consumers can costlessly maintain their anonymity, they all individually choose to do so, which paradoxically results in the highest profit for the monopolist. Increasing the cost of anonymity can benefit consumers, but only up to a point; at that point, the effect is reversed. Some of the results are extended to a setting with two competing firms selling differentiated products. Finally, the cost of maintaining anonymity is endogenized by considering a third party that can make consumers anonymous for a fee of its choosing. It is shown that this third party would prefer to be paid by the firm for allowing consumers to costlessly maintain their anonymity.

This dissertation collects work concerning the way individuals deal with imperfect information, both related to their knowledge of themselves and of others. The second chapter shows that bounded rationality, in the form of limited knowledge of utility, is an explanation for common stylized facts of prospect theory like loss aversion, status quo bias and non-linear probability weighting. Locally limited utility knowledge is considered within a classical demand model framework, suggesting that costs of inefficient search for optimal consumption will produce a value function that obeys the loss aversion axiom of Tversky and Kahneman (1991). Moreover, since this adjustment happens over time, new predictions are made that explain why the status quo bias is reinforced over time. This search can also describe the behavior of a consumer facing an uncertain future wealth level. The search cost justifies non-linear forms of probability weighting. The effects that have been observed in experiments will follow as a consequence.

The third chapter looks to understand how firms create and maintain long term relationships with consumers, or how procurement relations evolve over time, by studying a dynamic variant of the classical two-type-buyer contract in mechanism design. It is less trivial and more interesting if the utility determinant (or utility type) is not fixed or completely random, and fair assumptions are that it is either stochastic, or given by a distribution whose parameters are common knowledge. The first approach is that of Battaglini (2005), while the second is pursued in this paper. With two possible types of buyers, the buyer more likely to have a high utility type will receive the first-best allocations, while the other will receive the first best only if he has the high utility type.

The last chapter analyzes a dynamic procurement setting with promise keeping, where two firms (agents) with private information on their costs contract competitively with a principal. To this end, two models are proposed and the optimal allocations are determined. The agents face liquidity constraints, which induce distortions when high marginal costs are reported. We deduce that the principal uses promised utilities to incentivize the agents, which act as state variables in the recursive maximization problem. High cost types are allocated less than efficient quantities and the inefficiency of the allocation is relieved as the promised utilities increase.

\abstract

{\em Mechanism design} studies optimization problems taking into accounts of the selfish agents. {\em Network externality} is the effect a consumer receives from other consumers of the same good. This effect can be negative or positive. We first consider several mechanism design problems under the network externality assumption. The externality model used in this dissertation is more general than the widely used cardinality based model. In particular the network we consider in this dissertation is a graph, which is not necessarily complete. Our goal is to design {\em truthful} mechanisms to maximize the seller's revenue. Our main results under the network externality utility model are several optimal or near optimal mechanisms for {\em digital goods auctions}. To do so we invent several novel approximation schemes as well as applying results from the {\em approximation algorithm} literature. In particular when the agents exhibit negative network externality, we first model the problem as a two staged {\em pricing game}. We then show that the pricing game is an exact {\em potential game} which always admits a pure {\em Nash Equilibrium}. We then study the {\em best} and {\em worst} Nash Equilibrium in this game in terms of the revenue. We show two positive results. For the best Nash Equilibrium we show a $2$-approximation to the maximum revenue on bipartite graphs. For the worst Nash Equilibrium we use the notion of a {\em $\delta$-relaxed} equilibrium. In the sense that the prices for the same type of agents are within $\delta$ factor of each other. We accompany our positive results with matching hardness results. On the other hand, when the agents exhibit positive network externality, we take the {\em Myersonian} approach. We first give a complete characterization for all the truthful mechanisms. Using this characterization we present a truthful mechanism which achieves the optimal expected revenue among all the truthful mechanisms when the prior distributions of the agents are {\em independent} and {\em regular}. We also show near optimal mechanisms when the prior distributions are possibly {\em correlated}.

{\em Prior-free} auctions can approximate meaningful benchmarks for

non-identical bidders only when sufficient qualitative information

about the bidder asymmetry is publicly known.

We consider digital goods auctions where there is a {\em

total ordering} of the bidders that is known to the seller,

where earlier bidders are in some sense thought to have higher

valuations.

We define

an appropriate revenue benchmark: the maximum revenue that can be

obtained from a bid vector using prices that are nonincreasing in the

bidder ordering and bounded above by the second-highest bid.

This {\em monotone-price benchmark} is always as large as the well-known

fixed-price benchmark, so designing prior-free auctions with

good approximation guarantees is only harder.

By design, an auction that approximates the monotone-price benchmark

satisfies a very strong guarantee: it is, in particular, simultaneously

near-optimal for

essentially every {\em Bayesian} environment in which bidders'

valuation distributions have nonincreasing monopoly prices, or in

which the distribution of each bidder stochastically dominates that

of the next. Even when there is no distribution over bidders'

valuations, such an auction still provides a quantifiable

input-by-input performance guarantee. We design a simple $O(1)$-competitive prior-free

auction for digital goods with ordered bidders.

This dissertation considers practical operational settings, in which a decision maker needs to either coordinate preferences or to align incentives among different parties. We formulate these issues into stochastic optimization problems and use a variety of techniques from the theories of applied probability, queueing and dynamic programming.

First, we study a stochastic matching problem. We consider matching over time with short and long-lived players who are very sensitive to mismatch, and propose a novel method to characterize the mismatch. In particular, players' preferences are uniformly distributed on a circle, so the mismatch between two players is characterized by the one-dimensional circular angle between them. This framework allows us to capture matching processes in applications ranging from ride sharing to job hunting. Our analytical framework relies on threshold matching policies, and is focused on a limiting regime where players demonstrate low tolerance towards mismatch. This framework yields closed-form optimal matching thresholds. If the matching process is controlled by a centralized social planner (e.g. an online matching platform), the matching threshold reflects the trade-off between matching rate and matching quality. The corresponding optimal matching threshold is smaller than myopic matching threshold, which helps building market thickness. We further compare the centralized system with decentralized systems, where players decide their matching partners. We find that matching controlled by either side of the market may achieve optimal social welfare.

Second, we consider a dynamic incentive management problem in which a principal induces effort from an agent to reduce the arrival rate of a Poisson process of adverse events. The effort is costly to the agent, and unobservable to the principal, unless the principal is monitoring the agent. Monitoring ensures effort but is costly to the principal. The optimal contract involves monetary payments and monitoring sessions that depend on past arrival times. We formulate the problem as a stochastic optimal control model and solve the problem analytically. The optimal schedules of payment and monitoring demonstrate different structures depending on model parameters. Overall, the optimal dynamic contracts are simple to describe, easy to compute and implement, and intuitive to explain.

The revelation principle is a key tool in mechanism design. It allows the designer to restrict attention to the class of truthful mechanisms, greatly facilitating analysis. This is also borne out in an algorithmic sense, allowing certain computational prob- lems in mechanism design to be solved in polynomial time. Unfortunately, when not every type can misreport every other type (the partial verification model), or—more generally—misreporting can be costly, the revelation principle can fail to hold. This also leads to NP-hardness results.

The primary contribution of this work consists of characterizations of conditions under which the revelation principle still holds when reporting can be costly. (These are generalizations of conditions given earlier for the partial verification case) In fact, our results extend to cases where, instead of being able to report types directly, agents may be limited to sending signals that do not directly correspond to types. In this case, we obtain conditions for when the mechanism designer can restrict attention to a given (but arbitrary) mapping from types to signals without loss of generality. We also study associated computational problems.

This dissertation studies dynamic pricing in service systems where the system state is defined as the wait time. The first essay studies a single-server queue where customers arrive according to a Poisson process. The service provider announces the price rate and current system wait time to incoming customers, who decide whether to join the queue and determine their service duration. The objective is to maximize either the long-run average revenue or social welfare. The problem is formulated as a continuous-time control model, and we develop an innovative method to obtain the optimal control policy. The optimal dynamic pricing policy reveals the compensation effect, where the service provider lowers the price rate when the wait time exceeds a threshold, in addition to the usual congestion effect. A numerical study demonstrates the superiority of the revenue-maximizing pricing policy over static pricing policies, especially for low arrival rates and impatient customers. The extension to nonlinear pricing and heterogeneous customers yields similar policy insights, showcasing the value of considering customer characteristics in dynamic pricing models. The proposed model can be utilized to design dynamic pricing schemes for fast-charging stations.

The second essay addresses a mechanism design problem for a single-server queue with customers arriving according to a Poisson process and possessing private information about their wait time sensitivity. Following a direct mechanism, where the service provider announces the system wait time and offers a menu of options to each arriving customer. By choosing an option or opting out, customers aim to maximize their utility. The objective is to design a mechanism that maximizes the long-run average revenue. The optimal mechanism is wait-time dependent and admits customers with lower wait-time sensitivities. The model reveals strategic complementarity between admission decisions and service times which became the admission threshold, and offered service time decreases as the wait time increases. Comparisons with simpler heuristic mechanisms quantify the value of the optimal mechanism, showing significantly higher revenue generation, particularly for moderate service costs and arrival rates. Modifying service times becomes crucial when considering the different customer types and their interaction with wait time.

The third essay investigates a queueing system where the firm strategically determines the release time of each arriving request. We consider a first-come-first-serve single-server system, with customer requests arriving according to a Poisson process. The base model includes two types of customers: impatient and patient, characterized by their privately known service valuations and time sensitivities. The chapter explores the potential of strategically delaying the release of products to improve system performance. It reveals that such a delay occurs when the proportion of impatient customers is high and the system wait time is shorter than the threshold. Importantly, the optimal inflated release time does not vary with the system wait time, facilitating practical implementation. The extension to continuous-type customers confirms the tangible impact of strategic delay on revenue improvement, particularly when faced with uncertainty in the types of arriving requests.