1 Search Results for "Qiang, Ruixin"

Document

DOI: 10.4230/LIPIcs.ITCS.2019.31

Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice

Authors: Shaddin Dughmi, David Kempe, and Ruixin Qiang

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract

To select a subset of samples or "winners" from a population of candidates, order sampling [Rosén, 1997] and the k-unit Myerson auction [Myerson, 1981] share a common scheme: assign a (random) score to each candidate, then select the k candidates with the highest scores. We study a generalization of both order sampling and Myerson's allocation rule, called winner-selecting dice. The setting for winner-selecting dice is similar to auctions with feasibility constraints: candidates have random types drawn from independent prior distributions, and the winner set must be feasible subject to certain constraints. Dice (distributions over scores) are assigned to each type, and winners are selected to maximize the sum of the dice rolls, subject to the feasibility constraints. We examine the existence of winner-selecting dice that implement prescribed probabilities of winning (i.e., an interim rule) for all types. Our first result shows that when the feasibility constraint is a matroid, then for any feasible interim rule, there always exist winner-selecting dice that implement it. Unfortunately, our proof does not yield an efficient algorithm for constructing the dice. In the special case of a 1-uniform matroid, i.e., only one winner can be selected, we give an efficient algorithm that constructs winner-selecting dice for any feasible interim rule. Furthermore, when the types of the candidates are drawn in an i.i.d. manner and the interim rule is symmetric across candidates, unsurprisingly, an algorithm can efficiently construct symmetric dice that only depend on the type but not the identity of the candidate. One may ask whether we can extend our result to "second-order" interim rules, which not only specify the winning probability of a type, but also the winning probability conditioning on each other candidate's type. We show that our result does not extend, by exhibiting an instance of Bayesian persuasion whose optimal scheme is equivalent to a second-order interim rule, but which does not admit any dice-based implementation.

Cite as

Shaddin Dughmi, David Kempe, and Ruixin Qiang. Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ITCS.2019.31,
  author =	{Dughmi, Shaddin and Kempe, David and Qiang, Ruixin},
  title =	{{Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.31},
  URN =		{urn:nbn:de:0030-drops-101248},
  doi =		{10.4230/LIPIcs.ITCS.2019.31},
  annote =	{Keywords: Interim rule, order sampling, virtual value function, Border's theorem}
}

Refine by Author
1 Dughmi, Shaddin
1 Kempe, David
1 Qiang, Ruixin

Refine by Classification
1 Theory of computation → Algorithmic game theory

Refine by Keyword
1 Border's theorem
1 Interim rule
1 order sampling
1 virtual value function

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Qiang, Ruixin"

Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice

Abstract

Cite as

Thanks for your feedback!

Could not send message