Events Calendar

PhD Defense - Ruixin Qiang

Title: Do Humans Play Dice? Choice Making with Randomization

Time: 10 am on Friday, October 19th, 2018
Location: SAL 322

Ph.D. Candidate: Ruixin Qiang

Committee:
Prof. David Kempe
Prof. Shaddin Dughmi
Prof. Odilon Camara
Prof. Ming-Deh Huang

Abstract:
Making choices with a die sounds unhelpful, and may be adopted only by students who do not know the correct answer during exams. However, there are cases for which rolling a die is the best way to solve the problem. Allocating limited resources fairly is a common scenario that randomness is adopted. For example, the H1B lottery used by USCIS to select who can get the visa. On the other hand, making a choice randomly may be the only way to benefit oneself. In a repeated rock-paper-scissors game, a deterministic player can never win, unless his opponent does not observe he never changes his strategy. In this thesis, we examine several scenarios when randomization does and does not work.

We first study information structure design, also called ``persuasion'' or ``signaling,'' in the presence of a constraint on the amount of communication. We focus on the fundamental setting of bilateral trade, which in its simplest form involves a seller with a single item to price, a buyer whose value for the item is drawn from a common prior distribution over n different possible values, and a take-it-or-leave-it-offer protocol. A mediator with access to the buyer's type may partially reveal such information to the seller in order to further some objective such as the social welfare or the seller's revenue. A simple example can show that revealing the information deterministically is not optimal for the social welfare. We study how randomization can help in the communication constrained setting.

We next study the existence of dice-based winner-selection rules for given interim rules. In a winner-selection environment, multiple winners are selected from a candidate set, subject to certain feasibility constraints. The interim rule summarizes the probability of each candidate is selected. We show that when the feasibility constraint is a matroid constraint, any feasible interim rule admits a dice-based implementation. A dice-based implementation associates each candidate a die. To choose the winner, the rule rolls all dice and picks the subset that maximizes the sum of rolled value, subject to the feasibility constraint.

Aside from the scenarios in which dice can help, we also show two cases when they fail. Both of the cases fall in the Bayesian Persuasion model of Kamenica and Gentzkow. For one setting, we show that our positive algorithmic results for bilateral trade do not extend to communication-constrained signaling in the Bayesian Persuasion model. Specifically, we show that it is NP-hard to approximate the optimal sender's utility to within any constant factor in the presence of communication constraints. For the other, we treat Bayesian persuasion as a winner-selection environment and show an instance that does not admit a dice-based implementation.

Location: Henry Salvatori Computer Science Center (SAL) - 322

Audiences: Everyone Is Invited

Contact: Ryan Rozan