Person:
Gao, Xi

Profile Picture

Email Address

AA Acceptance Date

Birth Date

Research Projects

Organizational Units

Job Title

Last Name

Gao

First Name

Xi

Name

Gao, Xi
Author's Publications: search.filters.isAuthorOfPublication.d9699126-0719-4fe8-a4fc-75990a7cf058

Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    Publication
    What You Jointly Know Determines How You Act: Strategic Interactions in Prediction Markets
    (ACM Press, 2013) Gao, Xi; Zhang, Jie; Chen, Yiling
    The primary goal of a prediction market is to elicit and aggregate information about some future event of interest. How well this goal is achieved depends on the behavior of self-interested market participants, which are crucially influenced by not only their private information but also their knowledge of others' private information, in other words, the information structure of market participants. In this paper, we model a prediction market using the now-classic logarithmic market scoring rule (LMSR) market maker as an extensive-form Bayesian game and aim to understand and characterize the game-theoretic equilibria of the market for different information structures. Prior work has shown that when participants' information is independent conditioned on the realized outcome of the event, the only type of equilibria in this setting has every participant race to honestly reveal their private information as soon as possible, which is the most desirable outcome for the market's goal of information aggregation. This paper considers the remaining two classes of information structures: participants' information being unconditionally independent (the I game) and participants' information being both conditionally and unconditionally dependent (the D game). We characterize the unique family of equilibria for the I game with finite number of participants and finite stages. At any equilibrium in this family, if player i's last stage of participation in the market is after player j's, player i only reveals his information after player j's last stage of participation. This suggests that players race to delay revealing their information, which is probably the least desirable outcome for the market's goal. We consider a special case of the D game and cast insights on possible equilibria if one exists.
  • Thumbnail Image
    Publication
    Eliciting and Aggregating Truthful and Noisy Information
    (2014-10-21) Gao, Xi; Chen, Yiling; Parkes, David; Mitzenmacher, Michael; Pennock, David
    In the modern world, making informed decisions requires obtaining and aggregating relevant information about events of interest. For many political, business, and entertainment events, the information of interest only exists as opinions, beliefs, and judgments of dispersed individuals, and we can only get a complete picture by putting the separate pieces of information together. Thus, an important first step towards decision making is motivating the individuals to reveal their private information and coalescing the separate pieces of information together. In this dissertation, I study three information elicitation and aggregation methods, prediction markets, peer prediction mechanisms, and adaptive polling, using both theoretical and applied approaches. These methods mainly differ by their assumptions on the participants' behavior, namely whether the participants possess noisy or perfect information and whether they strategically decide on what information to reveal. The first two methods, prediction markets and peer prediction mechanisms, assume that the participants are strategic and have perfect information. Their primary goal is to use carefully designed monetary rewards to incentivize the participants to truthfully reveal their private information. As a result, my studies of these methods focus on understanding to what extent are these methods incentive compatible in theory and in practice. The last method, adaptive polling, assumes that the participants are not strategic and have noisy information. In this case, our goal is to accurately and efficiently estimate the latent ground truth given the noisy information, and we aim to evaluate whether this goal can be achieved by using this method experimentally. I make four main contributions in this dissertation. First, I theoretically analyze how the participants' knowledge of one another's private information affects their strategic behavior when trading in a prediction market with a finite number of participants. Each participant may trade multiple times in the market, and hence may have an incentive to withhold or misreport his information in order to mislead other participants and capitalize on their mistakes. When the participants' private information is unconditionally independent, we show that the participants reveal their information as late as possible at any equilibrium, which is arguably the worse outcome for the purpose of information aggregation. We also provide insights on the equilibria of such prediction markets when the participants' private information is both conditionally and unconditionally dependent given the outcome of the event. Second, I theoretically analyze the participants' strategic behavior in a prediction market when a participant has outside incentives to manipulate the market probability. The presence of such outside incentives would seem to damage the information aggregation in the market. Surprisingly, when the existence of such incentives is certain and common knowledge, we show that there exist separating equilibria where all the participants' private information is revealed and fully aggregated into the market probability. Although there also exist pooling equilibria with information loss, we prove that certain separating equilibria are more desirable than many pooling equilibria because the separating equilibria satisfy domination based belief refinements, maximize the social welfare of the setting, or maximize either participant's total expected payoff. When the existence of the outside incentives is uncertain, trust cannot be established and the separating equilibria no longer exist. Third, I experimentally investigate participants' behavior towards the peer prediction mechanisms, which were proposed to elicit information without observable ground truth. While peer prediction mechanisms promise to elicit truthful information by rewarding participants with carefully constructed payments, they also admit uninformative equilibria where coordinating participants provide no useful information. We conduct the first controlled online experiment of the Jurca and Faltings peer prediction mechanism, engaging the participants in a multiplayer, real-time and repeated game. Using a hidden Markov model to capture players' strategies from their actions, our results show that participants successfully coordinate on uninformative equilibria and the truthful equilibrium is not focal, even when some uninformative equilibria do not exist or result in lower payoffs. In contrast, most players are consistently truthful in the absence of peer prediction, suggesting that these mechanisms may be harmful when truthful reporting has similar cost to strategic behavior. Finally, I design and experimentally evaluate an adaptive polling method for aggregating small pieces of imprecise information together to produce an accurate estimate of a latent ground truth. In designing this method, we make two main contributions: (1) Our method aggregates the participants' noisy information by using a theoretical model to account for the noise in the participants' contributed information. (2) Our method uses an active learning inspired approach to adaptively choose the query for each participant. We apply this method to the problem of ranking a set of alternatives, each of which is characterized by a latent strength parameter. At each step, adaptive polling collects the result of a pairwise comparison, estimates the strength parameters from the pairwise comparison data, and adaptively chooses the next pairwise comparison question to maximize expected information gain. Our MTurk experiment shows that our adaptive polling method can effectively incorporate noisy information and improve the estimate accuracy over time. Compared to a baseline method, which chooses a random pairwise comparison question at each step, our adaptive method can generate more accurate estimates with less cost.
  • Thumbnail Image
    Publication
    Trick or Treat: Putting Peer Prediction to the Test
    (Association of Computing Machinery, 2014) Gao, Xi; Mao, Andrew; Chen, Yiling; Adams, Ryan Prescott
    Collecting truthful subjective information from multiple individuals is an important problem in many social and online systems. While peer prediction mechanisms promise to elicit truthful information by rewarding participants with carefully constructed payments, they also admit uninformative equilibria where coordinating participants provide no useful information. To understand how participants behave towards such mechanisms in practice, we conduct the first controlled online experiment of a peer prediction mechanism, engaging the participants in a multiplayer, real-time and repeated game. Using a hidden Markov model to capture players' strategies from their actions, our results show that participants successfully coordinate on uninformative equilibria and the truthful equilibrium is not focal, even when some uninformative equilibria do not exist or are undesirable. In contrast, most players are consistently truthful in the absence of peer prediction, suggesting that these mechanisms may be harmful when truthful reporting has similar cost to strategic behavior.
  • Thumbnail Image
    Publication
    Trick or treat
    (ACM, 2014) Gao, Xi; Mao, Andrew; Chen, Yiling; Adams, Ryan Prescott
    Collecting truthful subjective information from multiple individuals is an important problem in many social and online systems. While peer prediction mechanisms promise to elicit truthful information by rewarding participants with carefully constructed payments, they also admit uninformative equilibria where coordinating participants provide no useful information. To understand how participants behave towards such mechanisms in practice, we conduct the first controlled online experiment of a peer prediction mechanism, engaging the participants in a multiplayer, real-time and repeated game. Using a hidden Markov model to capture players’ strategies from their actions, our results show that participants successfully coordinate on uninformative equilibria and the truthful equilibrium is not focal, even when some uninformative equilibria do not exist or are undesirable. In contrast, most players are consistently truthful in the absence of peer prediction, suggesting that these mechanisms may be harmful when truthful reporting has similar cost to strategic behavior.
  • Thumbnail Image
    Publication
    Betting on the Real Line
    (Springer-Verlag, 2009) Gao, Xi; Chen, Yiling; Pennock, David M.
    We study the problem of designing prediction markets for random variables with continuous or countably infinite outcomes on the real line. Our interval betting languages allow traders to bet on any interval of their choice. Both the call market mechanism and two automated market maker mechanisms, logarithmic market scoring rule (LMSR) and dynamic parimutuel markets (DPM), are generalized to handle interval bets on continuous or countably infinite outcomes. We examine problems associated with operating these markets. We show that the auctioneer's order matching problem for interval bets can be solved in polynomial time for call markets. DPM can be generalized to deal with interval bets on both countably infinite and continuous outcomes and remains to have bounded loss. However, in a continuous-outcome DPM, a trader may incur loss even if the true outcome is within her betting interval. The LMSR market maker suffers from unbounded loss for both countably infinite and continuous outcomes.
  • Thumbnail Image
    Publication
    Market Manipulation with Outside Incentives
    (American Association for Artificial Intelligence, 2011) Chen, Yiling; Gao, Xi; Goldstein, Rick David; Kash, I
    Much evidence has shown that prediction markets, when used in isolation, can effectively aggregate dispersed information about uncertain future events and produce remarkably accurate forecasts. However, if the market prediction will be used for decision making, a strategic participant with a vested interest in the decision outcome may want to manipulate the market prediction in order to influence the resulting decision. The presence of such incentives outside of the market would seem to damage information aggregation because of the potential distrust among market participants. While this is true under some conditions, we find that, if the existence of such incentives is certain and common knowledge, then in many cases, there exists a separating equilibrium for the market where information is fully aggregated. This equilibrium also maximizes social welfare for convex outside payoff functions. At this equilibrium, the participant with outside incentives makes a costly move to gain the trust of other participants. When the existence of outside incentives is uncertain, however, trust cannot be established between players if the outside incentive is sufficiently large and we lose the separability in equilibrium.
  • Thumbnail Image
    Publication
    An Axiomatic Characterization of Continuous-Outcome Market Makers
    (Springer Verlag, 2010) Gao, Xi; Chen, Yiling
    Most existing market maker mechanisms for prediction markets are designed for events with a finite number of outcomes. All known attempts on designing market makers for forecasting continuous-outcome events resulted in mechanisms with undesirable properties. In this paper, we take an axiomatic approach to study whether it is possible for continuous-outcome market makers to satisfy certain desirable properties simultaneously. We define a general class of continuous-outcome market makers, which allows traders to express their information on any continuous subspace of their choice. We characterize desirable properties of these market makers using formal axioms. Our main result is an impossibility theorem showing that if a market maker offers binary-payoff contracts, either the market maker has unbounded worst case loss or the contract prices will stop being responsive, making future trades no longer profitable. In addition, we analyze a mechanism that does not belong to our framework. This mechanism has a worst case loss linear in the number of submitted orders, but encourages some undesirable strategic behavior.