3 Search Results for "Nikzad, Afshin"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.125
Unbalanced Random Matching Markets with Partial Preferences

Authors: Aditya Potukuchi and Shikha Singh

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Properties of stable matchings in the popular random-matching-market model have been studied for over 50 years. In a random matching market, each agent has complete preferences drawn uniformly and independently at random. Wilson (1972), Knuth (1976) and Pittel (1989) proved that in balanced random matching markets, the proposers are matched to their ln nth choice on average. In this paper, we consider competitive markets with n jobs and n+k candidates, and partial lists where each agent only ranks their top d choices. Despite the long history of the problem, the following fundamental question remains unanswered for these generalized markets: what is the tight threshold on list length d that results in a perfect stable matching with high probability? In this paper, we answer this question exactly - we prove a sharp threshold d₀ = ln n ⋅ ln (n+k)/(k+1) on the existence of perfect stable matchings when k = o(n). That is, we show that if d < (1-ε) d₀, then no stable matching matches all jobs; moreover, if d > (1+ ε) d₀, then all jobs are matched in every stable matching with high probability. This bound improves and generalizes recent results by Kanoria, Min and Qian (2021). Furthermore, we extend the line of work studying the effect of imbalance on the expected rank of the proposers (termed the "stark effect of competition"). We establish the regime in unbalanced markets that forces this stark effect to take shape in markets with partial preferences.
Cite as

Aditya Potukuchi and Shikha Singh. Unbalanced Random Matching Markets with Partial Preferences. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 125:1-125:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{potukuchi_et_al:LIPIcs.ICALP.2025.125,
  author =	{Potukuchi, Aditya and Singh, Shikha},
  title =	{{Unbalanced Random Matching Markets with Partial Preferences}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{125:1--125:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.125},
  URN =		{urn:nbn:de:0030-drops-235025},
  doi =		{10.4230/LIPIcs.ICALP.2025.125},
  annote =	{Keywords: stable matching, probabilistic method, Gale-Shapley algorithm}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.142
Reservation Exchange Markets for Internet Advertising

Authors: Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad, and Renato Paes-Leme

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Internet display advertising industry follows two main business models. One model is based on direct deals between publishers and advertisers where they sign legal contracts containing terms of fulfillment for a future inventory. The second model is a spot market based on auctioning page views in real-time on advertising exchange (AdX) platforms such as DoubleClick's Ad Exchange, RightMedia, or AppNexus. These exchanges play the role of intermediaries who sell items (e.g. page-views) on behalf of a seller (e.g. a publisher) to buyers (e.g., advertisers) on the opposite side of the market. The computational and economics issues arising in this second model have been extensively investigated in recent times. In this work, we consider a third emerging model called reservation exchange market. A reservation exchange is a two-sided market between buyer orders for blocks of advertisers' impressions and seller orders for blocks of publishers' page views. The goal is to match seller orders to buyer orders while providing the right incentives to both sides. In this work we first describe the important features of mechanisms for efficient reservation exchange markets. We then address the algorithmic problems of designing revenue sharing schemes to provide a fair division between sellers of the revenue collected from buyers. A major conceptual contribution of this work is in showing that even though both clinching ascending auctions and VCG mechanisms achieve the same outcome from a buyer perspective, however, from the perspective of revenue sharing among sellers, clinching ascending auctions are much more informative than VCG auctions.
Cite as

Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad, and Renato Paes-Leme. Reservation Exchange Markets for Internet Advertising. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 142:1-142:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{goel_et_al:LIPIcs.ICALP.2016.142,
  author =	{Goel, Gagan and Leonardi, Stefano and Mirrokni, Vahab and Nikzad, Afshin and Paes-Leme, Renato},
  title =	{{Reservation Exchange Markets for Internet Advertising}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{142:1--142:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.142},
  URN =		{urn:nbn:de:0030-drops-62863},
  doi =		{10.4230/LIPIcs.ICALP.2016.142},
  annote =	{Keywords: Reservation Markets, Internet Advertising, Two-sided Markets, Clinching Auction, Envy-free allocations}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.209
Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem

Authors: Takuro Fukunaga, Afshin Nikzad, and R. Ravi

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
The inventory routing problem involves trading off inventory holding costs at client locations with vehicle routing costs to deliver frequently from a single central depot to meet deterministic client demands over a finite planing horizon. In this paper, we consider periodic solutions that visit clients in one of several specified frequencies, and focus on the case when the frequencies of visiting nodes are nested. We give the first constant-factor approximation algorithms for designing optimum nested periodic schedules for the problem with no limit on vehicle capacities by simple reductions to prize-collecting network design problems. For instance, we present a 2.55-approximation algorithm for the minimum-cost nested periodic schedule where the vehicle routes are modeled as minimum Steiner trees. We also show a general reduction from the capacitated problem where all vehicles have the same capacity to the uncapacitated version with a slight loss in performance. This reduction gives a 4.55-approximation for the capacitated problem. In addition, we prove several structural results relating the values of optimal policies of various types.
Cite as

Takuro Fukunaga, Afshin Nikzad, and R. Ravi. Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 209-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{fukunaga_et_al:LIPIcs.APPROX-RANDOM.2014.209,
  author =	{Fukunaga, Takuro and Nikzad, Afshin and Ravi, R.},
  title =	{{Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{209--225},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.209},
  URN =		{urn:nbn:de:0030-drops-46985},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.209},
  annote =	{Keywords: Inventry Routing Problem, Approximation algorithm, Prize-collecting Steiner Tree}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2016
  • 1 2014

  • Refine by Author
  • 2 Nikzad, Afshin
  • 1 Fukunaga, Takuro
  • 1 Goel, Gagan
  • 1 Leonardi, Stefano
  • 1 Mirrokni, Vahab
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Clinching Auction
  • 1 Envy-free allocations
  • 1 Gale-Shapley algorithm
  • 1 Internet Advertising
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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