3 Search Results for "Echenique, Federico"


Document
New Characterizations of Core Imputations of Matching and b-Matching Games

Authors: Vijay V. Vazirani

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)


Abstract
We give new characterizations of core imputations for the following games: 1) The assignment game. 2) Concurrent games, i.e., general graph matching games having non-empty core. 3) The unconstrained bipartite b-matching game (edges can be matched multiple times). 4) The constrained bipartite b-matching game (edges can be matched at most once). The classic paper of Shapley and Shubik [Shapley and Shubik, 1971] showed that core imputations of the assignment game are precisely optimal solutions to the dual of the LP-relaxation of the game. Building on this, Deng et al. [Deng et al., 1999] gave a general framework which yields analogous characterizations for several fundamental combinatorial games. Interestingly enough, their framework does not apply to the last two games stated above. In turn, we show that some of the core imputations of these games correspond to optimal dual solutions and others do not. This leads to the tantalizing question of understanding the origins of the latter. We also present new characterizations of the profits accrued by agents and teams in core imputations of the first two games. Our characterization for the first game is stronger than that for the second; the underlying reason is that the characterization of vertices of the Birkhoff polytope is stronger than that of the Balinski polytope.

Cite as

Vijay V. Vazirani. New Characterizations of Core Imputations of Matching and b-Matching Games. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{vazirani:LIPIcs.FSTTCS.2022.28,
  author =	{Vazirani, Vijay V.},
  title =	{{New Characterizations of Core Imputations of Matching and b-Matching Games}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.28},
  URN =		{urn:nbn:de:0030-drops-174207},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.28},
  annote =	{Keywords: LP-duality theory, cooperative game theory, core of a game, assignment game, general graph matching game, bipartite b-matching game}
}
Document
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

Authors: Vijay V. Vazirani and Mihalis Yannakakis

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
In 1979, Hylland and Zeckhauser [Hylland and Zeckhauser, 1979] gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties - it is incentive compatible in the large and produces an allocation that is Pareto optimal - and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 2) An example that has only irrational equilibria, hence proving that this problem is not in PPAD. 3) A proof of membership of the problem in the class FIXP. 4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. We leave open the (difficult) questions of determining if computing an exact HZ equilibrium is FIXP-hard and an approximate HZ equilibrium is PPAD-hard.

Cite as

Vijay V. Vazirani and Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{vazirani_et_al:LIPIcs.ITCS.2021.59,
  author =	{Vazirani, Vijay V. and Yannakakis, Mihalis},
  title =	{{Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James 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.2021.59},
  URN =		{urn:nbn:de:0030-drops-135987},
  doi =		{10.4230/LIPIcs.ITCS.2021.59},
  annote =	{Keywords: Hyland-Zeckhauser scheme, one-sided matching markets, mechanism design, dichotomous utilities, PPAD, FIXP}
}
Document
Incentive Compatible Active Learning

Authors: Federico Echenique and Siddharth Prasad

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
We consider active learning under incentive compatibility constraints. The main application of our results is to economic experiments, in which a learner seeks to infer the parameters of a subject’s preferences: for example their attitudes towards risk, or their beliefs over uncertain events. By cleverly adapting the experimental design, one can save on the time spent by subjects in the laboratory, or maximize the information obtained from each subject in a given laboratory session; but the resulting adaptive design raises complications due to incentive compatibility. A subject in the lab may answer questions strategically, and not truthfully, so as to steer subsequent questions in a profitable direction. We analyze two standard economic problems: inference of preferences over risk from multiple price lists, and belief elicitation in experiments on choice over uncertainty. In the first setting, we tune a simple and fast learning algorithm to retain certain incentive compatibility properties. In the second setting, we provide an incentive compatible learning algorithm based on scoring rules with query complexity that differs from obvious methods of achieving fast learning rates only by subpolynomial factors. Thus, for these areas of application, incentive compatibility may be achieved without paying a large sample complexity price.

Cite as

Federico Echenique and Siddharth Prasad. Incentive Compatible Active Learning. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{echenique_et_al:LIPIcs.ITCS.2020.67,
  author =	{Echenique, Federico and Prasad, Siddharth},
  title =	{{Incentive Compatible Active Learning}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{67:1--67:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.67},
  URN =		{urn:nbn:de:0030-drops-117525},
  doi =		{10.4230/LIPIcs.ITCS.2020.67},
  annote =	{Keywords: Active Learning, Incentive Compatibility, Preference Elicitation}
}
  • Refine by Author
  • 2 Vazirani, Vijay V.
  • 1 Echenique, Federico
  • 1 Prasad, Siddharth
  • 1 Yannakakis, Mihalis

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Models of learning

  • Refine by Keyword
  • 1 Active Learning
  • 1 FIXP
  • 1 Hyland-Zeckhauser scheme
  • 1 Incentive Compatibility
  • 1 LP-duality theory
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021
  • 1 2022

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