4 Search Results for "Kong, Yuqing"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.81
False Consensus, Information Theory, and Prediction Markets

Authors: Yuqing Kong and Grant Schoenebeck

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study a setting where Bayesian agents with a common prior have private information related to an event’s outcome and sequentially make public announcements relating to their information. Our main result shows that when agents' private information is independent conditioning on the event’s outcome whenever agents have similar beliefs about the outcome, their information is aggregated. That is, there is no false consensus. Our main result has a short proof based on a natural information-theoretic framework. A key ingredient of the framework is the equivalence between the sign of the "interaction information" and a super/sub-additive property of the value of people’s information. This provides an intuitive interpretation and an interesting application of the interaction information, which measures the amount of information shared by three random variables. We illustrate the power of this information-theoretic framework by reproving two additional results within it: 1) that agents quickly agree when announcing (summaries of) beliefs in round-robin fashion [Aaronson 2005], and 2) results from [Chen et al 2010] on when prediction market agents should release information to maximize their payment. We also interpret the information-theoretic framework and the above results in prediction markets by proving that the expected reward of revealing information is the conditional mutual information of the information revealed.
Cite as

Yuqing Kong and Grant Schoenebeck. False Consensus, Information Theory, and Prediction Markets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 81:1-81:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kong_et_al:LIPIcs.ITCS.2023.81,
  author =	{Kong, Yuqing and Schoenebeck, Grant},
  title =	{{False Consensus, Information Theory, and Prediction Markets}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{81:1--81:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.81},
  URN =		{urn:nbn:de:0030-drops-175844},
  doi =		{10.4230/LIPIcs.ITCS.2023.81},
  annote =	{Keywords: Agreeing to disagree, false consensus, information theory, prediction market}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.95
More Dominantly Truthful Multi-Task Peer Prediction with a Finite Number of Tasks

Authors: Yuqing Kong

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In the setting where we ask participants multiple similar possibly subjective multi-choice questions (e.g. Do you like Bulbasaur? Y/N; do you like Squirtle? Y/N), peer prediction aims to design mechanisms that encourage honest feedback without verification. A series of works have successfully designed multi-task peer prediction mechanisms where reporting truthfully is better than any other strategy (dominantly truthful), while they require an infinite number of tasks. A recent work proposes the first multi-task peer prediction mechanism, Determinant Mutual Information (DMI)-Mechanism, where not only is dominantly truthful but also works for a finite number of tasks (practical). However, the existence of other practical dominantly-truthful multi-task peer prediction mechanisms remains to be an open question. This work answers the above question by providing - a new family of information-monotone information measures: volume mutual information (VMI), where DMI is a special case; - a new family of practical dominantly-truthful multi-task peer prediction mechanisms, VMI-Mechanisms. To illustrate the importance of VMI-Mechanisms, we also provide a tractable effort incentive optimization goal. We show that DMI-Mechanism may not be not optimal but we can construct a sequence of VMI-Mechanisms that are approximately optimal. The main technical highlight in this paper is a novel geometric information measure, Volume Mutual Information, that is based on a simple idea: we can measure an object A’s information amount by the number of objects that is less informative than A. Different densities over the object lead to different information measures. This also gives Determinant Mutual Information a simple geometric interpretation.
Cite as

Yuqing Kong. More Dominantly Truthful Multi-Task Peer Prediction with a Finite Number of Tasks. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kong:LIPIcs.ITCS.2022.95,
  author =	{Kong, Yuqing},
  title =	{{More Dominantly Truthful Multi-Task Peer Prediction with a Finite Number of Tasks}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.95},
  URN =		{urn:nbn:de:0030-drops-156912},
  doi =		{10.4230/LIPIcs.ITCS.2022.95},
  annote =	{Keywords: Information elicitation, information theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.13
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity

Authors: Yuqing Kong and Grant Schoenebeck

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
In this paper, we propose a new mechanism - the Disagreement Mechanism - which elicits privately-held, non-variable information from self-interested agents in the single question (peer-prediction) setting. To the best of our knowledge, our Disagreement Mechanism is the first strictly truthful mechanism in the single-question setting that is simultaneously: - Detail-Free: does not need to know the common prior; - Focal: truth-telling pays strictly higher than any other symmetric equilibria excluding some unnatural permutation equilibria; - Small group: the properties of the mechanism hold even for a small number of agents, even in binary signal setting. Our mechanism only asks each agent her signal as well as a forecast of the other agents' signals. Additionally, we show that the focal result is both tight and robust, and we extend it to the case of asymmetric equilibria when the number of agents is sufficiently large.
Cite as

Yuqing Kong and Grant Schoenebeck. Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kong_et_al:LIPIcs.ITCS.2018.13,
  author =	{Kong, Yuqing and Schoenebeck, Grant},
  title =	{{Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.13},
  URN =		{urn:nbn:de:0030-drops-83174},
  doi =		{10.4230/LIPIcs.ITCS.2018.13},
  annote =	{Keywords: peer prediction, equilibrium selection, information theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.14
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case

Authors: Yuqing Kong and Grant Schoenebeck

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Prediction markets provide a unique and compelling way to sell and aggregate information, yet a good understanding of optimal strategies for agents participating in such markets remains elusive. To model this complex setting, prior work proposes a three stages game called the Alice Bob Alice (A-B-A) game - Alice participates in the market first, then Bob joins, and then Alice has a chance to participate again. While prior work has made progress in classifying the optimal strategy for certain interesting edge cases, it remained an open question to calculate Alice's best strategy in the A-B-A game for a general information structure. In this paper, we analyze the A-B-A game for a general information structure and (1) show a "revelation-principle" style result: it is enough for Alice to use her private signal space as her announced signal space, that is, Alice cannot gain more by revealing her information more "finely"; (2) provide a FPTAS to compute the optimal information revelation strategy with additive error when Alice's information is a signal from a constant-sized set; (3) show that sometimes it is better for Alice to reveal partial information in the first stage even if Alice's information is a single binary bit.
Cite as

Yuqing Kong and Grant Schoenebeck. Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kong_et_al:LIPIcs.ITCS.2018.14,
  author =	{Kong, Yuqing and Schoenebeck, Grant},
  title =	{{Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.14},
  URN =		{urn:nbn:de:0030-drops-83191},
  doi =		{10.4230/LIPIcs.ITCS.2018.14},
  annote =	{Keywords: prediction market, information revelation, optimization}
}
  • Refine by Author
  • 4 Kong, Yuqing
  • 3 Schoenebeck, Grant

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory and mechanism design

  • Refine by Keyword
  • 3 information theory
  • 2 prediction market
  • 1 Agreeing to disagree
  • 1 Information elicitation
  • 1 equilibrium selection
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2018
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact