More Like this

1. A Truthful Cardinal Mechanism for One-Sided Matching

   https://doi.org/10.1137/1.9781611975994.129  

   Abebe, Rediet ; Cole, Richard ; Gkatzelis, Vasilis ; Hartline, Jason D. ( January 2020 , ACM-SIAM Symposium on Discrete Algorithms)

   We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value vij for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the vij values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest. 

   more » « less
2. Contract Design for Afforestation Programs

   Immorlica, Nicole ; Li, Wanyi ; Lucier, Brendan ( July 2020 , AI For Social Good Workshop)

   Trees on farms provide environmental benefits to society and improve agricultural productivity for farmers. We study incentive schemes for afforestation on farms through the lens of contract theory, designing conditional cash transfer schemes that encourage farmers to sustain tree growth. We capture the tree growth process as a Markov chain whose evolution is affected by the agent’s (farmer) actions – e.g., investing costly effort or cutting the tree for firewood. The principal has imperfect information about the agent’s costs and actions taken, and wants to maximize long-run tree survival with minimal payment. We show how to calculate the optimal contract structure in our model: notably, it can involve time-varying payments and may incentivize the agent to join the program but abandon it prematurely. 

   more » « less
3. Contract design for purchasing private data using a biased differentially private algorithm

   https://doi.org/10.1145/3338506.3340273  

   Khalili, Mohammad Mahdi ; Zhang, Xueru ; Liu, Mingyan ( June 2019 , 14th Workshop on the Economics of Networks, Systems and Computation)

   Personal information and other types of private data are valuable for both data owners and institutions interested in providing targeted and customized services that require analyzing such data. In this context, privacy is sometimes seen as a commodity: institutions (data buyers) pay individuals (or data sellers) in exchange for private data. In this study, we examine the problem of designing such data contracts, through which a buyer aims to minimize his payment to the sellers for a desired level of data quality, while the latter aim to obtain adequate compensation for giving up a certain amount of privacy. Specifically, we use the concept of differential privacy and examine a model of linear and nonlinear queries on private data. We show that conventional algorithms that introduce differential privacy via zero-mean noise fall short for the purpose of such transactions as they do not provide sufficient degree of freedom for the contract designer to negotiate between the competing interests of the buyer and the sellers. Instead, we propose a biased differentially private algorithm which allows us to customize the privacy-accuracy tradeoff for each individual. We use a contract design approach to find the optimal contracts when using this biased algorithm to provide privacy, and show that under this combination the buyer can achieve the same level of accuracy with a lower payment as compared to using the unbiased algorithms, while incurring lower privacy loss for the sellers. 

   more » « less
4. Effective Premium Discrimination for Designing Cyber Insurance Policies with Rare Losses

   https://doi.org/10.1007/978-3-030-32430-8_16  

   Khalili, M. ; Zhang, X. ; Liu, M. ( October 2019 , Conference on Decision and Game Theory for Security (GameSec))

   null (Ed.)

   Cyber insurance like other types of insurance is a method of risk transfer, where the insured pays a premium in exchange for coverage in the event of a loss. As a result of the reduced risk for the insured and the lack of information on the insurer’s side, the insured is generally inclined to lower its effort, leading to a worse state of security, a common phenomenon known as moral hazard. To mitigate moral hazard, a widely employed concept is premium discrimination, i.e., an agent/insured who exerts higher effort pays less premium. This, however, relies on the insurer’s ability to assess the effort exerted by the insured. In this paper, we study two methods of premium discrimination that rely on two different types of assessment: pre-screening and post-screening. Pre-screening occurs before the insured enters into a contract and can be done at the beginning of each contract period; the result of this process gives the insurer an estimated risk on the insured, which then determines the contract terms. The post-screening mechanism involves at least two contract periods whereby the second-period premium is increased if a loss event occurs during the first period. Prior work shows that both pre-screening and post-screening are generally effective in mitigating moral hazard and increasing the insured’s effort. The analysis in this study shows, however, that the conclusion becomes more nuanced when loss events are rare. Specifically, we show that post-screening is not effective at all with rare losses, while pre-screening can be an effective method when the agent perceives them as rarer than the insurer does; in this case pre-screening improves both the agent’s effort level and the insurer’s profit. 

   more » « less
5. Information Design in Spatial Resource Competition

   Yang, Pu ; Iyer, Krishnamurthy ; Frazier, Peter I. ( December 2019 , Lecture notes in computer science)

   We consider information design in spatial resource competition, motivated by ride sharing platforms sharing information with drivers about rider demand. Each of N co-located agents (drivers) decides whether to move to another location with an uncertain and possibly higher resource level (rider demand), where the utility for moving increases in the resource level and decreases in the number of other agents that move. A principal who can observe the resource level wishes to share this information in a way that ensures a welfare-maximizing number of agents move. Analyzing the principal’s information design problem using the Bayesian persuasion framework, we study both private signaling mechanisms, where the principal sends personalized signals to each agent, and public signaling mechanisms, where the principal sends the same information to all agents. We show: 1) For private signaling, computing the optimal mechanism using the standard approach leads to a linear program with 2 N variables, rendering the computation challenging. We instead describe a computationally efficient two-step approach to finding the optimal private signaling mechanism. First, we perform a change of variables to solve a linear program with O(N^2) variables that provides the marginal probabilities of recommending each agent move. Second, we describe an efficient sampling procedure over sets of agents consistent with these optimal marginal probabilities; the optimal private mechanism then asks the sampled set of agents to move and the rest to stay. 2) For public signaling, we first show the welfare-maximizing equilibrium given any common belief has a threshold structure. Using this, we show that the optimal public mechanism with respect to the sender-preferred equilibrium can be computed in polynomial time. 3) We support our analytical results with numerical computations that show the optimal private and public signaling mechanisms achieve substantially higher social welfare when compared with no-information and full-information benchmarks. 

   more » « less