BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Eva Tardos

Eva Tardos contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryData Structures and AlgorithmsMachine Learningmath.OCmath.PRphysics.soc-phSocial and Information Networks

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

5 published item(s)

preprint2022arXiv

Dynamic Pricing Provides Robust Equilibria in Stochastic Ridesharing Networks

Ridesharing markets are complex: drivers are strategic, rider demand and driver availability are stochastic, and complex city-scale phenomena like weather induce large scale correlation across space and time. At the same time, past work has focused on a subset of these challenges. We propose a model of ridesharing networks with strategic drivers, spatiotemporal dynamics, and stochasticity. Supporting both computational tractability and better modeling flexibility than classical fluid limits, we use a two-level stochastic model that allows correlated shocks caused by weather or large public events. Using this model, we propose a novel pricing mechanism: stochastic spatiotemporal pricing (SSP). We show that the SSP mechanism is asymptotically incentive-compatible and that all (approximate) equilibria of the resulting game are asymptotically welfare-maximizing when the market is large enough. The SSP mechanism iteratively recomputes prices based on realized demand and supply, and in this sense prices dynamically. We show that this is critical: while a static variant of the SSP mechanism (whose prices vary with the market-level stochastic scenario but not individual rider and driver decisions) has a sequence of asymptotically welfare-optimal approximate equilibria, we demonstrate that it also has other equilibria producing extremely low social welfare. Thus, we argue that dynamic pricing is important for ensuring robustness in stochastic ride-sharing networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Adversarial Perturbations of Opinion Dynamics in Networks

We study the connections between network structure, opinion dynamics, and an adversary's power to artificially induce disagreements. We approach these questions by extending models of opinion formation in the social sciences to represent scenarios, familiar from recent events, in which external actors seek to destabilize communities through sophisticated information warfare tactics via fake news and bots. In many instances, the intrinsic goals of these efforts are not necessarily to shift the overall sentiment of the network, but rather to induce discord. These perturbations diffuse via opinion dynamics on the underlying network, through mechanisms that have been analyzed and abstracted through work in computer science and the social sciences. We investigate the properties of such attacks, considering optimal strategies both for the adversary seeking to create disagreement and for the entities tasked with defending the network from attack. We show that for different formulations of these types of objectives, different regimes of the spectral structure of the network will limit the adversary's capacity to sow discord; this enables us to qualitatively describe which networks are most vulnerable against these perturbations. We then consider the algorithmic task of a network defender to mitigate these sorts of adversarial attacks by insulating nodes heterogeneously; we show that, by considering the geometry of this problem, this optimization task can be efficiently solved via convex programming. Finally, we generalize these results to allow for two network structures, where the opinion dynamics process and the measurement of disagreement become uncoupled, and determine how the adversary's power changes; for instance, this may arise when opinion dynamics are controlled an online community via social media, while disagreement is measured along "real-world" connections.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Feedback graph regret bounds for Thompson Sampling and UCB

We study the stochastic multi-armed bandit problem with the graph-based feedback structure introduced by Mannor and Shamir. We analyze the performance of the two most prominent stochastic bandit algorithms, Thompson Sampling and Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that these algorithms achieve regret guarantees that combine the graph structure and the gaps between the means of the arm distributions. Surprisingly this holds despite the fact that these algorithms do not explicitly use the graph structure to select arms; they observe the additional feedback but do not explore based on it. Towards this result we introduce a "layering technique" highlighting the commonalities in the two algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Learning and Efficiency in Games with Dynamic Population

We study the quality of outcomes in repeated games when the population of players is dynamically changing and participants use learning algorithms to adapt to the changing environment. Game theory classically considers Nash equilibria of one-shot games, while in practice many games are played repeatedly, and in such games players often use algorithmic tools to learn to play in the given environment. Most previous work on learning in repeated games assumes that the population playing the game is static over time. We analyze the efficiency of repeated games in dynamically changing environments, motivated by application domains such as Internet ad-auctions and packet routing. We prove that, in many classes of games, if players choose their strategies in a way that guarantees low adaptive regret, then high social welfare is ensured, even under very frequent changes. In fact, in large markets learning players achieve asymptotically optimal social welfare despite high turnover. Previous work has only showed that high welfare is guaranteed for learning outcomes in static environments. Our work extends these results to more realistic settings when participation is drastically evolving over time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stability and Learning in Strategic Queuing Systems

Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research. In this paper, we study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get service will be resent at future rounds, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. We model this as an (infinitely) repeated game, where the system holds a state (number of packets held by each queue) that arises from the results of the previous round. We assume that routers satisfy the no-regret condition, e.g. they use learning strategies to identify the server where their packets get the best service. Classical work on repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent (beyond the influence on learning from past history). The carryover effect caused by packets remaining in this system makes learning in our context result in a highly dependent random process. We analyze this random process and find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, and queues use no-regret learning algorithms, then the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. This paper is the first to study the effect of selfish learning in a queuing system, where the learners compete for resources, but rounds are not all independent: the number of packets to be routed at each round depends on the success of the routers in the previous rounds.

0 citations0 reviewsNo code linkedOpen access