Atanas Dinev

dblp:336/0469 · DBLP profile ↗
← Back
3ranked-venue papers
2as first author
3since 2021 · last 2024
0009-0006-0342-2155ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 2 since 2021Artificial intelligence and machine learning · 1 · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2024 Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids
abstract
We provide a simple $(1-O(\frac{1}{\sqrt{k}}))$-selectable Online Contention Resolution Scheme for $k$-uniform matroids against a fixed-order adversary. If $A_i$ and $G_i$ denote the set of selected elements and the set of realized active elements among the first $i$ (respectively), our algorithm selects with probability $1-\frac{1}{\sqrt{k}}$ any active element $i$ such that $|A_{i-1}| + 1 \leq (1-\frac{1}{\sqrt{k}})\cdot \mathbb{E}[|G_i|]+\sqrt{k}$. This implies a $(1-O(\frac{1}{\sqrt{k}}))$ prophet inequality against fixed-order adversaries for $k$-uniform matroids that is considerably simpler than previous algorithms [Ala14, AKW14, JMZ22]. We also prove that no OCRS can be $(1-Ω(\sqrt{\frac{\log k}{k}}))$-selectable for $k$-uniform matroids against an almighty adversary. This guarantee is matched by the (known) simple greedy algorithm that accepts every active element with probability $1-Θ(\sqrt{\frac{\log k}{k}})$ [HKS07].
Atanas Dinev, S. Matthew Weinberg
ITCS1
2024 Social Learning with Bounded Rationality: Negative Reviews Persist under Newest First
abstract
The use of product reviews in online platforms is ubiquitous and it is well established that reviews play a significant role on customer purchase decisions. The process in which reviews impact product purchases can be seen as a problem of social learning, which generically studies how agents update their beliefs for an unknown quantity of interest (e.g., product quality) based on observing actions of past agents (e.g., reading reviews by past customers). The typical assumption in the literature of social learning with reviews is that, when deciding whether to purchase a product, customers consider either all reviews provided by previous customers or a summary statistic such as their average rating. However, in practice, a common scenario may be somewhere "in between" the above two assumptions: customers read a small number of reviews in detail.
Jackie Baek, Atanas Dinev, Thodoris Lykouris
EC2
2022 Tight Bounds on 3-Team Manipulations in Randomized Death Match
Atanas Dinev, S. Matthew Weinberg
WINE1