The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

Transportation is important in making supply chain decisions. With the careful consideration of transportation expenses, the performance of each supply chain member, as well as the entire supply chain, could be improved significantly. The purpose of this research is: 1) to explore and identify the various situations that relate to replenishment and transportation activities; and 2) to reveal the strength of the connection between purchase quantity and transportation discounts, and integrate the two discounts to enhance supply-chain coordination. The problem is analyzed and categorized into four representative cases, depending on transportation. To aid the supplier or the carrier to determine the discount that should be offered, in light of the buyer's reaction to that discount, decision models are proposed under three different circumstances. First, assuming a single product, we investigate the quantity discounts from the supplier's perspective, via a noncooperative game-theoretical approach and also a joint decision model. Taking into account the price elasticity of demand, this analysis aids a sole supplier in establishing an all-unit quantity discount policy in light of the buyer's best reaction. The Stackelberg equilibrium and the Pareto-optimal solution set are derived for the noncooperative and joint-decision cases, respectively. Our research indicates that channel efficiency can be improved significantly if the quantity discount decision is made jointly rather than noncooperatively. Moreover, we extend our model in several directions: (a) the product is transported by a private fleet; (b) the buyer may choose to offer her customers a different percentage discount than that she obtained from the supplier; and (c) the case of multiple (heterogeneous) buyers. Numerical examples are employed, here and throughout the thesis, to illustrate the practical applications of the models presented and the sensitivity to model parameters. Secondly, we consider a situation with a family of SKUs for which the supplier will offer a quantity discount, according to the aggregate purchases of the product group. Management of those items is based on the modified periodic policy. From the supplier's point of view, what are the optimal parameters (breakpoint and discount percentage)? For deterministic demand, we discuss the cases in which demand is both constant and price-sensitive. First as a noncooperative Stackelberg game, and then when the two parties make the discount and replenishment decisions jointly, we illustrate the impact of price-sensitivity and joint decision making on the supplier's discount policy. The third approach studies the case in which transportation of the goods by a common carrier (a public, for-hire trucking company) is integrated in the quantity discount decisions. In reality, it is quite difficult for the carrier to determine the proper transportation discount, especially in the case of LTL (less-than-truckload) trucking. This is not only because of the "phantom freight" phenomenon, caused by possible over-declaration of the weight by the shipper, but also due to the fact that the discount relates to both transportation and inventory issues. In this research, we study the problem of coordinating the transportation and quantity discount decisions from the perspectives of the parties who offer the discounts, rather than the ones that take them. By comparison of the noncooperative and cooperative models, we show that cooperation provides better overall results, not only to each party, but also to the entire supply chain. To divide the extra payoffs gained from that cooperation, we further conduct a coalition analysis, based upon the concept of "Shapley Value." A detailed algorithm and numerical examples are provided to illustrate the solution procedure. Finally, the thesis concludes with comprehensive remarks. We summarize the contributions of this thesis, show the overall results obtained here, and present the directions that our research may take in the future.

Thesis (Ph. D.)--University of California, San Diego, 2007. / Title from first page of PDF file (viewed August 7, 2007). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 86-90).

Thesis (M.S. in Defense Analysis)--Naval Postgraduate School, 2007. / Cover title. "December 2007." AD-A476 373. Includes bibliographical references. Electronic version available on the Public STINET.

Thesis (M.Sc.) - Carleton University, 2006. / Includes bibliographical references (p. 90-92). Also available in electronic format on the Internet.

Thesis (M. Phil.)--University of Hong Kong, 2007. / Title proper from title frame. Also available in printed format.

Thesis (Ph. D.)--University of California, San Diego, 1997. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of California, San Diego, 1999. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of California, San Diego, 2001. / Vita. Includes bibliographical references (leaves 103-117).