Explore the vast range of titles available.

We consider the problem of screening where a seller puts up for sale an indivisible good, and a buyer with a valuation unknown to the seller wishes to acquire the good. We assume that the buyer valuations are represented as discrete types drawn from some distribution, which is also unknown to the seller. The seller is averse to possible mis-specification of types distribution, and considers the unknown type density as member of an ambiguity set and seeks an optimal pricing mechanism in a worst case sense. We specify four choices for the ambiguity set and derive the optimal mechanism in each case.

This thesis consists of three parts focusing on three different problems. All of these problems have optimization at heart yet they are related to different branches of optimization. Our first problem is on the convergence rate of two moment based methods, Polyak's Heavy Ball and Nesterov's Accelerated Gradient, employing adaptive restart. We introduce two criteria and show that under such criteria these methods have linear convergence. Strongly convex functions satisfy these criteria hence the results are valid for such functions. To the best of our knowledge, our result is the first convergence result for the adaptive restart scheme. We then introduce a novel restarting criteria which are highly tunable and also satisfies linear convergence. Our second problem is on computation of the sparsest solution to an underdetermined system of linear equations. We introduce an extrapolation procedure which computes the sparsest solution from a penalized relaxation of the problem via Huber function. This extrapolation procedure uses a condition called sign constancy and we show that if one works with extreme points this can be removed. We present necessary and sufficient conditions for the recovery of the sparsest solution by penalized Huber loss function and ties among different solutions. Our last problem of concern is on Network flows. In this work in progress, we investigate existence and computation of the equilibrium in trade networks with constraints. To the best of our knowledge, these networks are only investigated under simple capacity constraints on each link. Here we first start with a negative result where we give a counterexample where the link capacities live in a polymatroid yet there is no integer equilibrium point in the feasible region. We then move on to investigate the cases where the constraints are less restrictive.

We introduce HUNTRESS, a computational method for mutational intratumor heterogeneity inference from noisy genotype matrices derived from single-cell sequencing data, the running time of which is linear with the number of cells and quadratic with the number of mutations. We prove that, under reasonable conditions, HUNTRESS computes the true progression history of a tumor with high probability. On simulated and real tumor sequencing data, HUNTRESS is demonstrated to be faster than available alternatives with comparable or better accuracy. Additionally, the progression histories of tumors inferred by HUNTRESS on real single-cell sequencing datasets agree with the best known evolution scenarios for the associated tumors.

It is well known that mirror descent may diverge or cycle on merely monotone variational inequalities. In this paper, we propose Target Mirror Descent (TMD), a unified framework that stabilizes monotone flows via a target point correction mechanism in the dual update. By appropriate design choices, TMD recovers the proximal point algorithm, extragradient methods, splitting methods, Brown-von Neumann-Nash dynamics, forward-backward-forward dynamics, and discounted mirror descent as special cases. Thus, we establish a unified perspective on these landmark algorithms and their convergence. Beyond unification, we leverage the TMD framework to correct an equilibrium misalignment in discounted mirror descent and to generalize its higher-order extension beyond interior solutions. Moreover, a key structural feature of TMD is the explicit decoupling of the mirror map from the target determination, which enables geometric ensembles: multiple algorithms solve the same problem in parallel using distinct mirror maps, while sharing a common dual update. We show that such an ensemble rigorously reduces to a single TMD with a synthesized mirror map, and thus inherits these convergence guarantees.

Advances in single-cell RNA sequencing (scRNAseq) technologies uncovered an unexpected complexity in tumors, underlining the relevance of intratumor heterogeneity to cancer progression and therapeutic resistance. Heterogeneity in the mutational composition of cancer cells is a result of distinct (sub)clonal expansions, each with a distinct metastatic potential and resistance to specific treatments. Unfortunately, due to their low read coverage per cell, scRNAseq datasets are too sparse and noisy to be used for detecting expressed mutations in single cells. Additionally, the large number of cells and mutations present in typical scRNAseq datasets are too large for available computational tools to, e.g., infer distinct subclones, lineages or trajectories in a tumor. Finally, there are no principled methods to assess distinct subclones inferred through single-cell sequencing data and the genomic alterations that seed and potentially cause them. Here we present Trisicell, a computational toolkit for scalable mutational intratumor heterogeneity inference and assessment from scRNAseq as well as single-cell genome or exome sequencing data. Trisicell allows reliable identification of distinct clonal lineages of a tumor, offering the ability to focus on the most important subclones and the genomic alterations that are associated with tumor proliferation. We comprehensively assessed Trisicell on a melanoma model by comparing distinct lineages and subclones it identifies on scRNAseq data, to those inferred using matching bulk whole exome (bWES) and transcriptome (bWTS) sequencing data from clonal sublines derived from single cells. Our results demonstrate that distinct lineages and subclones of a tumor can be reliably inferred and evaluated based on mutation calls from scRNAseq data through the use of Trisicell. Additionally, they reveal a strong correlation between aggressiveness and mutational composition, both across the inferred subclones, and among human melanomas. We also applied Trisicell to infer and evaluate distinct subclonal expansion patterns of the same mouse melanoma model after treatment with immune checkpoint blockade (ICB). After integratively analyzing our cell-specific mutation calls with their expression profiles, we observed that each subclone with a distinct set of novel somatic mutations is strongly associated with a specific developmental status. Moreover, each subclone had developed a unique ICB-resistance mechanism. These results demonstrate that Trisicell can robustly utilize scRNAseq data to delineate intratumor heterogeneity and help understand biological mechanisms underlying tumor progression and resistance to therapy.

We leverage best response dynamics to solve monotone variational inequalities on compact and convex sets. Specialization of the method to variational inequalities in game theory recovers convergence results to Nash equilibria when agents select the best response to the current distribution of strategies. We apply the method to generalize population games with additional convex constraints. Furthermore, we explore the robustness of the method by introducing various types of time-varying disturbances.

The Braess paradox is a counter-intuitive phenomenon whereby adding roads to a network results in higher travel time at equilibrium. In this paper we present an algorithm to detect the occurrence of this paradox in real-world networks with the help of an improved graph representation accounting for queues. The addition of queues to the network representation enables a closer match with real data. Moreover, we search for routes causing this phenomenon (\"Braess routes\") rather than links, and advocate removing such routes virtually from navigation systems so that the associated links can continue to serve other routes. Our algorithm relies on a convex optimization problem utilizing Beckmann potentials for road links as well as queues, and results in a route reconfiguration with reduced delay. We assume the availability of historical data to build the optimization model. We also assume the existence of a centralized navigation system to manage the routing options and remove the Braess routes. The theoretical solution demonstrates up to 12% delay reduction in a network from Montgomery County, Maryland. We validate the improvement with simulations.

Trades based on bilateral (indivisible) contracts can be represented by a network. Vertices correspond to agents while arcs represent the non-price elements of a bilateral contract. Given prices for each arc, agents choose the incident arcs that maximize their utility. We enlarge the model to allow for polymatroidal constraints on the set of contracts that may be traded which can be interpreted as modeling limited one for-one substitution. We show that for two-sided markets there exists a competitive equilibrium however for multi-sided markets this may not be possible.

Trades based on bilateral (indivisible) contracts can be represented by a network. Vertices correspond to agents while arcs represent the non-price elements of a bilateral contract. Given prices for each arc, agents choose the incident arcs that maximize their utility. We enlarge the model to allow for polymatroidal constraints on the set of contracts that may be traded which can be interpreted as modeling limited one for-one substitution. We show that for two-sided markets there exists a competitive equilibrium however for multi-sided markets this may not be possible.

Growing EV adoption can worsen traffic conditions if chargers are sited without regard to their impact on congestion. We study how to strategically place EV chargers to reduce congestion using two equilibrium models: one based on congestion games and one based on an atomic queueing simulation. We apply both models within a scalable greedy station-placement algorithm. Experiments show that this greedy scheme yields optimal or near-optimal congestion outcomes in realistic networks, even though global optimality is not guaranteed as we show with a counterexample. We also show that the queueing-based approach yields more realistic results than the congestion-game model, and we present a unified methodology that calibrates congestion delays from queue simulation and solves equilibrium in link-space.