A canonical setting for non-monetary online resource allocation is one where agents compete over multiple rounds for a single item per round, with i.i.d. valuations and additive utilities across rounds. With $n$ symmetric agents, a natural benchmark for each agent is the utility realized by her favorite $1/n$-fraction of rounds; a line of work has demonstrated one can robustly guarantee each agent a constant fraction of this ideal utility, irrespective of how other agents behave. In particular, several mechanisms have been shown to be $1/2$-robust, and recent work established that repeated first-price auctions based on artificial credits have a robustness factor of $0.59$, which cannot be improved beyond $0.6$ using first-price and simple strategies. In contrast, even without strategic considerations, the best achievable factor is $1-1/e\approx 0.63$. In this work, we break the $0.6$ first-price barrier to get a new $0.625$-robust mechanism, which almost closes the gap to the non-strategic robustness bound. Surprisingly, we do so via a simple auction, where in each round, bidders decide if they ask for the item, and we allocate uniformly at random among those who ask. The main new ingredient is the idea of competitive subsidies, wherein we charge the winning agent an amount in artificial credits that decreases when fewer agents are bidding (specifically, when $k$ agents bid, then the winner pays proportional to $k/(k+1)$, varying the payment by a factor of 2 depending on the competition). Moreover, we show how it can be modified to get an equilibrium strategy with a slightly weaker robust guarantee of $5/(3e) \approx 0.61$ (and the optimal $1-1/e$ factor at equilibrium). Finally, we show that our mechanism gives the best possible bound under a wide class of auction-based mechanisms.

We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: (\(i\)) (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and (\(ii\)) simple distribution-agnostic mechanisms with robust utility guarantees for each individual agent, which are worse than the Nash outcome, but hold irrespective of how others behave (including possibly collusive behavior). Recent work has hinted at barriers to achieving both simultaneously. Our work however establishes this is not the case, by proposing the first mechanism in which each agent has a natural strategy that is both a Bayes-Nash equilibrium and also comes with strong robust guarantees for individual agent utilities. Our mechanism comes out of a surprising connection between the online shared resource allocation problem and implementation theory, and uses a surprising strengthening of Border’s theorem. In particular, we show that establishing robust equilibria in this setting reduces to showing that a particular subset of the Border polytope is non-empty. We establish this via a novel joint Schurconvexity argument. This strengthening of Border’s criterion for obtaining a stronger conclusion is of independent technical interest, as it may prove useful in other settings.

We study the problem of fair online resource allocation via non-monetary mechanisms, where multiple agents repeatedly share a resource without monetary transfers. Previous work has shown that every agent can guarantee 1/2 of their ideal utility (the highest achievable utility given their fair share of resources) robustly, i.e., under arbitrary behavior by the other agents. While this 1/2-robustness guarantee has now been established under very different mechanisms, including pseudo-markets and dynamic max-min allocation, improving on it has appeared difficult. In this work, we obtain the first significant improvement on the robustness of online resource sharing. In more detail, we consider the widely-studied repeated first-price auction with artificial currencies. Our main contribution is to show that a simple randomized bidding strategy can guarantee each agent a 2 - √2 ≈ 0.59 fraction of her ideal utility, irrespective of others' bids. Specifically, our strategy requires each agent with fair share α to use a uniformly distributed bid whenever her value is in the top α-quantile of her value distribution. Our work almost closes the gap to the known 1 - 1/e ≈ 0.63 hardness for robust resource sharing; we also show that any static (i.e., budget independent) bidding policy cannot guarantee more than a 0.6-fraction of the ideal utility, showing our technique is almost tight.

We analyze the performance of heterogeneous learning agents in asset markets with stochastic payoffs. Agents aim to maximize the expected growth rate of their wealth but have different theories on how to learn to do this best. Our main focus is on comparing Bayesian learners and no-regret learners who compete in markets and identifying the conditions under which each approach is more effective. Bayesian learners with a finite prior that assigns positive probability to the correct model have posterior beliefs that converge exponentially fast, and such agents survive even in the presence of agents who invest according to the correct model. Bayesian learners with a continuum prior converge at a slower rate of O((logT)/T).

We consider the classical Dynamic Max-min fair (DMMF) mechanism for allocating an indivisible resource without money over multiple agents and T rounds. We show that under mild assumption on value distributions, it guarantees every agent close to optimal utility in large markets.

In this paper, we introduce a novel approach to repeated auctions that accounts for bidders' temporal preferences, important in applications such as advertising. In our model, when a player wins an auction after not winning for ℓ rounds, she is awarded r(ℓ) utility and her goal is to maximize her total utility. r : ℕ → ℝ ≥0 satisfies the following properties. (i) The more rounds without a win, the higher the reward, i.e., r is weakly increasing. (ii) As more rounds pass without winning, the increase in reward becomes smaller, i.e., r is concave. The motivation behind these properties comes from the advertising literature, which states that an increased frequency of winning builds advertising effectiveness at a decreasing (but not declining) rate. The above properties guarantee that adding more wins to any sequence of winning intervals increases the total reward.

A fundamental component in the growing theoretical literature on school choice is the problem a student faces in deciding which schools to apply to. Recent models have considered a setting with a set of schools of different selectiveness, and a student who is unsure of their strength as an applicant and can apply to at most k schools [Ali and Shorrer, 2023]. Such models assume that the student cares solely about maximizing the quality of the school that they will attend. However, experience suggests that students' decisions are additionally influenced by a set of crucial behavioral biases based on reputational effects: they experience a subjective reputational benefit when they are admitted to a selective school, whether or not they attend; and a subjective loss based on disappointment when they are rejected. Guided by these observations, and inspired by recent behavioral economics work on loss aversion relative to expectations [Dreyfuss et al., 2022, Kőszegi and Rabin, 2006, 2007, 2009, Meisner and von Wangenheim, 2023], we propose a behavioral model by which a student chooses schools in a way that balances these subjective behavioral effects with the quality of the school they eventually attend.

Bandits with Knapsacks (BwK), the generalization of the Multi-Armed Bandits problem under global budget constraints, has received a lot of attention in recent years. It has numerous applications, including dynamic pricing, repeated auctions, ad allocation, network scheduling, etc. Previous work has focused on one of the two extremes: Stochastic BwK where the rewards and consumptions of the resources of each round are sampled from an i.i.d. distribution, and Adversarial BwK where these parameters are picked by an adversary. Achievable guarantees in the two cases exhibit a massive gap: No-regret learning is achievable in the stochastic case, but in the adversarial case only competitive ratio style guarantees are achievable, where the competitive ratio depends either on the budget or on both the time and the number of resources. What makes this gap so vast is that in Adversarial BwK the guarantees get worse in the typical case when the budget is more binding. While “best-of-both-worlds” type algorithms are known (single algorithms that provide the best achievable guarantee in each extreme case), their bounds degrade to the adversarial case as soon as the environment is not fully stochastic.Our work aims to bridge this gap, offering guarantees for a workload that is not exactly stochastic but is also not worst-case. We define a condition, Approximately Stationary BwK, that parameterizes how close to stochastic or adversarial an instance is. Based on these parameters, we explore what is the best competitive ratio attainable in BwL. We explore two algorithms that are oblivious to the values of the parameters but guarantee competitive ratios that smoothly transition between the best possible guarantees in the two extreme cases, depending on the values of the parameters. Our guarantees offer great improvement over the adversarial guarantee, especially when the available budget is small. We also prove bounds on the achievable guarantee, showing that our results are approximately tight when the budget is small.

We study non-monetary mechanisms for the fair and efficient allocation of reusable public resources. We consider settings where a limited resource is repeatedly shared among a set of agents, each of whom may request to use the resource over multiple consecutive rounds, receiving some utility only if they get to use the resource for the full duration of their request. Such settings are of particular significance in scientific research where large-scale instruments such as electron microscopes, particle colliders, or telescopes are shared between multiple research groups; this model also subsumes and extends existing models of repeated non-monetary allocation where the resource is demanded only for a single round.

We study the liquid welfare in sequential first-price auctions with budget-limited buyers. We focus on first-price auctions, which are increasingly commonly used in many settings, and consider liquid welfare, a natural and well-studied generalization of social welfare for the case of budget-constrained buyers. We use a behavioral model for the buyers, assuming a learning style guarantee: the resulting utility of each buyer is within a γ factor (where γ ≥ 1) of the utility achievable by shading her value with the same factor at each iteration. Under this assumption, we show a γ + 1/2 + O(1/γ) price of anarchy for liquid welfare assuming buyers have additive valuations. This positive result is in stark contrast to sequential second-price auctions, where even with γ = 1, the resulting liquid welfare can be arbitrarily smaller than the maximum liquid welfare, even though the latter can be achieved by a constant shading factor. We prove a lower bound of γ on the liquid welfare loss under the above assumption in first-price auctions, making our bound asymptotically tight. For the case when γ = 1 our theorem implies a price of anarchy upper bound that is about 2.41; we show a lower bound of 2 for that case.

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 algorithmic game theory. Classical work on such bounds in repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent beyond any influence on play from past history. This work studies such bounds in environments that themselves change due to the actions of the agents. Concretely, we consider this problem in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet at each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies. We analyze this queuing system from multiple perspectives. As a baseline measure, we first establish precise conditions on the queuing arrival rates and service capacities that ensure all packets clear efficiently under centralized coordination. We then show that if queues strategically choose servers according to independent and stationary distributions, the system remains stable provided it would be stable under coordination with arrival rates scaled up by a factor of just \(\frac{e}{e-1}\) . Finally, we extend these results to no-regret learning dynamics: if queues use learning algorithms satisfying the no-regret property to choose servers, then the requisite factor increases to 2, and both of these bounds are tight. Both of these results require new probabilistic techniques compared to the classical price of anarchy literature and show that in such settings, no-regret learning can exhibit efficiency loss due to myopia.

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.

No abstract available.

No abstract available.

We study the outcome in a matching market where both sides have limited ability to consider options. For example, in the national residency matching program, doctors are limited to apply to a small set of hospitals, and hospitals are limited by the time required to interview candidates. Our main findings are the following: (1) In markets where jobs can only consider a limited number of candidates for interview, it increases the size of the resulting matching if the system has a limit on the number of applications a candidate can send. (2) The fair system of all applicants being allowed to apply to the exact same number of positions maximizes the expected size of the matching. More particularly, starting from an integer k as the number of applications, the matching size decreases as a few applicants are allowed to apply to one additional position (and then increases again as they are all allowed to apply to k+1). Although it seems natural to expect that the size of the matching would be a monotone increasing and concave function in the number of applications, our results show that neither is true. These results hold even in a market where a-priori all jobs and all candidates are equally likely to be good, and the judgments of different employers and candidates are independent. Our main technical contribution is computing the expected size of the matching found via the deferred acceptance algorithm as a function of the number of interviews and applications in a market where preferences are uniform and independent. Through simulations we confirm that these findings extend to markets where rankings become correlated after the interviews.

In light of increasing recent attention to political polarization, understanding how polarization can arise poses an important theoretical question. While more classical models of opinion dynamics seem poorly equipped to study this phenomenon, a recent novel approach by H\ka zł a, Jin, Mossel, and Ramnarayan (HJMR) proposes a simple geometric model of opinion evolution that provably exhibits strong polarization in specialized cases. Moreover, polarization arises quite organically in their model: in each time step, each agent updates opinions according to their correlation/response with an issue drawn at random. However, their techniques do not seem to extend beyond a set of special cases they identify, which benefit from fragile symmetry or contractiveness assumptions, leaving open how general this phenomenon really is.

We consider the problem of selfish agents in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies, resulting in a highly dependent random process. In classical work for learning in repeated games, the learners evaluate the outcome of their strategy in each step---in our context, this means that queues estimate their success probability at each server. Earlier work by the authors [in EC'20] shows that with no-regret learners, the system needs twice the capacity as would be required in the coordinated setting to ensure queue lengths remain stable despite the selfish behavior of the queues. In this paper, we demonstrate that this myopic way of evaluating outcomes is suboptimal: if more patient queues choose strategies that selfishly maximize their long-run success rate, stability can be ensured with just e/e-1 ~1.58 times extra capacity, strictly better than what is possible assuming the no-regret property.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

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.

In this paper, 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 mathematical social sciences to represent scenarios, familiar from recent events, in which external actors have sought 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 towards a particular policy, but rather to induce discord. These perturbations will 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. Here 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. By employing spectral techniques, 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; in fact, somewhat surprisingly, the entire spectrum can be relevant, rather than just the extreme eigenvectors. Via the strong connections between spectral and structural properties of graphs, we are able to qualitatively describe which networks are most vulnerable or resilient 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; for instance, this may arise when opinion dynamics are controlled by an online community via social media, while disagreement is measured along "real-world" connections. We characterize conditions on the relationship between these two graphs that will determine how much power the adversary gains when this occurs.

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 algorithmic game theory. 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 rounds. 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.

No abstract available.

No abstract available.

No abstract available.

We consider the problem of adversarial (non-stochastic) online learning with partial information feedback, where at each round, a decision maker selects an action from a finite set of alternatives. We develop a black-box approach for such problems where the learner observes as feedback only losses of a subset of the actions that includes the selected action. When losses of actions are non-negative, under the graph-based feedback model introduced by Mannor and Shamir, we offer algorithms that attain the so called “small-loss” $o(\alpha L^{\star})$ regret bounds with high probability, where $\alpha$ is the independence number of the graph, and $L^{\star}$ is the loss of the best action. Prior to our work, there was no data-dependent guarantee for general feedback graphs even for pseudo-regret (without dependence on the number of actions, i.e. utilizing the increased information feedback). Taking advantage of the black-box nature of our technique, we extend our results to many other applications such as semi-bandits (including routing in networks), contextual bandits (even with an infinite comparator class), as well as learning with slowly changing (shifting) comparators. In the special case of classical bandit and semi-bandit problems, we provide optimal small-loss, high-probability guarantees of $\tilde{O}(\sqrt{dL^{\star}})$ for actual regret, where $d$ is the number of actions, answering open questions of Neu. Previous bounds for bandits and semi-bandits were known only for pseudo-regret and only in expectation. We also offer an optimal $\tilde{O}(\sqrt{\kappa L^{\star}})$ regret guarantee for fixed feedback graphs with clique-partition number at most $\kappa$.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

Market equilibria of matching markets offer an intuitive and fair solution for matching problems without money with agents who have preferences over the items. Such a matching market can be viewed as a variation of Fisher market, albeit with rather peculiar preferences of agents. These preferences can be described by piece-wise linear concave (PLC) functions, which however, are not separable (due to each agent only asking for one item), are not monotone, and do not satisfy the gross substitute property-- increase in price of an item can result in increased demand for the item. Devanur and Kannan in FOCS 08 showed that market clearing prices can be found in polynomial time in markets with fixed number of items and general PLC preferences. They also consider Fischer markets with fixed number of agents (instead of fixed number of items), and give a polynomial time algorithm for this case if preferences are separable functions of the items, in addition to being PLC functions.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings. We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees for the equilibria of many widely-used auction formats.

We show that learning algorithms satisfying a low approximate regret property experience fast convergence to approximate optimality in a large class of repeated games. Our property, which simply requires that each learner has small regret compared to a (1+eps)-multiplicative approximation to the best action in hindsight, is ubiquitous among learning algorithms; it is satisfied even by the vanilla Hedge forecaster. Our results improve upon recent work of Syrgkanis et al. in a number of ways. We require only that players observe payoffs under other players' realized actions, as opposed to expected payoffs. We further show that convergence occurs with high probability, and show convergence under bandit feedback. Finally, we improve upon the speed of convergence by a factor of n, the number of players. Both the scope of settings and the class of algorithms for which our analysis provides fast convergence are considerably broader than in previous work. Our framework applies to dynamic population games via a low approximate regret property for shifting experts. Here we strengthen the results of Lykouris et al. in two ways: We allow players to select learning algorithms from a larger class, which includes a minor variant of the basic Hedge algorithm, and we increase the maximum churn in players for which approximate optimality is achieved. In the bandit setting we present a new algorithm which provides a "small loss"-type bound with improved dependence on the number of actions in utility settings, and is both simple and efficient. This result may be of independent interest.

We study the quality of outcomes in repeated games when the population of players is dynamically changing, and where participants use learning algorithms to adapt to the dynamic environment. Price of anarchy has originally been introduced to study the Nash equilibria of one-shot games. Many games studied in computer science, such as packet routing or ad-auctions, are played repeatedly. Given the computational hardness of Nash equilibria, an attractive alternative in repeated game settings is that players use no-regret learning algorithms. The price of total anarchy considers the quality of such learning outcomes, assuming a steady environment and player population, which is rarely the case in online settings. In this paper we analyze efficiency of repeated games in dynamically changing environments. An important trait of learning behavior is its versatility to changing environments, assuming that the learning method used is adaptive, i.e., doesn't rely too heavily on experience from the distant past. We show that, in large classes of games, if players choose their strategies in a way that guarantees low adaptive regret, high social welfare is ensured, even under very frequent changes. A main technical tool for our analysis is the existence of a solution to the welfare maximization problem that is both close to optimal and relatively stable over time. Such a solution serves as a benchmark in the efficiency analysis of learning outcomes. We show that such a stable and close to optimal solution exists for many problems, even in cases when the exact optimal solution can be very unstable. We further show that a sufficient condition on the existence of stable outcomes is the existence of a differentially private algorithm for the welfare maximization problem. Hence, we draw a strong connection between differential privacy and high efficiency of learning outcomes in frequently changing repeated games. We demonstrate our techniques by focusing on two classes of games as examples: independent item auctions and congestion games. In both applications we show that adaptive learning guarantees high social welfare even with surprisingly high churn in the player population.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

Recent price-of-anarchy analyses of games of complete information suggest that coarse correlated equilibria, which characterize outcomes resulting from no-regret learning dynamics, have near-optimal welfare. This work provides two main technical results that lift this conclusion to games of incomplete information, a.k.a., Bayesian games. First, near-optimal welfare in Bayesian games follows directly from the smoothness-based proof of near-optimal welfare in the same game when the private information is public. Second, no-regret learning dynamics converge to Bayesian coarse correlated equilibrium in these incomplete information games. These results are enabled by interpretation of a Bayesian game as a stochastic game of complete information.

Many algorithms, that are originally designed without explicitly considering incentive properties, are later combined with simple pricing rules and used as mechanisms. The resulting mechanisms are often natural and simple to understand. But how good are these algorithms as mechanisms? Truthful reporting of valuations is typically not a dominant strategy (certainly not with a pay-your-bid, first-price rule, but it is likely not a good strategy even with a critical value, or second-price style rule either). Our goal is to show that a wide class of approximation algorithms yields this way mechanisms with low Price of Anarchy. The seminal result of Lucier and Borodin [2010] shows that combining a greedy algorithm that is an α-approximation algorithm with a pay-your-bid payment rule yields a mechanism whose Price of Anarchy is O(α). In this paper we significantly extend the class of algorithms for which such a result is available by showing that this close connection between approximation ratio on the one hand and Price of Anarchy on the other also holds for the design principle of relaxation and rounding provided that the relaxation is smooth and the rounding is oblivious.

Using renewable energy in an efficient way is a key challenge facing our society. In this paper we study online mechanisms motivated by markets for such renewable energy, such as wind energy. While the aggregate demand of the large populations served by energy providers is quite predictable, supply in such systems is rather uncertain; e.g. it depends on the strength of the wind at the wind turbines. Energy, when it is available, must be delivered immediately, due to the inefficiency of technologies for electric power storage, hence the supply is perishable. We model this scenario with an online market where supply is unknown, but participants know their own demand, and bid for energy at the beginning of the period. Items arrive online and are perishable, meaning that they have to be allocated to bidders immediately after arrival. This setup have been used for modeling renewable energy markets by earlier works, such as Tan and Varaiya (1993). We perform a price-of-anarchy analysis for a simple greedy allocation scheme, and compare efficiency of equilibria and learning outcomes to the socially optimal offline allocation. Due to the uncertainty, traditional dominant-strategy truthfulness cannot be achieved except by trivial mechanisms, which makes simple allocation mechanisms, such as the greedy, an appealing alternative. We show that simple first-price or second-price auctions combined with a greedy allocation rule ensure that equilibria closely approximate the optimum, assuming that bidders' preferences are non-increasing over time and additive within their demand, and demand is captured by a cardinality or matroid constraint. The results are of interest not only due to the application to energy markets, but also as they provide the first successful bounds on the price of anarchy of mechanisms in any online setting, while for the classical sequential auction setting Paes Leme et al. (2012) show that the price of anarchy is prohibitively high even with very simple bidder utilities. In more detail, we prove that equilibria and learning outcomes ensure at least half of the optimal welfare in case of the first-price rule with cardinality constraints, matching the approximation bound for the greedy algorithm. For second-price and more general matroid constraints, we show weaker guarantees. All results also extend to the Bayesian setting, where player values are random: bidder know their own future demand, but the competition is uncertain as is the supply, and all values may be correlated.

The main goal of this paper is to develop a theory of inference of player valuations from observed data in the generalized second price auction without relying on the Nash equilibrium assumption. Existing work in Economics on inferring agent values from data relies on the assumption that all participant strategies are best responses of the observed play of other players, i.e. they constitute a Nash equilibrium. In this paper, we show how to perform inference relying on a weaker assumption instead: assuming that players are using some form of no-regret learning. Learning outcomes emerged in recent years as an attractive alternative to Nash equilibrium in analyzing game outcomes, modeling players who haven't reached a stable equilibrium, but rather use algorithmic learning, aiming to learn the best way to play from previous observations. In this paper we show how to infer values of players who use algorithmic learning strategies. Such inference is an important first step before we move to testing any learning theoretic behavioral model on auction data. We apply our techniques to a dataset from Microsoft's sponsored search ad auction system.

We consider common-value hybrid auctions among two asymmetrically informed bidders, where the winning bidder pays his bid with some positive probability k and the losing bid otherwise. Under the assumption of discrete and affiliated signals, we give an explicit characterization of the (unique) equilibrium, based on a simple recurrence relation, which gives rise to a linear-time algorithm for explicitly computing the equilibrium. By analyzing the execution of the algorithm, we derive several insights about the equilibrium structure. First, we show that equilibrium revenue is decreasing in k, and that the limit second-price equilibrium selected as k->0 has highest revenue, in stark contrast to the revenue collapse of the second-price auction predicted by the trembling-hand equilibrium selection of Abraham et al. We further show that the Linkage Principle can fail to hold even in a pure first-price auction with binary signals: public revelation of a signal to both bidders may decrease the auctioneer's revenue. Lastly, we analyze the effects of public acquisition of additional information on bidder utilities and exhibit cases in which both bidders strictly prefer for a specific bidder to receive additional information.

The existence of a unique equilibrium is the classic tool for ensuring predictiveness of game theory. Typical uniqueness results, however, are for Nash and Bayes-Nash equilibria and do not guarantee that natural game playing dynamic converges to this equilibrium. In fact, there are well known examples in which the equilibrium is unique, yet natural learning behavior does not converge to it. Motivated by this, we strive for stronger uniqueness results. We do not only require that there is a unique equilibrium, but also that this equilibrium must be learnable. We adopt correlated equilibrium as our solution concept, as simple and natural learning algorithms guarantee that the empirical distribution of play converges to the space of correlated equilibria. Our main result is to show uniqueness of correlated equilibria in a large class of single-parameter mechanisms with matroid structure. We also show that our uniqueness result extends to problems with polymatroid structure under some conditions. Our model includes a number of special cases interesting on their own right, such as procurement auctions and Bertrand competitions. An interesting feature of our model is that we do not need to assume that the players have quasi-linear utilities, and hence can incorporate models with risk averse players and certain forms of externalities.

We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome both in equilibrium and in learning outcomes in the full information setting, as well as in Bayesian equilibrium with uncertainty about participants. Our main result is to show that smooth mechanisms compose well: smoothness locally at each mechanism implies global efficiency.

Typical models of strategic interactions in computer science use simultaneous move games. However, in applications simultaneity is often hard or impossible to achieve. In this paper, we study the robustness of the Nash Equilibrium when the assumption of simultaneity is dropped. In particular we propose studying the sequential price of anarchy: the quality of outcomes of sequential versions of games whose simultaneous counterparts are prototypical in algorithmic game theory. We study different classes of games with high price of anarchy, and show that the subgame perfect equilibrium of their sequential version is a much more natural prediction, ruling out unreasonable equilibria, and leading to much better quality solutions.

In many natural settings agents participate in multiple different auctions that are not simultaneous. In such auctions, future opportunities affect strategic considerations of the players. The goal of this paper is to develop a quantitative understanding of outcomes of such sequential auctions. In earlier work (Paes Leme et al. 2012) we initiated the study of the price of anarchy in sequential auctions. We considered sequential first price auctions in the full information model, where players are aware of all future opportunities, as well as the valuation of all players. In this paper, we study efficiency in sequential auctions in the Bayesian environment, relaxing the informational assumption on the players. We focus on two environments, both studied in the full information model in Paes Leme et al. 2012, matching markets and matroid auctions. In the full information environment, a sequential first price cut auction for matroid settings is efficient. In Bayesian environments this is no longer the case, as we show using a simple example with three players. Our main result is a bound of 3 on the price of anarchy in both matroid auctions and matching markets. To bound the price of anarchy we need to consider possible deviations at an equilibrium. In a sequential Bayesian environment the effect of deviations is more complex than in one-shot games; early bids allow others to infer information about the player's value. We create effective deviations despite the presence of this difficulty by introducing a bluffing technique of independent interest.

In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this consideration, we study a setting of a market of buyers and sellers, where each seller holds one item, bidders have combinatorial valuations and sellers hold item auctions sequentially. Our results are qualitatively different from those of simultaneous auctions, proving that simultaneity is a crucial aspect of previous work. We prove that if sellers hold sequential first price auctions then for unit-demand bidders (matching market) every subgame perfect equilibrium achieves at least half of the optimal social welfare, while for submodular bidders or when second price auctions are used, the social welfare can be arbitrarily worse than the optimal. We also show that a first price sequential auction for buying or selling a base of a matroid is always efficient, and implements the VCG outcome. An important tool in our analysis is studying first and second price auctions with externalities (bidders have valuations for each possible winner outcome), which can be of independent interest. We show that a Pure Nash Equilibrium always exists in a first price auction with externalities.

The Generalized Second Price (GSP) auction is the primary auction used for selling sponsored search advertisements. In this paper we consider the revenue of this auction at equilibrium. We prove that if agent values are drawn from identical regular distributions, then the GSP auction paired with an appropriate reserve price generates a constant fraction (1/6th) of the optimal revenue. In the full-information game, we show that at any Nash equilibrium of the GSP auction obtains at least half of the revenue of the VCG mechanism excluding the payment of a single participant. This bound holds also with any reserve price, and is tight.

The spread of a cascading failure through a network is an issue that comes up in many domains - in the contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease. Here we study a natural model of threshold contagion: each node v is assigned a numerical threshold ℓ(v) drawn independently from an underlying distribution μ, and v will fail as soon as ℓ(v) of its neighbors fail. Despite the simplicity of the formulation, it has been very challenging to analyze the failure processes that arise from arbitrary threshold distributions; even qualitative questions concerning which graphs are the most resilient to cascading failures in these models have been difficult to resolve. Here we develop a set of new techniques for analyzing the failure probabilities of nodes in arbitrary graphs under this model, and we compare different graphs G according to their μ-risk, defined as the maximum failure probability of any node in G when thresholds are drawn from μ. We find that the space of threshold distributions has a surprisingly rich structure when we consider the risk that these thresholds induce on different graphs: small shifts in the distribution of the thresholds can favor graphs with a maximally clustered structure (i.e., cliques), those with a maximally branching structure (trees), or even intermediate hybrids.

There are a number of domains where agents must collectively form a network in the face of the following trade-off: each agent receives benefits from the direct links it forms to others, but these links expose it to the risk of being hit by a cascading failure that might spread over multi-step paths. Financial contagion, epidemic disease, and the exposure of covert organizations to discovery are all settings in which such issues have been articulated.

We give several new upper and lower bounds on the worst-case severity of Braess's paradox and the price of anarchy of selfish routing with respect to the maximum latency objective. In single-commodity networks with arbitrary continuous and nondecreasing latency functions, we prove that this worst-case price of anarchy is exactly $n-1$, where n is the number of network vertices. For Braess's paradox in such networks, we prove that removing at most c edges from a network decreases the common latency incurred by traffic at equilibrium by at most a factor of $c+1$. In particular, the worst-case severity of Braess's paradox with a single edge removal is maximized in Braess's original four-vertex network. In multicommodity networks, we exhibit an infinite family of two-commodity networks, related to the Fibonacci numbers, in which both the worst-case severity of Braess's paradox and the price of anarchy for the maximum latency objective grow exponentially with the network size. This construction demonstrates that numerous known selfish routing results for single-commodity networks have no analogues in networks with two or more commodities. We also prove an upper bound on both of these quantities that is exponential in the network size and independent of the network latency functions, showing that our construction is close to optimal. Finally, we use our family of two-commodity networks to exhibit a natural network design problem with intrinsically exponential (in)approximability.

We consider pixel labeling problems where the label set forms a tree, and where the observations are also labels. Such problems arise in feature-space analysis with a very large label set, for instance in color image segmentation. In this case a tree of labels can be constructed via hierarchical clustering of the observations. This leads to an obvious distance function between two labels, namely their distance within the tree; such tree metrics have been extensively studied outside of computer vision. We provide fast algorithms that use graph cuts to exactly minimize the energy function for pixel labeling problems with tree metrics. Our work substantially improves a facility location algorithm of Kolen, which is impractical for large label sets L since it requires O(|L|) min cuts on large graphs. Our main technical contribution is a new ordering of swap moves that reduces the running time to the equivalent of O(log |L|) min cuts; as a result, we can handle realistic-sized color images in a few seconds.

The Generalized Second Price Auction has been the main mechanism used by search companies to auction positions for advertisements on search pages. In this paper we study the social welfare of the Nash equilibria of this game in various models. In the full information setting, socially optimal Nash equilibria are known to exist (i.e., the Price of Stability is 1). This paper is the first to prove bounds on the price of anarchy, and to give any bounds in the Bayesian setting. Our main result is to show that the price of anarchy is small assuming that all bidders play un-dominated strategies. In the full information setting we prove a bound of 1.618 for the price of anarchy for pure Nash equilibria, and a bound of 4 for mixed Nash equilibria. We also prove a bound of 8 for the price of anarchy in the Bayesian setting, when valuations are drawn independently, and the valuation is known only to the bidder and only the distributions used are common knowledge. Our proof exhibits a combinatorial structure of Nash equilibria and uses this structure to bound the price of anarchy. While establishing the structure is simple in the case of pure and mixed Nash equilibria, the extension to the Bayesian setting requires the use of novel combinatorial techniques that can be of independent interest.

We introduce a facility location problem with submodular facility cost functions, and give an O (log n ) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give a (4.237 + ϵ)-approximation algorithm using local search. The hierarchical facility costs model multilevel service installation. Shmoys et al. [2004] gave a constant factor approximation algorithm for a two-level version of the problem. Here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.

We analyze the performance of protocols for load balancing in distributed systems based on no-regret algorithms from online learning theory. These protocols treat load balancing as a repeated game and apply algorithms whose average performance over time is guaranteed to match or exceed the average performance of the best strategy in hindsight.

We study the outcome of natural learning algorithms in atomic congestion games. Atomic congestion games have a wide variety of equilibria often with vastly differing social costs. We show that in almost all such games, the well-known multiplicative-weights learning algorithm results in convergence to pure equilibria. Our results show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game introduced by Koutsoupias and Papadimitriou, which has super-constant price of anarchy and has correlated equilibria that are exponentially worse than any mixed Nash equilibrium.

Abstract The smallest k‐ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k‐edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2 (k ≥ 1), a polynomial‐time algorithm approximating the smallest k‐ECSS on undirected (directed) multigraphs to within ratio 1 + c/k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

A fundamental principle in social network research is that individuals can benefit from serving as intermediaries between others who are not directly connected. Through such intermediation, they potentially can broker the flow of information and synthesize ideas arising in different parts of the network. These principles form the underpinning for the theory of structural holes, which studies the ways in which individuals, particularly in organizational settings, fill the holes between people or groups that are not otherwise interacting.We apply a game-theoretic approach to this notion, studying the structures that evolve when individuals in a social network have incentives to form links that bridge otherwise disconnected parties. We model payoffs as a trade-off between the benefits of connecting non-neighboring nodes, and the cost, in effort, to maintain links - including settings where the costs are non-uniform to reflect the increased difficulty in spanning different parts of a hierarchical organization.We find, both through theoretical results and computational experiments, that the equilibrium networks in this model have rich combinatorial structure, and capture qualitative observations arising in the study of structural holes. In particular, even in completely symmetric settings, individuals will differentiate themselves in equilibrium, occupying different social strata and receiving correspondingly different payoffs.

The study of bargaining has a long history, but many basic settings are still rich with unresolved questions. In particular, consider a set of agents who engage in bargaining with one another,but instead of pairs of agents interacting in isolation,agents have the opportunity to choose whom they want to negotiate with, along the edges of a graph representing social-network relations. The area of network exchange theory in sociology has developed a large body of experimental evidence for the way in which people behave in such network-constrained bargaining situations, and it is a challenging problem to develop models that are both mathematically tractable and in general agreement with the results of these experiments.

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions—the Nash equilibria—may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best Nash equilibrium solution has a natural meaning of stability in this context—it is the optimal solution that can be proposed from which no user will defect. We consider the price of stability for network design with respect to one of the most widely studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is $O(\log k)$, where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game.

In a wide range of markets, individual buyers and sellers often trade through intermediaries, who determine prices via strategic considerations. Typically, not all buyers and seller shave access to the same intermediaries, and they trade at correspondingly different prices that reflect their relative amounts of power in the market. We model this phenomenon using a game in which buyers, sellers, and traders engage in trade on a graph that represents the access each buyer and seller has to the traders. In this model, traders set prices strategically, and then buyers and sellers react to the prices they are offered. We show that the resulting game always has a subgame perfect Nash equilibrium, and that all equilibria lead to an efficient (i.e. socially optimal) allocation of goods. We extend these results to a more general type of matching market, such as one finds in the matching ofjob applicants and employers. Finally, we consider how the profits obtained by the traders depend on the underlying graph -- roughly, a trader cancommand a positive profit if and only if it has an "essential" connection in the network structure, thus providing a graph-theoretic basis for quantifying the amount of competition among traders. Our work differs from recent studies of how price is affected by network structure through our modeling of price-setting as a strategic activity carried out by a subset of agents in the system, rather than studying prices set via competitive equilibrium or by a truthful mechanism.

We consider a resource allocation game in polyhedral environments. Polyhedral environments model a wide range of problems, including bandwidth sharing, some models of Adwords auctions and general resource allocation. We extend the fair sharing mechanism for such resource allocation games. We show that our mechanism simultaneously creates approximately efficient allocations andallapproximately maximizes revenue. We also develop a new approach for analyzing games of these types. At the core of this approach is the relation between the condition for Nash equilibriums of the game and the dual of a certain linear program.

We consider the problem of selecting a low-cost s - t path in a graph where the edge costs are a secret, known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) mechanism, which pays a premium to induce the edges so as to reveal their costs truthfully. We observe that this premium can be unacceptably high. There are simple instances where the mechanism pays Θ(n) times the actual cost of the path, even if there is an alternate path available that costs only (1 + ϵ) times as much. This inspires the frugal path problem, which is to design a mechanism that selects a path and induces truthful cost revelation, without paying such a high premium.

In this paper we initiate the study of how collusion alters the quality of solutions obtained in competitive games. The price of anarchy aims to measure the cost of the lack of coordination by comparing the quality of a Nash equilibrium to that of a centrally designed optimal solution. This notion assumes that players act not only selfishly, but also independently. We propose a framework for modeling groups of colluding players, in which members of a coalition cooperate so as to selfishly maximize their collective welfare. Clearly, such coalitions can improve the social welfare of the participants, but they can also harm the welfare of those outside the coalition. One might hope that the improvement for the coalition participants outweighs the negative effects on the others. This would imply that increased cooperation can only improved the overall solution quality of stable outcomes. However, increases in coordination can actually lead to significant decreases in total social welfare. In light of this, we propose the price of collusion as a measure of the possible negative effect of collusion, specifying the factor by which solution quality can deteriorate in the presence of coalitions. We give examples to show that the price of collusion can be arbitrarily high even in convex games. Our main results show that in the context of load-balancing games, the price of collusion depends upon the disparity in market power among the game participants. We show that in some symmetric nonatomic games (where all users have access to the same set of strategies) increased cooperation always improves the solution quality, and in the discrete analogs of such games, the price of collusion is bounded by two.

The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disperate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system.

We present efficient algorithms for a special case of network design problems, the strong-connectivity problem. Given a directed graph G, the strong-connectivity problem seeks a minimum cost strongly connected spanning subgraph of G. Our algorithms include the primal-dual method, penalty algorithms, and drop algorithms. Primal-dual methods have been quite successful for developing algorithms for undirected network design problems. However, no results are known for extending them to the directed counterparts. We apply the primal-dual method to the strong-connectivity problem, and show that the new algorithm has an approximation guarantee of three. Our computational results over randomly created instances show that the primal-dual is efficient. We develop two improved algorithms, penalty and drop, building on primal-dual as a subroutine.

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions - the Nash equilibria - may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best Nash equilibrium solution has a natural meaning of stability in this context - it is the optimal solution that can be proposed from which no user will "defect". We consider the price of stability for network design with respect to one of the most widely-studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value, and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is O(log k), where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game.

Network games approach some of the traditional algorithmic questions in networks from the perspective of game theory, which gives rise of a wide range of interesting issues. In this talk we will give an overview of recent progress in many of these areas, and show strong ties to certain algorithmic techniques.

Abstract We present approximation algorithms for a class of directed network design problems. The network design problem is to find a minimum cost subgraph such that for each vertex set S there are at least f ( S ) arcs leaving the set S . In the last 10 years general techniques have been developed for designing approximation algorithms for undirected network design problems. Recently, Kamal Jain gave a 2‐approximation algorithm for the case when the function f is weakly supermodular. There has been very little progress made on directed network design problems. The main techniques used for the undirected problems do not have simple extensions to the directed case. András Frank has shown that in a special case when the function f is intersecting supermodular the problem can be solved optimally. In this article, we use this result to get a 2‐approximation algorithm for a more general case when f is crossing supermodular. We also extend Jain's techniques to directed problems. We prove that if the function f is crossing supermodular, then any basic solution of the LP relaxation of our problem contains at least one variable with value greater or equal to ¼. This result implies a 4‐approximation algorithm for the class of directed network design problems. © 2004 Wiley Periodicals, Inc.

We develop a general method for turning a primal-dual algorithm into a group strategy proof cost-sharing mechanism. We use our method to design approximately budget balanced cost sharing mechanisms for two NP-complete problems: metric facility location, and single source rent-or-buy network design. Both mechanisms are competitive, group strategyproof and recover a constant fraction of the cost. For the facility location game our cost-sharing method recovers a 1/3rd of the total cost, while in the network design game the cost shares pay for a 1/15 fraction of the cost of the solution.

Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. Recently, motivated by the design of viral marketing strategies, Domingos and Richardson posed a fundamental algorithmic problem for such social network processes: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?We consider this problem in several of the most widely studied models in social network analysis. The optimization problem of selecting the most influential nodes is NP-hard here, and we provide the first provable approximation guarantees for efficient algorithms. Using an analysis framework based on submodular functions, we show that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.We also provide computational experiments on large collaboration networks, showing that in addition to their provable guarantees, our approximation algorithms significantly out-perform node-selection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks.

We introduce a simple network design game that models how independent selfish agents can build or maintain a large network. In our game every agent has a specific connectivity requirement, i.e. each agent has a set of terminals and wants to build a network in which his terminals are connected. Possible edges in the network have costs and each agent's goal is to pay as little as possible. Determining whether or not a Nash equilibrium exists in this game is NP-complete. However, when the goal of each player is to connect a terminal to a common source, we prove that there is a Nash equilibrium as cheap as the optimal network, and give a polynomial time algorithm to find a (1+ε)-approximate Nash equilibrium that does not cost much more. For the general connection game we prove that there is a 3-approximate Nash equilibrium that is as cheap as the optimal network, and give an algorithm to find a (4.65+ε)-approximate Nash equilibrium that does not cost much more.

In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects , in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry, and document analysis. In its most basic form, this style of analysis seeks to find a classification that optimizes a combinatorial function consisting of assignment costs ---based on the individual choice of label we make for each object---and separation costs ---based on the pair of choices we make for two "related" objects.We formulate a general classification problem of this type, the metric labeling problem ; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem .We provide the first nontrivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O (log k log log k )-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric ---all distances are the same---our methods provide a 2-approximation algorithm.

We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times---the total latency---is minimized.In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance.In this article, we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routingtwiceas much traffic.

The authors show how to design truthful (dominant strategy) mechanisms for several combinatorial problems where each agent's secret data is naturally expressed by a single positive real number. The goal of the mechanisms we consider is to allocate loads placed on the agents, and an agent's secret data is the cost she incurs per unit load. We give an exact characterization for the algorithms that can be used to design truthful mechanisms for such load balancing problems using appropriate side payments. We use our characterization to design polynomial time truthful mechanisms for several problems in combinatorial optimization to which the celebrated VCG mechanism does not apply. For scheduling related parallel machines (Q/spl par/C/sub max/), we give a 3-approximation mechanism based on randomized rounding of the optimal fractional solution. This problem is NP-complete, and the standard approximation algorithms (greedy load-balancing or the PTAS) cannot be used in truthful mechanisms. We show our mechanism to be frugal, in that the total payment needed is only a logarithmic factor more than the actual costs incurred by the machines, unless one machine dominates the total processing power. We also give truthful mechanisms for maximum flow, Q/spl par//spl Sigma/C/sub j/ (scheduling related machines to minimize the sum of completion times), optimizing an affine function over a fixed set, and special cases of uncapacitated facility location. In addition, for Q/spl par//spl Sigma/w/sub j/C/sub j/ (minimizing the weighted sum of completion times), we prove a lower bound of 2//spl radic/3 for the best approximation ratio achievable by truthful mechanism.

The authors give the first constant factor approximation algorithm for the facility location problem with nonuniform, hard capacities. Facility location problems have received a great deal of attention in recent years. Approximation algorithms have been developed for many variants. Most of these algorithms are based on linear programming, but the LP techniques developed thus far have been unsuccessful in dealing with hard capacities. A local-search based approximation algorithm (M. Korupolu et al., 1998; F.A. Chudak and D.P. Williamson, 1999) is known for the special case of hard but uniform capacities. We present a local-search heuristic that yields an approximation guarantee of 9 + /spl epsi/ for the case of nonuniform hard capacities. To obtain this result, we introduce new operations that are natural in this context. Our proof is based on network flow techniques.

We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times-the total latency-is minimized. In many settings, including the Internet and other large-scale communication networks, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance. We quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and non-decreasing in the edge congestion.

In a traditional classification problem, we wish to assign labels from a set to each of objects so that the labeling is consistent with some observed data that includes pairwise relationships among the objects. Kleinberg and Tardos recently formulated a general classification problem of this type, the “metric labeling problem”, and gave an approximation algorithm for it. The algorithm is based on solving a linear programming relaxation of a natural integer program and then randomized rounding. In this paper we consider an important case of the metric labeling problem, in which the metric is the truncated linear metric. This is a natural non-uniform and robust metric, and it arises in a number of applications. We give a combinatorial 4-approximation algorithm for this metric. Our algorithm is a natural local search method, where the local steps are based on minimum cut computations in an appropriately constructed graph. Our method extends previous work by Boykov, Veksler and Zabih on more restricted classes of metrics.

In this paper, we undertake the first study of statistical multiplexing from the perspective of approximation algorithms. The basic issue underlying statistical multiplexing is the following: in high-speed networks, individual connections (i.e., communication sessions) are very bursty, with transmission rates that vary greatly over time. As such, the problem of packing multiple connections together on a link becomes more subtle than in the case when each connection is assumed to have a fixed demand. We consider one of the most commonly studied models in this domain: that of two communicating nodes connected by a set of parallel edges, where the rate of each connection between them is a random variable. We consider three related problems: (1) stochastic load balancing, (2) stochastic bin-packing, and (3) stochastic knapsack. In the first problem the number of links is given and we want to minimize the expected value of the maximum load. In the other two problems the link capacity and an allowed overflow probabilityp are given, and the objective is to assign connections to links, so that the probability that the load of a link exceeds the link capacity is at most p. In bin-packing we need to assign each connection to a link using as few links as possible. In the knapsack problem each connection has a value, and we have only one link. The problem is to accept as many connections as possible. For the stochastic load balancing problem we give an O(1)-approximation algorithm for arbitrary random variables. For the other two problems we have algorithms restricted to on-off sources (the most common special case studied in the statistical multiplexing literature), with a somewhat weaker range of performance guarantees. A standard approach that has emerged for dealing with probabilistic resource requirements is the notion of effective bandwidth---this is a means of associating a fixed demand with a bursty connection that "represents" its distribution as closely as possible. Our approximation algorithms make use of the standard definition of effective bandwidth and also a new one that we introduce; the performance guarantees are based on new results showing that a combination of these measures can be used to provide bounds on the optimal solution.

We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria interacts in a complex fashion with the optimization of network utilization and throughput; in this work, we undertake an investigation of this relationship through the framework of approximation algorithms. In this work we consider the problem of selecting paths for routing so as to provide a bandwidth allocation that is as fair as possible (in the max-min sense). We obtain the first approximation algorithms for this basic optimization problem, for single-source unsplittable routings in an arbitrary directed graph. Special cases of our model include several fundamental load balancing problems, endowing them with a natural fairness criterion to which our approach can be applied. Our results form an interesting counterpart to the work of Megiddo (1974), who considered max-min fairness for single-source fractional flow. The optimization problems in our setting become NP-complete, and require the development of new techniques for relating fractional relaxations of routing to the equilibrium constraints imposed by the fairness criterion.

In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry: and document analysis. In its most basic form, this style of analysis seeks a classification that optimizes a combinatorial function consisting of assignment costs-based on the individual choice of label we make for each object-and separation costs-based on the pair of choices we make for two "related" objects. We formulate a general classification problem of this type, the metric labeling problem; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem. We provide the first non-trivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O(log k log log k)-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric-all distances are the same-our methods provide a 2-approximation.

Article Free Access Share on A constant-factor approximation algorithm for the k-median problem (extended abstract) Authors: Moses Charikar Stanford University, Stanford, CA Stanford University, Stanford, CAView Profile , Sudipto Guha Stanford University, Stanford, CA Stanford University, Stanford, CAView Profile , Éva Tardos Cornell University, Ithaca, NY Cornell University, Ithaca, NYView Profile , David B. Shmoys Cornell University, Ithaca, NY Cornell University, Ithaca, NYView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 1–10https://doi.org/10.1145/301250.301257Published:01 May 1999Publication History 170citation1,175DownloadsMetricsTotal Citations170Total Downloads1,175Last 12 Months198Last 6 weeks31 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we consider the online ftp problem.The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network.The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as mu-stretch, total flow time, max flow time, and total completion time.In particular, we show how to achieve optimum total flow time and optimum max.stretch if we increase the capacity of the underlying network by a logarithmic factor.We show that the resource augmentation is necessary by proving polynomial lower bounds on the maxstretch and total flow time for the case where online and offline algorithms are using same-capacity edges.Moreover, we also give poly-logarithmic lower bounds on the resource augmentation factor necessary in order to keep the total Aow time and max.stretch within a constant factor of optimum.

We consider the problem of connecting distinguished terminal pairs in a graph via edge-disjoint paths. This is a classical NP-complete problem for which no general approximation techniques are known; it has recently been brought into focus in papers discussing applications to admission control in high-speed networks and to routing in all- optical networks. In this paper we provideO(log n)-approximation algorithms for two natural optimization versions of this problem for the class of nearly Eulerian, uniformly high-diameter planar graphs, which includes two-dimensional meshes and other common planar interconnection networks. We give anO(log n)-approximation to the maximum number of terminal pairs that can be simultaneously connected via edge-disjoint paths, and anO(log n)-approximation to the minimum number of wavelengths needed to route a collection of terminal pairs in the “optical routing” model considered by Raghavan, Upfal, and others. The latter result improves on anO(log2 n)-approximation for the special case of the mesh obtained independently by Aumann and Rabani. For both problems theO(log n)-approximation is a consequence of anO(1)-approximation for the special case when all terminal pairs are roughly the same distance apart. Our algorithms make use of a number of new techniques, including the construction of a “crossbar” structure in any nearly Eulerian planar graph, and develops some connections with classical matroid algorithms.

Abstract. In this paper, we undertake the first study of statistical multiplexing from the perspective of approximation algorithms. The basic issue underlying statistical multiplexing is the following: in high-speed networks, individual connections (i.e., communication sessions) are very bursty, with transmission rates that vary greatly over time. As such, the problem of packing multiple connections together on a link becomes more subtle than in the case when each connection is assumed to have a fixed demand. We consider one of the most commonly studied models in this domain: that of two communicating nodes connected by a set of parallel edges, where the rate of each connection between them is a random variable. We consider three related problems: (1) stochastic load balancing, (2) stochastic bin-packing, and (3) stochastic knapsack. In the first problem the number of links is given and we want to minimize the expected value of the maximum load. In the other two problems the link capacity and an allowed overflow probability p are given, and the objective is to assign connections to links, so that the probability that the load of a link exceeds the link capacity is at most p. In binpacking we need to assign each connection to a link using as few links as possible. In the knapsack problem each connection has a value, and we have only one link. The problem is to accept as many

We present new approximation algorithms for several facility location problems.In each facility location problem that we study, there is a set of locations at which we may build a facility (such as a warehouse), where the cost of building at location i is ~i; ftiermore, there is a set of client locations (such as stores) that require to be serviced by a facility, and if a client at location j is assigned to a facility at location i, a cost of cl] is incurred that is proportional to the distance between i and j.The objective is to determine a set of locations at which to open facilities so as to minimize the total facility and assignment costs.In the incapacitated case, each facility can service an unlimited number of clients, whereas in the capacitated case, each facility can serve, for example, at most u clients.These models and a number of closely related ones have been studied extensively in the Operations Research literature.We shall consider the case in which the distances between locations are non-negative, symmetric and satisfy the triangle inequality.For the incapacitated facility location, we give a polynomial-time algorithm that finds a solution of cost within a factor of 3.16 of the optimal.This is the first constant performance guarantee known for this problem.We also present approximation algorithms with constant performance guarantees for a number of capacitated models as well as a generalization in which there is a 2-level hierarchy of facilities.Our results are based on the filtering and rounding technique of Lin & Wter.We also give a randomized variant of this technique that can then be derandomized to yield improved deterministic performance guarantees.

In a seminal paper Leighton, Maggs, and Rao consider the packet scheduling problem when a single packet has to traverse each path. They show that there exists a schedule where each packet reaches its destination in O(C + D) steps, where C is the congestion and D is the dilation. The proof relies on the Lov'asz Local Lemma, and hence is not algorithmic. In a followup paper Leighton and Maggs use an algorithmic version of the Local Lemma due to Beck to give centralized algorithms for the problem. Leighton, Maggs, and Rao also give a distributed randomized algorithm where all packets reach their destinations with high probability in O(C +D log n) steps. In this paper we develop techniques to guarantee the high probability of delivering packets without resorting to the Lov'asz Local Lemma. We improve the distributed algorithm for problems with relatively high dilation to O(C) + (log n) O(log n) D + poly(log n). We extend the techniques to handle the case of infinite streams of ...

We consider the following maximum disjoint paths problem (MDPP). We are given a large network, and pairs of nodes that wish to communicate over paths through the network-the goal is to simultaneously connect as many of these pairs as possible in such a way that no two communication paths share an edge in the network. This classical problem has been brought into focus recently in papers discussing applications to routing in high-speed networks, where the current lack of understanding of the MDPP is an obstacle to the design of practical heuristics. We consider the class of densely embedded, nearly-Eulerian graphs, which includes the two-dimensional mesh and other planar and locally planar interconnection networks. We obtain a constant-factor approximation algorithm for the maximum disjoint paths problem for this class of graphs; this improves on an O(log n)-approximation for the special case of the two-dimensional mesh due to Aumann-Rabani and the authors. For networks that are not explicitly required to be "high-capacity," this is the first constant-factor approximation for the MDPP in any class of graphs other than trees. We also consider the MDPP in the on-line setting, relevant to applications in which connection requests arrive over time and must be processed immediately. Here we obtain an asymptptically optimal O(log n)competitive on-line algorithm for the same class of graphs; this improves on an O(log n log log n) competitive algorithm for the special case of the mesh due to B. Awerbuch et al (1994).

Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the multicommodity flow problem with integer demands and at least O(k2.5n2m0.5 log(nϵ−1DU)) time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in O (knm log4n) time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + ϵ)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in "sparsest cut" problems and uniform concurrent flow problems.

This paper describes new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. These algorithms are much faster than algorithms discovered previously. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications. Leighton and Rao used uniform-capacity concurrent flow to find an approximately “sparsest cut” in a graph and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical as it required solving a large linear program. This paper shows that their method might be practical by giving an $O(m^2 \log m)$ expected-time randomized algorithm for their concurrent flow problem on an m-edge graph. Raghavan and Thompson used uniform-capacity concurrent flow to solve approximately a channel width minimization problem in very large scale integration. An $O(k^{{3 / 2}} (m + n\log n)$ expected-time randomized algorithm and an $O(k\min \{ n,k\} (m + n\log n)\log k)$ deterministic algorithm is given for this problem when the channel width is $\Omega (\log n)$, where k denotes the number of wires to be routed in an n-node, m-edge network.

In this paper we consider the worst case ratio between the capaciry of minimum-cuts and the value of maximum-flow for multicommodity flow problems.We improve the best known bounds for the rein-cut rnax-flow ratio for multicommodi~flows in undirected graphs, by replacing the O(log D) in the bound by O(log k), where D denotes the sum of all demands, and k denotes the number of commodities.In essence we prove that up to constant factors the worst tin-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rae, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the rein-cut max-flow ratio in general undirected graphs is bounded by O(log C log D), where C denotes the sum of all the capacities.Tragoudas has improved this bound to O(log n log D),where n is the number of nodes in the network.Garg, Vazirani and Yannakakis further improved this to O(log k log D).Klein, Plotkin and Rao have proved that for planar networks, the ratio is O(log D).Our result improves the bound for general nemvorks to O(log2 k) and the bound for planar networks to O(log k).In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved.The method presented in this paper can be used to give polynomial time approfi~~on ~gorithms tO the ~~mum-cuts in the network UP to the above factors.Compumtion Of such cuts is a basic step for a varie~of approximation algorithms for NP-complete problems.

We consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this problem can be bounded by O(log k), where k is the number of commodities. In this note we improve this ratio to O(1) for planar graphs, and more generally to O(r3) for graphs with an excluded Kr, r minor. The proof is based on the network decomposition theorem of Klein, Plotkin and Rao. Our proof is constructive and yields approximation algorithms, with the same factors, for the minimum multicut problem on such networks.

In this paper interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. This algorithm finds a maximum cardinality matching in a bipartite graph with n nodes and m edges in $O(\sqrt m \log ^3 n)$ time on a CRCW PRAM. The results here extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding $O(\sqrt m \log ^2 n\log nC)$ algorithms, where $C > 1$ is an upper bound on the absolute value of the integral weights or costs in the two problems, respectively. The results here improve previous bounds on these problems and introduce interior-point methods to the context of parallel algorithm design.

Fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems, are presented. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. The algorithms are based on a Lagrangian relaxation technique, and an important result is a theoretical analysis of the running time of a Lagrangian relaxation based algorithm. Several applications of the algorithms are presented.>

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming.The best of these algorithms [14] uses a fast matrix multiplication algorithm and takes O(k25n2m5 log(nDU))time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity.Substantially more time is needed to find an exact solution.As a consequence, even multicommodit y flow problems with jnst a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems.In thk paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem.The running time of our randomized algorithm is (up to ,log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation.In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2 n) single-commodity minimum-cost flow problems.Our k-commodity algorithm runs in O(knm log4 n) time with high probability.We also describe a deterministic algorithm that uses an O(k)-factor more time.Given any multicommodit y flow problem as input, both rdgorithms are guaranteed to provide a feasible solution to a modified @ 1991

In this paper, we describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities.Our algorithms are much faster than previously known algorithms.Besides being an important problem in its own right, the concurrent flow problem has many interesting applications.Leighton and Rao used concurrent flow to find an approximately "sparsest cut" in a graph, and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout.We show that their method might be practical by giving an O(m~logm) expected-time randomized algorithm for their concurrent flow problem on an m-edge graph.l~aghavan and Thompson used concurrent flow to approximately solve a channel width minimization problem in VLSI.We give an O(k3/2(m+n log n)) expectedtime randomized algorithm and an O(k min{n, k}(m + n log n) log k) deterministic algorithm for this problem when the channel width is O(logn), where k denotes the number of wires to be routed in an n-node, m-edge network,

Interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. The algorithm runs in O*( square root m) time. The results extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding O*( square root m log C) algorithms. This improves previous bounds on these problems and illustrates the importance of interior-point methods in parallel algorithm design.>

In 1974 Weintraub [Management Sci., 21 (1974), pp. 87–97] published an algorithm for the minimum-cost circulation problems with convex cost function. In this note Weintraub’s algorithm is considered when applied to a minimum-cost circulation problem with linear objective function. It is shown that a minor variation of the algorithm runs in polynomial time. The resulting algorithm, although it is not strongly polynomial, does not rely on scaling. It is a generalization of the maximum flow algorithm due to Edmonds and Karp [J. Assoc. Comput. Mach., 19 (1972), pp. 248–264] that augments along the fattest augmenting path in the residual graph. The algorithm described here is slower than the fastest minimum-cost circulation algorithms known. The authors’ interest in the algorithm is partially historical, a scaling free “almost polynomial time” algorithm was published in 1974, and partially due to the different ideas involved.

A generalization of the maximum-flow problem is considered in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e) lambda (e) units arrive at the other end. For instance, nodes of the graph can correspond to different currencies, with the multipliers being the exchange rates. Conservation of flow is required at every node except a given source node. The goal is to maximize the amount of flow excess at the source. This problem is a special case of linear programming, and therefore can be solved in polynomial time. The authors present polynomial-time combinatorial algorithms for this problem. The algorithms are simple and intuitive.>

The minimum-cost flow problem is: Given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the problem has been known for some time, but only recently a strongly polynomial algorithm was discovered. In this paper an O ( n 2 ( m + n log n )log n ) algorithm is designed. The previous best algorithm, due to Fujishige and Orlin, had an O ( m 2 ( m + n log n )log n ) time bound. Thus, for dense graphs an improvement of two orders of magnitude is obtained. The algorithm in this paper is based on Fujishige's algorithm (which is based on Tardos's algorithm). Fujishige's algorithm consists of up to m iterations, each consisting of O ( m log n ) steps. Each step solves a single source shortest path problem with nonnegative edge lengths. This algorithm is modified in order to make an improved analysis possible. The new algorithm may still consist of up to m iterations, and an iteration may still consist of up to O ( m log n ) steps, but it can still be shown that the total number of steps is bounded by O ( n 2 log n . The improvement is due to a new technique that relates the time spent to the progress achieved.

We consider the following scheduling problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time pij. The objective is to find a schedule that minimizes the makespan. Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints. In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unless P = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.

The minimum-cost flow problem is the following: given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the problem has been known for some time [EK], but only recently a strongly polynomial algorithm was discovered [Ts]. In this paper we design an O(n2(m + n log n)log n) algorithm. The previous best algorithm had an O(m2 (m + n log n) log n) time bound ([F], [O]). Thus, we obtain an improvement of two orders of magnitude for dense graphs. Our algorithm is based on Fujishige's algorithm [F] (which is based on Tardos' algorithm [Ts]). Fujishige's algorithm consists of up to O(m log n) steps. Each step solves a single source shortest path problem with nonnegative edge lengths. We modify this algorithm in order to make an improved analysis possible. The new algorithm may still consist of up to m iterations, and an iteration may still consist of up to O(m log n) steps, but we can still show that the total number of steps is bounded by O(n2 log n). The improvement is due to a new technique that relates the time spent to the progress achieved.

We present a preprocessing algorithm to make certain polynomial algorithms strongly polynomial. The running time of some of the known combinatorial optimization algorithms depends on the size of the objective function w. Our preprocessing algorithm replaces w by an integral valued w whose size is polynomially bounded in the size of the combinatorial structure and which yields the same set of optimal solutions as w. As applications we show how existing polynomial algorithms for finding the maximum weight clique in a perfect graph and for the minimum cost submodular flow problem can be made strongly polynomial. The method relies on Lovász's simultaneous approximation algorithm.