Search Results

Documents authored by Moscardelli, Luca

Document
DOI: 10.4230/LIPIcs.MFCS.2018.47
Pricing Problems with Buyer Preselection

Authors: Vittorio Bilò, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We investigate the problem of preselecting a subset of buyers participating in a market so as to optimize the performance of stable outcomes. We consider four scenarios arising from the combination of two stability notions, item and bundle envy-freeness, with the two classical objective functions, i.e., the social welfare and the seller's revenue. When adopting the notion of item envy-freeness, we prove that, for both the two objective functions, the problem cannot be approximated within n^(1-epsilon) for any epsilon >0, and provide tight or nearly tight approximation algorithms. We also prove that maximizing the seller's revenue is NP-hard even for a single buyer, thus closing an open question. Under bundle envy-freeness, instead, we show how to transform in polynomial time any stable outcome for a market involving only a subset of buyers to a stable one for the whole market without worsening its performance, both for the social welfare and the seller's revenue. Finally, we consider multi-unit markets, where all items are of the same type and are assigned the same price. For this specific case, we show that buyer preselection can improve the performance of stable outcomes in all of the four considered scenarios, and we design corresponding approximation algorithms.
Cite as

Vittorio Bilò, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. Pricing Problems with Buyer Preselection. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.MFCS.2018.47,
  author =	{Bil\`{o}, Vittorio and Flammini, Michele and Monaco, Gianpiero and Moscardelli, Luca},
  title =	{{Pricing Problems with Buyer Preselection}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.47},
  URN =		{urn:nbn:de:0030-drops-96292},
  doi =		{10.4230/LIPIcs.MFCS.2018.47},
  annote =	{Keywords: Pricing problems, Envy-freeness, Revenue maximization, Social Welfare maximization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.146
Uniform Mixed Equilibria in Network Congestion Games with Link Failures

Authors: Vittorio Bilò, Luca Moscardelli, and Cosimo Vinci

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Motivated by possible applications in fault-tolerant routing, we introduce the notion of uniform mixed equilibria in network congestion games with adversarial link failures, where players need to route traffic from a source to a destination node. Given an integer rho >= 1, a rho-uniform mixed strategy is a mixed strategy in which a player plays exactly rho edge disjoint paths with uniform probabilities, so that a rho-uniform mixed equilibrium is a tuple of rho-uniform mixed strategies, one for each player, in which no player can lower her cost by deviating to another rho-uniform mixed strategy. For games with weighted players and affine latency functions, we show existence of rho-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted players, instead, we extend the existential guarantee to any class of latency functions and, restricted to games with affine latencies, we derive a tight characterization of both the prices of anarchy and stability.
Cite as

Vittorio Bilò, Luca Moscardelli, and Cosimo Vinci. Uniform Mixed Equilibria in Network Congestion Games with Link Failures. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 146:1-146:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ICALP.2018.146,
  author =	{Bil\`{o}, Vittorio and Moscardelli, Luca and Vinci, Cosimo},
  title =	{{Uniform Mixed Equilibria in Network Congestion Games with Link Failures}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{146:1--146:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.146},
  URN =		{urn:nbn:de:0030-drops-91508},
  doi =		{10.4230/LIPIcs.ICALP.2018.146},
  annote =	{Keywords: Network Congestion Games, Fault-Tolerant Routing, Nash Equilibria, Price of Anarchy, Price of Stability}
}
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 About DROPS Imprint Privacy Contact