BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Vijay V. Vazirani

Vijay V. Vazirani appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryData Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsecon.THmath.COMachine Learningmath.DSmath.PRNetworking and Internet ArchitecturePopulations and Evolution

Catalog footprint

What is connected

21works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

21 published item(s)

preprint2026arXiv

Robust Stable Matchings: Dealing with Changes in Preferences

We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances $A$ and $B$ on the same set of agents, a matching is said to be robust if it is stable under both instances. This notion captures desirable robustness properties in matching markets where preferences may evolve, be misreported, or be subject to uncertainty. While the classical theory of stable matchings reveals rich lattice, algorithmic, and polyhedral structure for a single instance, it is unclear which of these properties persist when stability is required across multiple instances. Our work initiates a systematic study of the structural and computational behavior of robust stable matchings under increasingly general models of preference changes. We analyze robustness under a hierarchy of perturbation models: 1. a single upward shift in one agent's preference list, 2. an arbitrary permutation change by a single agent, and 3. arbitrary preference changes by multiple agents on both sides. For each regime, we characterize when: 1. the set of robust stable matchings forms a sublattice, 2. the lattice of robust stable matchings admits a succinct Birkhoff partial order enabling efficient enumeration, 3. worker-optimal and firm-optimal robust stable matchings can be computed efficiently, and 4. the robust stable matching polytope is integral (by studying its LP formulation). We provide explicit counterexamples demonstrating where these structural and geometric properties break down, and complement these results with XP-time algorithms running in $O(n^k)$ time, parameterized by $k$, the number of agents whose preferences change. Our results precisely delineate the boundary between tractable and intractable cases for robust stable matchings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications

Recently MV18 identified and initiated work on the new problem of understanding structural relationships between the lattices of solutions of two "nearby" instances of stable matching. They also gave an application of their work to finding a robust stable matching. However, the types of changes they allowed in going from instance $A$ to $B$ were very restricted, namely any one agent executes an upward shift. In this paper, we allow any one agent to permute its preference list arbitrarily. Let $M_A$ and $M_B$ be the sets of stable matchings of the resulting pair of instances $A$ and $B$, and let $\mathcal{L}_A$ and $\mathcal{L}_B$ be the corresponding lattices of stable matchings. We prove that the matchings in $M_A \cap M_B$ form a sublattice of both $\mathcal{L}_A$ and $\mathcal{L}_B$ and those in $M_A \setminus M_B$ form a join semi-sublattice of $\mathcal{L}_A$. These properties enable us to obtain a polynomial time algorithm for not only finding a stable matching in $M_A \cap M_B$, but also for obtaining the partial order, as promised by Birkhoff's Representation Theorem, thereby enabling us to generate all matchings in this sublattice. Our algorithm also helps solve a version of the robust stable matching problem. We discuss another potential application, namely obtaining new insights into the incentive compatibility properties of the Gale-Shapley Deferred Acceptance Algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

New Characterizations of Core Imputations of Matching and $b$-Matching Games

We give new characterizations of core imputations for the following games: * The assignment game. * Concurrent games, i.e., general graph matching games having non-empty core. * The unconstrained bipartite $b$-matching game (edges can be matched multiple times). * The constrained bipartite $b$-matching game (edges can be matched at most once). The classic paper of Shapley and Shubik \cite{Shapley1971assignment} showed that core imputations of the assignment game are precisely optimal solutions to the dual of the LP-relaxation of the game. Building on this, Deng et al. \cite{Deng1999algorithms} gave a general framework which yields analogous characterizations for several fundamental combinatorial games. Interestingly enough, their framework does not apply to the last two games stated above. In turn, we show that some of the core imputations of these games correspond to optimal dual solutions and others do not. This leads to the tantalizing question of understanding the origins of the latter. We also present new characterizations of the profits accrued by agents and teams in core imputations of the first two games. Our characterization for the first game is stronger than that for the second; the underlying reason is that the characterization of vertices of the Birkhoff polytope is stronger than that of the Balinski polytope.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings

In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G \subseteq K_{n,n}$ has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function $w$ on the edges of $K_{n,n}$, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph $G \subseteq K_{n,n}$ contains one of these minimum weight perfect matchings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

In 1979, Hylland and Zeckhauser \cite{hylland} gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalant and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1. A combinatorial, strongly polynomial time algorithm for the special case of $0/1$ utilities. 2. An example that has only irrational equilibria, hence proving that this problem is not in PPAD. Furthermore, its equilibria are disconnected, hence showing that the problem does not admit a convex programming formulation. 3. A proof of membership of the problem in the class FIXP. We leave open the (difficult) question of determining if the problem is FIXP-hard. Settling the status of the special case when utilities are in the set $\{0, {\frac 1 2}, 1 \}$ appears to be even more difficult.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R

This paper resolves two of the handful of remaining questions on the computability of market equilibria, a central theme within algorithmic game theory (AGT). Our results are as follows: 1. We show FIXP-hardness of computing equilibria in Arrow-Debreu markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets. We note that these are the first FIXP-hardness results ever since the introduction of the class FIXP and the hardness of 3-Nash established therein. 2. We note that for the problems stated above, the corresponding results showing membership in FIXP were established after imposing suitable sufficiency conditions to render the problems total, as is customary in economics. However, if all instances are under consideration, then in both cases we prove that the problem of deciding if a given instance admits an equilibrium is \Exists-R-complete, where \Exists-R is the class of decision problems which can be reduced in polynomial time to Existential Theory of the Reals. 3. For Arrow-Debreu markets under Leontief utility functions and a constant number of agents, we give a polynomial-time algorithm for computing an equilibrium. This settles part of an open problem of Devanur and Kannan (FOCS'08). We note that PLC utilities are about the most general utilities of interest in economics and several fundamental utility functions studied within AGT are special cases of it. Several important problems, which have been shown to be in FIXP, are waiting for proofs of FIXP-hardness. In this context, our technique of reducing from 3-Nash to Multivariate Polynomial Equations and then to the problem is likely to be useful in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\mathcal{R}_1$ and $\mathcal{R}_2$. In round $\mathcal{R}_1$, the capacity of each school is fixed and mechanism $\mathcal{M}_1$ finds a student optimal stable matching. In round $\mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round $\mathcal{R}_2$ under certain settings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Performance-Based Scheme for Pricing Resources in the Cloud

With the rapid growth of the cloud computing marketplace, the issue of pricing resources in the cloud has been the subject of much study in recent years. In this paper, we identify and study a new issue: how to price resources in the cloud so that the customer's risk is minimized, while at the same time ensuring that the provider accrues his fair share. We do this by correlating the revenue stream of the customer to the prices charged by the provider. We show that our mechanism is incentive compatible in that it is in the best interest of the customer to provide his true revenue as a function of the resources rented. We next add another restriction to the price function, i.e., that it be linear. This removes the distortion that creeps in when the customer has to pay more money for less resources. Our algorithms for both the schemes mentioned above are efficient.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convex Program Duality, Fisher Markets, and Nash Social Welfare

We study Fisher markets and the problem of maximizing the Nash social welfare (NSW), and show several closely related new results. In particular, we obtain: -- A new integer program for the NSW maximization problem whose fractional relaxation has a bounded integrality gap. In contrast, the natural integer program has an unbounded integrality gap. -- An improved, and tight, factor 2 analysis of the algorithm of [7]; in turn showing that the integrality gap of the above relaxation is at most 2. The approximation factor shown by [7] was $2e^{1/e} \approx 2.89$. -- A lower bound of $e^{1/e}\approx 1.44$ on the integrality gap of this relaxation. -- New convex programs for natural generalizations of linear Fisher markets and proofs that these markets admit rational equilibria. These results were obtained by establishing connections between previously known disparate results, and they help uncover their mathematical underpinnings. We show a formal connection between the convex programs of Eisenberg and Gale and that of Shmyrev, namely that their duals are equivalent up to a change of variables. Both programs capture equilibria of linear Fisher markets. By adding suitable constraints to Shmyrev's program, we obtain a convex program that captures equilibria of the spending-restricted market model defined by [7] in the context of the NSW maximization problem. Further, adding certain integral constraints to this program we get the integer program for the NSW mentioned above. The basic tool we use is convex programming duality. In the special case of convex programs with linear constraints (but convex objectives), we show a particularly simple way of obtaining dual programs, putting it almost at par with linear program duality. This simple way of finding duals has been used subsequently for many other applications.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Mutation, Sexual Reproduction and Survival in Dynamic Environments

A new approach to understanding evolution [Val09], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [CLPV14]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [WVA05], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Convex Programs for Fisher's Market Model and its Generalizations

We present the following results pertaining to Fisher's market model: -We give two natural generalizations of Fisher's market model: In model M_1, sellers can declare an upper bound on the money they wish to earn (and take back their unsold good), and in model M_2, buyers can declare an upper bound on the amount to utility they wish to derive (and take back the unused part of their money). -We derive convex programs for the linear case of these two models by generalizing a convex program due to Shmyrev and the Eisenberg-Gale program, respectively. -We generalize the Arrow-Hurwicz theorem to the linear case of these two models, hence deriving alternate convex programs. -For the special class of convex programs having convex objective functions and linear constraints, we derive a simple set of rules for constructing the dual program (as simple as obtaining the dual of an LP). Using these rules we show a formal relationship between the two seemingly different convex programs for linear Fisher markets, due to Eisenberg-Gale and Shmyrev; the duals of these are the same, upto a change of variables.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Learning Economic Parameters from Revealed Preferences

A recent line of work, starting with Beigman and Vohra (2006) and Zadimoghaddam and Roth (2012), has addressed the problem of {\em learning} a utility function from revealed preference data. The goal here is to make use of past data describing the purchases of a utility maximizing agent when faced with certain prices and budget constraints in order to produce a hypothesis function that can accurately forecast the {\em future} behavior of the agent. In this work we advance this line of work by providing sample complexity guarantees and efficient algorithms for a number of important classes. By drawing a connection to recent advances in multi-class learning, we provide a computationally efficient algorithm with tight sample complexity guarantees ($Θ(d/ε)$ for the case of $d$ goods) for learning linear utility functions under a linear price model. This solves an open question in Zadimoghaddam and Roth (2012). Our technique yields numerous generalizations including the ability to learn other well-studied classes of utility functions, to deal with a misspecified model, and with non-linear prices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Settling Some Open Problems on 2-Player Symmetric Nash Equilibria

Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowledge, the last remaining open problem of this sort is the following; it was stated by Papadimitriou in 2007: find a non-symmetric Nash equilibrium (NE) in a symmetric game. We show that this problem is NP-complete and the problem of counting the number of non-symmetric NE in a symmetric game is #P-complete. In 2005, Kannan and Theobald defined the "rank of a bimatrix game" represented by matrices (A, B) to be rank(A+B) and asked whether a NE can be computed in rank 1 games in polynomial time. Observe that the rank 0 case is precisely the zero sum case, for which a polynomial time algorithm follows from von Neumann's reduction of such games to linear programming. In 2011, Adsul et. al. obtained an algorithm for rank 1 games; however, it does not solve the case of symmetric rank 1 games. We resolve this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Computability of Equilibria in Markets with Production

Although production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. We first define the notion of separable, piecewise-linear concave (SPLC) production by analogy with SPLC utility functions. We then obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria for Arrow-Debreu markets with SPLC utilities and SPLC production, and we give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 of extending his complementary pivot algorithm to markets with production. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm runs fast on randomly chosen examples, and unlike previous approaches, it does not suffer from issues of numerical instability. Additionally, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Thrifty Algorithms for Multistage Robust Optimization

We consider a class of multi-stage robust covering problems, where additional information is revealed about the problem instance in each stage, but the cost of taking actions increases. The dilemma for the decision-maker is whether to wait for additional information and risk the inflation, or to take early actions to hedge against rising costs. We study the "k-robust" uncertainty model: in each stage i = 0, 1,...,T, the algorithm is shown some subset of size k_i that completely contains the eventual demands to be covered; here k_1 > k_2 >...> k_T which ensures increasing information over time. The goal is to minimize the cost incurred in the worst-case possible sequence of revelations. For the multistage k-robust set cover problem, we give an O(log m + log n)-approximation algorithm, nearly matching the Ω(log n + log m/loglog m) hardness of approximation even for T=2 stages. Moreover, our algorithm has a useful "thrifty" property: it takes actions on just two stages. We show similar thrifty algorithms for multi-stage k-robust Steiner tree, Steiner forest, and minimum-cut. For these problems our approximation guarantees are O(min{T, log n, log L_{max}), where L_{max} is the maximum inflation over all the stages. We conjecture that these problems also admit O(1)-approximate thrifty algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Market for Air Traffic Flow Management

The two somewhat conflicting requirements of efficiency and fairness make ATFM an unsatisfactorily solved problem, despite its overwhelming importance. In this paper, we present an economics motivated solution that is based on the notion of a free market. Our contention is that in fact the airlines themselves are the best judge of how to achieve efficiency and our market-based solution gives them the ability to pay, at the going rate, to buy away the desired amount of delay on a per flight basis. The issue of fairness is simply finessed away by our solution -- whoever pays gets smaller delays. We show how our solution has the potential of enabling travelers from a large spectrum of affordability and punctuality requirements to achieve an end that is most desirable to them. Our market model is particularly simple, requiring only one parameter per flight from the airline company. Furthermore, we show that it admits a combinatorial, strongly polynomial algorithm for computing an equilibrium landing schedule and prices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Modeling Tiered Pricing in the Internet Transit Market

ISPs are increasingly selling "tiered" contracts, which offer Internet connectivity to wholesale customers in bundles, at rates based on the cost of the links that the traffic in the bundle is traversing. Although providers have already begun to implement and deploy tiered pricing contracts, little is known about how such pricing affects ISPs and their customers. While contracts that sell connectivity on finer granularities improve market efficiency, they are also more costly for ISPs to implement and more difficult for customers to understand. In this work we present two contributions: (1) we develop a novel way of mapping traffic and topology data to a demand and cost model; and (2) we fit this model on three large real-world networks: an European transit ISP, a content distribution network, and an academic research network, and run counterfactuals to evaluate the effects of different pricing strategies on both the ISP profit and the consumer surplus. We highlight three core findings. First, ISPs gain most of the profits with only three or four pricing tiers and likely have little incentive to increase granularity of pricing even further. Second, we show that consumer surplus follows closely, if not precisely, the increases in ISP profit with more pricing tiers. Finally, the common ISP practice of structuring tiered contracts according to the cost of carrying the traffic flows (e.g., offering a discount for traffic that is local) can be suboptimal and that dividing contracts based on both traffic demand and the cost of carrying it into only three or four tiers yields near-optimal profit for the ISP.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Non-Separable, Quasiconcave Utilities are Easy -- in a Perfect Price Discrimination Market Model

Recent results, establishing evidence of intractability for such restrictive utility functions as additively separable, piecewise-linear and concave, under both Fisher and Arrow-Debreu market models, have prompted the question of whether we have failed to capture some essential elements of real markets, which seem to do a good job of finding prices that maintain parity between supply and demand. The main point of this paper is to show that even non-separable, quasiconcave utility functions can be handled efficiently in a suitably chosen, though natural, realistic and useful, market model; our model allows for perfect price discrimination. Our model supports unique equilibrium prices and, for the restriction to concave utilities, satisfies both welfare theorems.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game

Over the last decade, combinatorial algorithms have been obtained for exactly solving several nonlinear convex programs. We first provide a formal context to this activity by introducing the notion of {\em rational convex programs} -- this also enables us to identify a number of questions for further study. So far, such algorithms were obtained for total problems only. Our main contribution is developing the methodology for handling non-total problems, i.e., their associated convex programs may be infeasible for certain settings of the parameters. The specific problem we study pertains to a Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We reduce this game to computing an equilibrium in a new market model called {\em flexible budget market}, and we obtain primal-dual algorithms for determining feasibility, as well as giving a proof of infeasibility and finding an equilibrium. We give an application of our combinatorial algorithm for ADNB to an important "fair" throughput allocation problem on a wireless channel.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties

The solution to a Nash or a nonsymmetric bargaining game is obtained by maximizing a concave function over a convex set, i.e., it is the solution to a convex program. We show that each 2-player game whose convex program has linear constraints, admits a rational solution and such a solution can be found in polynomial time using only an LP solver. If in addition, the game is succinct, i.e., the coefficients in its convex program are ``small'', then its solution can be found in strongly polynomial time. We also give a non-succinct linear game whose solution can be found in strongly polynomial time.

0 citations0 reviewsNo code linkedOpen access