An Algorithmic Study of Information and Contracts

Abstract

Information design and contract design are two important and well-studied fields in microeconomics. They typically address different challenges, where information design is used for information asymmetry between two players while contract design addresses moral hazard in principal-agent setups. With the rapid growth of Internet technology, online markets and businesses, including online advertising, sponsored content creation, electronic commercials and more, have begun to thrive in recent decades. This causes a demand for computational and algorithmic approaches to applying the theories of these two critical fields to handle complicated and general settings in practices. Hence, in this thesis, we present an algorithmic study of these two problems.

In Chapter 2, we apply the information design concept to a new problem of selling data to a machine learner who looks to purchase data to train his machine learning model. A key challenge in this setup is that neither the seller nor the machine learner knows the true quality of data. When designing a revenue-maximizing mechanism, a data seller faces the tradeoff between the cost and precision of data quality estimation. To address this challenge, we study a natural class of mechanisms that price data via costly signaling. Motivated by the assumption of i.i.d. data points as in classic machine learning models, we first consider selling homogeneous data and derive an optimal selling mechanism. We then turn to the sale of heterogeneous data, motivated by the sale of multiple data sets, and show that 1) on the negative side, it is NP-hard to approximate the optimal mechanism within a constant ratio e/(e+1) + o(1); while 2) on the positive side, there is a 1/k-approximate algorithm, where k is the number of the machine learner’s private types.

In Chapter 3, we further study information design and its application in click-through auctions, in which the bidders/advertisers bid to win an opportunity to show their ads but only pay for realized clicks. The payment may or may not happen, and its probability is called the click-through rate (CTR). This auction format is widely used in the industry of online advertising. Bidders have private values, whereas the seller has private information about each bidder's CTRs. We are interested in the seller's problem of partially revealing CTR information to maximize revenue. Our first result is an FPTAS to compute an approximately optimal mechanism under a constant number of bidders. The design of this algorithm leverages Bayesian bidder values which help to "smooth" the seller's revenue function and lead to better tractability. The design of this FPTAS is complex and primarily algorithmic. Our second main result pursues the design of "simple" mechanisms that are approximately optimal yet more practical. We primarily focus on the two-bidder situation, which is already notoriously challenging as demonstrated in recent works. When bidders' CTR distribution is symmetric, we develop a simple prior-free signaling scheme, whose construction relies on a parameter termed optimal signal ratio. The constructed scheme provably obtains a good approximation as long as the maximum and minimum of bidders' value density functions do not differ much.

In Chapter 4, we shift our attention to contract design, especially Bayesian contract design, where the agent has a private type. In its most general form of setups, the agent's type is inherently "multi-parameter" and can arbitrarily affect both the agent's productivity and effort costs. In contrast, a natural single-parameter setting of much recent interest simplifies the agent's type to a single value that describes the agent's cost per unit of effort, whereas agents' efforts are assumed to be equally productive. The main result of this chapter is an almost approximation-preserving polynomial-time reduction from the most general multi-parameter Bayesian contract design (BCD) to single-parameter BCD. That is, for any multi-parameter BCD instance I^M, we construct a single-parameter instance I^S such that any β-approximate contract (resp. menu of contracts) of I^S can in turn be converted to a (β-ε)-approximate contract (resp. menu of contracts) of I^M. The reduction is in time polynomial in the input size and log(1/ε); moreover, when β = 1 (i.e., the given single-parameter solution is exactly optimal), the dependence on 1/ε can be removed, leading to a polynomial-time exact reduction. This efficient reduction is somewhat surprising because in the closely related problem of Bayesian mechanism design, a polynomial-time reduction from multi-parameter to single-parameter setting is believed not to exist. Our result demonstrates the intrinsic difficulty of addressing moral hazard in Bayesian contract design, regardless of being single-parameter or multi-parameter. As byproducts, our reduction answers two open questions in recent literature of algorithmic contract design: (a) it implies that optimal contract design in single-parameter BCD is not in APX unless P=NP even when the agent's type distribution is regular, answering the open question of [Alon et al. 2021] in the negative; (b) it implies that the principal's (order-wise) tight utility gap between using a menu of contracts and a single contract is Θ(n) where n is the number of actions, answering the major open question of [Guruganesh et al. 2021] for the single-parameter case.

In Chapter 5, we initiate the computational problem of jointly designing information and contracts. We consider three possible classes of contracts with decreasing flexibility and increasing simplicity: ambiguous contracts, menus of explicit contracts and explicit single contract. Ambiguous contracts allow the principal to conceal the applied payment schemes through a contract that depends on the unknown state of nature, while explicit contracts reveal the contract prior to the agent's decision. Our results show a trade-off between the simplicity of the contracts and the computational complexity of the joint design. Indeed, we show that an approximately-optimal mechanism with ambiguous contracts can be computed in polynomial time. However, they are convoluted mechanisms and not well-suited for some real-world scenarios. Conversely, explicit menus of contracts and single contracts are simpler mechanisms, but they cannot be computed efficiently. In particular, we show that computing the optimal mechanism with explicit menus of contracts and single contracts is APX-Hard. We also characterize the structure of optimal mechanisms. Interestingly, direct mechanisms are optimal for both the most flexible ambiguous contracts and the least flexible explicit single contract, but they are suboptimal for that with menus of contracts. Finally, motivated by our hardness results, we turn our attention to menus of linear contracts and single linear contracts. We show that both the problem of computing the optimal mechanism with an explicit menu of linear contracts and an explicit single linear contract admits an FPTAS.

Date of Award	19 Dec 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor)