Source author record

Natalie Collina

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computer Science and Game Theory Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates

We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically.

preprint2020arXiv

On the (in)-approximability of Bayesian Revenue Maximization for a Combinatorial Buyer

We consider a revenue-maximizing single seller with $m$ items for sale to a single buyer whose value $v(\cdot)$ for the items is drawn from a known distribution $D$ of support $k$ . A series of works by Cai et al. establishes that when each $v(\cdot)$ in the support of $D$ is additive or unit-demand (or $c$ -demand), the revenue-optimal auction can be found in $\operatorname{poly}(m,k)$ time. We show that going barely beyond this, even to matroid-based valuations (a proper subset of Gross Substitutes), results in strong hardness of approximation. Specifically, even on instances with $m$ items and $k \leq m$ valuations in the support of $D$ , it is not possible to achieve a $1/m^{1-\varepsilon}$ -approximation for any $\varepsilon>0$ to the revenue-optimal mechanism for matroid-based valuations in (randomized) poly-time unless NP $\subseteq$ RP (note that a $1/k$ -approximation is trivial). Cai et al.'s main technical contribution is a black-box reduction from revenue maximization for valuations in class $\mathcal{V}$ to optimizing the difference between two values in class $\mathcal{V}$ . Our main technical contribution is a black-box reduction in the other direction (for a wide class of valuation classes), establishing that their reduction is essentially tight.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.