Search

In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21]. In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever. There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative online benchmark and show that considering this new benchmark allows them to improve the 0.5 approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a 0.51-approximation algorithm which was later improved to 0.526 by Saberi and Wajc [ICALP'21]. The main contribution of this paper is designing a simple algorithm with a significantly improved approximation ratio of (1-1/e) for this problem. We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive in an online fashion with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively with the best approximation ratio being 0.337 with respect to the offline benchmark. This paper, however, is the first to consider the online benchmark for the edge arrival version of the problem. For this problem, we provide a simple algorithm with an approximation ratio of 0.5 with respect to the online benchmark. [ABSTRACT FROM AUTHOR]

A century ago, Emile Borel published his seminal paper on the theory of play and integral equations with skew-symmetric kernels[1]. Borel describes what is now called the Blotto game: a resource-allocation game in which two players compete for over n different battlefields by simultaneously allocating resources to each battlefield. The following two additional characteristics are perhaps the most salient features of the Blotto game: Winner-takes-all: For each battlefield, the player allocating the most resources to a given battlefield wins the battlefield. Fixed budget: each player is subject to a fixed---and deterministic---budget that mixed strategies should satisfy almost surely. Despite its century-long existence, Nash equilibria for the Blotto game are only known under various restrictions on the main parameters of the problem: the budget of each player and the value given to each battlefield. Moreover, previous solutions for two-player games have consisted in constructing explicit solutions. Because of the budget constraints, these strategies can be decomposed into two parts: marginal distributions that indicate which (random) strategy to play on each battlefield and a coupling that correlates the marginal strategies in such a way to ensure that the budget constraint is satisfied almost surely. The first part may be studied independently of the second by considering what is known as the (General) Lotto game. In this game, the budget constraint needs only be enforced in expectation with respect to the randomization of the mixed strategies. While this setup lacks a defining characteristic of the Blotto game (fixed budget), it has the advantage of lending itself to more amenable computations. Indeed, unlike the Blotto game, a complete solution to the Lotto game was recently proposed in [2] where the authors describe an explicit Nash equilibrium in the most general case: asymmetric budget, asymmetric and heterogeneous values. In light of this progress, a natural question is whether the marginal solutions discovered in [2] could be coupled in such a way that the budget constraint is satisfied almost surely. We provide a positive answer to this question by appealing to an existing result from the theory of joint mixability [5]. Mixability asks the following question: Can n random variables X1,..., Xn with prescribed marginal distributions Xi ~ Pi, be coupled in such a way that var(X1+ ··· + Xn)=0. Joint mixability is precisely the step required to go from a Lotto solution to a Blotto one by coupling the marginals of the Lotto solution in such a way that the budget constraint is satisfied. In this paper, we exploit a simple connection between joint mixability and the theory of multi-marginal couplings. We propose an algorithmic solution to the Blotto problem by efficiently constructing a coupling that satisfies the budget constraint almost surely and can be easily sampled from. Our construction relies on three key steps: first, we reduce the problem to a small number of marginals to bypass the inherent NP-hardness of multi-marginal problems, second, we discretize the marginals and finally, we employ a multi-marginal version of the Sinkhorn algorithm [3,4] to construct a coupling of the discretized marginals. This procedure outputs a coupling with continuous marginals that are close to the ones prescribed by the Lotto solutions of [2] and from which it is straightforward to sample. Furthermore, we quantify the combined effect of discretization error and of the Sinkhorn algorithm on the value of the game, effectively leading to an approximate Nash equilibrium and even to an approximately optimal solution in the case of symmetric values. For symmetric battlefield values and asymmetric budget, the Blotto game is constant-sum so optimal solutions exist, and our algorithm samples from an ε-optimal solution in time Õ(n2 + ε-4), independently of budgets and battlefield values. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an ε-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values. The full paper is available at: https://arxiv.org/abs/2202.07318. [ABSTRACT FROM AUTHOR]

Why do biased algorithmic predictions arise, and what interventions can prevent them?We examine this topic with a field experiment about using machine learning to predict human capital. We randomly assign ≈400 AI engineers to develop software to predict standardized test scores of OECD residents under different experimental conditions. We then assess the resulting predictive algorithms using the realized test performances, and through randomized audit-like manipulations of algorithmic inputs. We also used the diversity of our subject population to measure whether demographically non-traditional engineers were more likely to notice and reduce algorithmic bias, and whether algorithmic prediction errors are correlated within programmer demographic groups. This document describes our experimental design and motivation; the full results of our experiment are available at https://ssrn.com/abstract=3615404. [ABSTRACT FROM AUTHOR]

Most algorithmic studies on multi-agent information design have focused on the restricted situation of optimal public signaling with no inter-agent externalities; only a few exceptions investigated special game classes such as zero-sum games and second-price auctions. This paper initiates the algorithmic information design of both public and private signaling in a fundamental class of games with negative externalities, i.e., atomic singleton congestion games, with a wide range of applications in scheduling, routing, and network design, etc. For both public and private signaling, we show that the optimal information design can be efficiently computed when the number of resources is a constant. To our knowledge, this is the first set of efficient exact algorithms for information design in succinctly representable many-player games. Our results hinge on novel techniques such as developing certain reduced forms to compactly characterize equilibria in public signaling or to represent players' marginal beliefs in private signaling. When there are many resources, we show computational intractability results. Here, we introduce a new notion of (equilibrium)-obliviously NP-hardness, which rules out any possibility of computing a good signaling scheme, irrespective of the equilibrium selection. full version of this paper can be accessed from the following link: https://arxiv.org/pdf/2109.12445.pdf [ABSTRACT FROM AUTHOR]

A central goal in algorithmic game theory is to analyze the performance of decentralized multiagent systems, like communication and information networks. In the absence of a central planner who can enforce how these systems are utilized, the users can strategically interact with the system, aiming to maximize their own utility, possibly leading to very inefficient outcomes, and thus a high price of anarchy. To alleviate this issue, the system designer can use decentralized mechanisms that regulate the use of each resource (e.g., using local queuing protocols or scheduling mechanisms), but with only limited information regarding the state of the system. These information limitations have a severe impact on what such decentralized mechanisms can achieve, so most of the success stories in this literature have had to make restrictive assumptions (e.g., by either restricting the structure of the networks or the types of cost functions). In this paper, we overcome some of the obstacles that the literature has imposed on decentralized mechanisms, by designing mechanisms that are enhanced with predictions regarding the missing information. Specifically, inspired by the big success of the literature on "algorithms with predictions", we design decentralized mechanisms with predictions and evaluate their price of anarchy as a function of the prediction error, focusing on two very well-studied classes of games: scheduling games and multicast network formation games. [ABSTRACT FROM AUTHOR]

This paper introduces an objective for optimizing proper scoring rules. The objective is to maximize the increase in payoff of a forecaster who exerts a binary level of effort to refine a posterior belief from a prior belief. In this framework we characterize optimal scoring rules in simple settings, give efficient algorithms for computing optimal scoring rules in complex settings, and identify simple scoring rules that are approximately optimal. In comparison, standard scoring rules in theory and practice -- for example the quadratic rule, scoring rules for the expectation, and scoring rules for multiple tasks that are averages of single-task scoring rules -- can be very far from optimal. [ABSTRACT FROM AUTHOR]

Recent advances in the literature have demonstrated that standard supervised learning algorithms are ill-suited for problems with endogenous explanatory variables. To correct for this, many variants of nonparameteric instrumental variable regression methods have been developed. In this paper, we propose an alternative algorithm called boostIV that builds on the traditional gradient boosting algorithm and corrects for the endogeneity bias. The algorithm is very intuitive and resembles an iterative version of the standard 2SLS estimator. The proposed estimator is data driven and does not require any functional form approximation assumptions besides specifying a weak learner. We demonstrate that our estimator is consistent under mild conditions. We carry out extensive Monte Carlo simulations to demonstrate the finite sample performance of our algorithm compared to other recently developed methods. We show that boostIV is at worst on par with the existing methods and on average significantly outperforms them. [ABSTRACT FROM AUTHOR]

Centralized school admission mechanisms are an attractive way of improving social welfare and fairness in large educational systems. In this paper we report the design and implementation of the newly established school choice mechanism in Chile, where over 274,000 students applied to more than 6,400 schools. The Chilean system presents unprecedented design challenges that make it unique. On the one hand, it is a simultaneous nationwide system, making it one of the largest school admission problems worldwide. On the other hand, the system runs at all school levels, from Pre-K to 12th grade, raising at least two issues of outmost importance; namely, the system needs to guarantee their current seat to students applying for a school change, and the system has to favor the assignment of siblings to the same school. As in other systems around the world, we develop a model based on the celebrated Deferred Acceptance algorithm. The algorithm deals not only with the aforementioned issues, but also with further practical features such as soft-bounds and overlapping types. In this context we analyze new stability definitions, present the results of its implementation and conduct simulations showing the benefits of the innovations of the implemented system. [ABSTRACT FROM AUTHOR]

In recent years, Google has entered into a growing set of markets that are adjacent to its general search engine, launching new products such as Google Flights, Google Shopping, and Google Local. To leverage its dominance in general search, Google has often tied these products to its general search page, excluding competitor content. In this paper, we explore the strategic tradeoffs platforms face when pursuing a tying strategy to enter complementary markets, empirically investigating Google's decision to tie Google Local (its reviews product) to its search engine. We experimentally vary the content displayed on top of organic search results (called the "Onebox"), to show either exclusively Google reviews (the status quo), or reviews from multiple platforms that are determined to be the best-performing by Google's own organic search algorithm. We find that users prefer the OneBox and are more likely to engage with it when it includes competitor content. This suggests that Google's strategy of excluding competitor content leaves customers with a lower quality product. However, the number of reviews contained in Google Local has increased rapidly in recent years, suggesting that there may be a benefit of excluding competitors as well. Overall, these results shed light on a strategic tradeoff for companies that enter a complementary market using a tying strategy: while companies have successfully used this strategy, it can also come at a cost to consumers in the form of a lower-quality product. [ABSTRACT FROM AUTHOR]

A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify natural distributed algorithms that converge quickly to an equilibrium. This paper established new convergence results for two generalizations of proportional response in Fisher markets with buyers having CES utility functions. The starting points are respectively a new convex and a new convex-concave formulation of such markets. The two generalizations correspond to suitable mirror descent algorithms applied to these formulations. Several of our new results are a consequence of new notions of strong Bregman convexity and of strong Bregman convex-concave functions, and associated linear rates of convergence, which may be of independent interest. Among other results, we analyze a damped generalized proportional response and show a linear rate of convergence in a Fisher market with buyers whose utility functions cover the full spectrum of CES utilities aside the extremes of linear and Leontief utilities; when these utilities are included, we obtain an empirical $O(1/T)$ rate of convergence. [ABSTRACT FROM AUTHOR]

We consider the stochastic matching problem. An edge-weighted general (i.e., not necessarily bipartite) graph G(V, E) is given in the input, where each edge in E is realized independently with probability p ; the realization is initially unknown, however, we are able to query the edges to determine whether they are realized. The goal is to query only a small number of edges to find a realized matching that is sufficiently close to the maximum matching among all realized edges. The stochastic matching problem has received a considerable attention during the past decade after the initial paper of Chen et al. [ICALP'09] because of its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Most relevant to our work are the recent papers of Blum et al. [EC'15], Assadi et al. [EC'16, EC'17] and Maehara and Yamaguchi~[SODA'18] that consider the same model of stochastic matching. Our main result is an adaptive algorithm that for any arbitrarily small ε > 0, finds a (1-ε)-approximation in expectation, by querying only O(1) edges per vertex. We further show that our approach leads to a (1/2-ε)-approximate non-adaptive algorithm that also uses $O(1)$ edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi achieves a (1-ε)-approximation (resp. (1/2-ε)-approximation) by querying up to O(w łogn) edges per vertex where w denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of augmenting paths to weighted matchings that may be of independent interest. [ABSTRACT FROM AUTHOR]

We study combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC'14] and its follow-ups) the focus was on analyzing the implications and mitigating their negative consequences. In contrast, in this paper we show how in some cases cognitive biases can be harnessed to obtain better outcomes. Specifically, we study Walrasian equilibria in combinatorial markets. It is well known that Walrasian equilibria exist only in limited settings, e.g., when all valuations are gross substitutes, but fails to exist in more general settings, e.g., when the valuations are submodular. We consider combinatorial settings in which bidders exhibit the endowment effect, that is, their value for items increases with ownership. Our main result shows that when the valuations are submodular, even a mild degree of endowment effect is sufficient to guarantee the existence of Walrasian equilibria. In fact, we show that in contrast to Walrasian equilibria with standard utility maximizing bidders — in which the equilibrium allocation must be efficient — when bidders exhibit endowment effect any local optimum can be an equilibrium allocation. Our techniques reveal interesting connections between the LP relaxation of combinatorial auctions and local maxima. We also provide lower bounds on the intensity of the endowment effect that the bidders must have in order to guarantee the existence of a Walrasian equilibrium in various settings. [ABSTRACT FROM AUTHOR]

We study computational aspects of a well-known single-winner voting rule called the Schulze method [Schulze, 2003] which is used broadly in practice. In this method the voters give (weak) ordinal preference ballots which are used to define the weighted majority graph of direct comparisons between pairs of candidates. The choice of the winner comes from indirect comparisons in the graph, and more specifically from considering directed paths instead of direct comparisons between candidates. When the input is the weighted majority graph, to our knowledge, the fastest algorithm for computing all winners in the Schulze method uses a folklore reduction to the All-Pairs Bottleneck Paths (APBP) problem and runs in O(m2.69) time, wherem is the number of candidates. It is an interesting open question whether this can be improved. Our first result is a combinatorial algorithm with a nearly quadratic running time for computing all winners. This running time is essentially optimal as it is nearly linear in the size of the weighted majority graph. If the input to the Schulze winners problem is not the weighted majority graph but the preference profile, then constructing the weighted majority graph is a bottleneck that increases the running time significantly; in the special case when there arem candidates and n = O(m) voters, the running time is O(m2.69), or O(m2.5) if there is a nearly-linear time algorithm for multiplying dense square matrices. To address this bottleneck, we prove a formal equivalence between the well-studied Dominance Product problem and the problem of computing the weighted majority graph. As the Dominance Product problem is believed to require at least time r 2.5-o(1) on r x r matrices, our equivalence implies that constructing the weighted majority graph in O(m2.499) time form candidates and n = O(m) voters would imply a breakthrough in the study of "intermediate" problems [Lincoln et al., 2020] in fine-grained complexity. We prove a similar connection between the so called Dominating Pairs problem and the problem of verifying whether a given candidate is a winner. Our paper is the first to bring fine-grained complexity into the field of computational social choice. Previous approaches say nothing about lower bounds for problems that already have polynomial time algorithms. By bringing fine-grained complexity into the picture we can identify voting protocols that are unlikely to be practical for large numbers of candidates and/or voters, as their complexity is likely, say at least cubic. [ABSTRACT FROM AUTHOR]

This paper introduces a unified framework for stable matching, which nests the traditional definition of stable matching in finite markets and the continuum definition of stable matching from Azevedo and Leshno (2016) as special cases. Within this framework, I identify a novel continuum model, which makes individual-level probabilistic predictions. This new model always has a unique stable outcome, which can be found using an analog of the Deferred Acceptance algorithm. The crucial difference between this model and that of Azevedo and Leshno (2016) is that they assume that the amount of student interest at each school is deterministic, whereas my proposed alternative assumes that it follows a Poisson distribution. As a result, this new model accurately predicts the simulated distribution of cutoffs, even for markets with only ten schools and twenty students. This model generates new insights about the number and quality of matches. When schools are homogeneous, it provides upper and lower bounds on students' average rank, which match results from Ashlagi, Kanoria and Leshno (2017) but apply to more general settings. This model also provides clean analytical expressions for the number of matches in a platform pricing setting considered by Marx and Schummer (2021). [ABSTRACT FROM AUTHOR]

We study the problem of finding optimal correlated equilibria of various sorts: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). This is NP-hard in the general case and has been studied in special cases, most notably triangle-free games[2], which include all two-player games with public chance moves. However, the general case is not well understood, and algorithms usually scale poorly. In this paper, we make two primary contributions. First, we introduce the correlation DAG, a representation of the space of correlated strategies whose structure and size are dependent on the specific solution concept desired. It extends the team belief DAG of Zhang et al. [3] to general-sum games. For each of the three solution concepts, its size depends exponentially only on a parameter related to the information structure of the game. We also prove a fundamental complexity gap: while our size bounds for NFCCE are similar to those achieved in the case of team games by Zhang et al. [3], this is impossible to achieve for the other two concepts under standard complexity assumptions. Second, we propose a two-sided column generation approach to compute optimal correlated strategies in extensive-form games. Our algorithm improves upon the one-sided approach of Farina et al. [1] by means of a new decomposition of correlated strategies which allows players to re-optimize their sequence-form strategies with respect to correlation plans which were previously added to the support. Experiments show that our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria, and that our two families of approaches have complementary strengths: the correlation DAG is fast when the parameter is small and the two-sided column generation approach is superior when the parameter is large. For team games, we show that the two-sided column generation approach vastly outperforms standard column generation approaches, making it the state of the art algorithm when the parameter is large. Along the way, we also introduce two new benchmark games: a trick-taking game that emulates the endgame phase of the card game bridge, and a ride-sharing game, where two drivers traversing a graph are competing to reach specific nodes and serve requests. The full version is available at: https://arxiv.org/abs/2203.07181 [ABSTRACT FROM AUTHOR]

Motivated by a variety of online matching platforms, we consider demand and supply units which are located i.i.d. in d-dimensional space, and each demand unit needs to be matched with a supply unit. The goal is to minimize the expected average distance between matched pairs (the "cost"). We model dynamic arrivals of one or both of demand and supply with uncertain locations of future arrivals, and characterize the scaling behavior of the achievable cost in terms of system size (number of supply units), as a function of the dimension d. Our achievability results are backed by concrete matching algorithms. Across cases, we find that the platform can achieve cost (nearly) as low as that achievable if the locations of future arrivals had been known beforehand. Furthermore, in all cases except one, cost nearly as low as the expected distance to the nearest neighboring supply unit is achievable, i.e., the matching constraint does not cause an increase in cost either. The aberrant case is where only demand arrivals are dynamic, and space is one-dimensional d=1; excess supply significantly reduces cost in this case. We now elaborate a little on our settings and results. We study the following three settings: (i) Static matching between N demand units and N+M supply units, where all demand units must be matched. (ii) A semi-dynamic model where N+M supply units are present beforehand and N demand units arrive sequentially and must be matched immediately. (iii) A fully dynamic model where there are always m supply units present in the system, one supply and one demand unit arrive in each period, and the demand must be matched immediately. We show that one can achieve nearly the same cost under the semi-dynamic model as under the static model, despite uncertainty about the future, and that, under these two models, d=1 is the only case where cost far exceeds the expected distance to the nearest neighboring supply unit (which is Θ(1/N1/d)) and where adding excess supply M substantially reduces cost (by smoothing stochastic fluctuations at larger spatial length scales). In the fully dynamic model, we show that, remarkably, for all d we can achieve a cost only slightly more than the optimistic expected distance to the nearest neighbor Θ(1/m1/d). Thus, excess supply m reduces cost in the fully dynamic model for all d by reducing the distance to the nearest neighbor. This is a fundamentally different phenomenon than that seen in the other two models, where -- only for d=1 -- excess supply reduces cost while leaving the distance to the nearest neighbor unchanged. Our achievability results are based on analysis of a certain "Hierarchical Greedy" algorithm which separately handles stochastic demand-supply imbalances at different length scales. The full version of the paper can be found at https://arxiv.org/abs/2105.07329. [ABSTRACT FROM AUTHOR]

Firms engaged in electronic commerce increasingly rely on predictive analytics via machine-learning algorithms to drive a wide array of managerial decisions. The tuning of many standard machine learning algorithms can be understood as trading off bias (i.e., accuracy) with variance (i.e., precision) in the algorithm's predictions. The goal of this paper is to understand how competition between firms affects their strategic choice of such algorithms. To this end, we model the interaction of two firms choosing learning algorithms as a game and analyze its equilibria. Absent competition, players care only about the magnitude of predictive error and not its source. In contrast, our main result is that with competition, players prefer to incur error due to variance rather than due to bias, even at the cost of higher total error. In addition, we show that competition can have counterintuitive implications---for example, reducing the error incurred by a firm's algorithm can be harmful to that firm---but we provide conditions under which such phenomena do not occur. In addition to our theoretical analysis, we also validate our insights by applying our metrics to a publicly available data set. [ABSTRACT FROM AUTHOR]

As the economy digitizes, menu costs fall, and firms can more easily monitor prices. These trends have led to the rise of automatic pricing tools. We employ a novel e-commerce dataset to examine the potential implications of these developments on price competition. We provide evidence from an RDD that the immediate impact of automatic pricing is a significant decline in prices. However, repricers have developed strategies to avoid the stark competitive realities of Bertrand-Nash competition. By employing plausibly exogenous variation in the execution of repricing strategies, we find that 'resetting' strategies (which regularly raise prices, e.g., at night) effectively coax competitors to raise their prices. While the resulting patterns of cycling prices are reminiscent of Maskin-Tirole's Edgeworth cycles, a model of equilibrium in delegated strategies fits the data better. This model suggests that if the available repricing technology remains fixed, cycling will increase, and prices could rise significantly in the future. [ABSTRACT FROM AUTHOR]

In this paper, we study the effectiveness and generalizability of techniques for classifying partisanship and ideology from text in the context of US politics. In particular, we are interested in how well measures of partisanship transfer across domains as well as the potential to rely upon measures of partisan intensity as a proxy for political ideology. We construct novel datasets of English texts from (1) the Congressional Record, (2) prominent conservative and liberal media websites, and (3) conservative and liberal wikis, and apply text classification algorithms to evaluate domain specificity via a domain adaptation technique. Surprisingly, we find that the cross-domain learning performance, benchmarking the ability to generalize from one of these datasets to another, is in general poor, even though the algorithms perform very well in within-dataset cross-validation tests. While party affiliation of legislators is not predictable based on models learned from other sources, we do find some ability to predict the leanings of the media and crowds-sourced websites based on models learned from the Congressional Record. This predictivity is different across topics, and itself a priori predictable based on within-topic cross-validation results. Temporally, phrases tend to move from politicians to the media, helping to explain this predictivity. Finally, when we compare legislators themselves across different media (the Congressional Record and press releases), we find that while party affiliation is highly predictable, within-party ideology is completely unpredictable. Legislators are communicating different messages through different channels while clearly signaling party identity systematically across all channels. Choice of language is a clearly strategic act, among both legislators and the media, and we must therefore proceed with extreme caution in extrapolating from language to partisanship or ideology across domains. [ABSTRACT FROM AUTHOR]

This paper presents a new primal-dual method for computing an equilibrium of generalized (continuous) Nash game (referred to as generalized Nash equilibrium problem (GNEP)) where each player's feasible strategy set depends on the other players' strategies. The method is based on a new form of Lagrangian function with a quadratic approximation. First, we reformulate a GNEP as a saddle point computation problem using the new Lagrangian and establish equivalence between a saddle point of the Lagrangian and an equilibrium of the GNEP. We then propose a simple algorithm that is convergent to the saddle point. Furthermore, we establish global convergence by assuming that the Lagrangian function satisfies the Kurdyka-Łojasiewicz property. A distinctive feature of our analysis is to make use of the new Lagrangian as a potential function to guide the iterate convergence, which is based on the idea of turning a descent method into a multiplier method. Our method has two novel features over existing approaches: (i) it requires neither boundedness assumptions on the strategy set and the set of multipliers of each player, nor any boundedness assumptions on the iterates generated by the algorithm; (ii) it leads to a Jacobi-type decomposition scheme, which, to the best of our knowledge, is the first development of a distributed algorithm to solve a general class of GNEPs. Numerical experiments are performed on benchmark test problems, and the results demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We consider the problem of aggregating individual preferences over alternatives into a social ranking. A key feature of the problems that we consider---and the one that allows us to obtain positive results, in contrast to negative results such as Arrow's Impossibililty Theorem---is that the alternatives to be ranked are outcomes of a competitive process. Examples include rankings of colleges or academic journals. The foundation of our ranking method is that alternatives that an agent desires---those that they have been rejected by---should be ranked higher than the one they receive. We provide a mechanism to produce a social ranking given any preference profile and outcome assignment, and characterize this ranking as the unique one that satisfies certain desirable axioms. A full version of this paper can be found at: https://arxiv.org/abs/2205.11684. [ABSTRACT FROM AUTHOR]

A common problem in modern web-services revolves around constructing personalized offer sets (or assortments) for users with the objective of optimizing some objective related to the user's experience with the service. Recommendation problems (such as those faced by services such as Netflix) represent a canonical version of such a problem. Assortment optimization problems (as faced by online retailers) are another common example. Rigorous latency constraints are an important practical consideration when building algorithms to construct optimized offer sets. A large-scale study recently showed that a 100ms delay in loading page content can result in a decrease in conversion of up to 7%1. When taken together with the vast size of the product universe (which can run to the tens of millions), such constraints place severe limitations on what a real-time algorithm to construct an optimized offer can do in practice. As such, practically implementable algorithms for real-time offer set optimization at scale must be sub-linear in the size of the universe of potential products. The dynamic nature of the product universe limits the use of pre-computation. Moreover, distributional models of the user further restrict our ability to exhaustively pre-compute optimal offer sets. As a result, the dominant approach today to building optimized offer sets in real-time relies on the design of so-called approximate nearest neighbor (ANN) algorithms. Succinctly, such algorithms leverage metric-space representations of users and products wherein the distance between a user and product is inversely related to how attractive the product is to the user. Whereas such a metric space representation may be constructed offline, the real-time problem then consists of identifying a point in the metric space that corresponds to the user, and finding the k products in the metric space that are nearest to that user in time sub-linear in the number of products. This problem is well-solved both theoretically and practically. Now an economically grounded approach to constructing an optimal offer-set would typically rely on modeling the user's utility for various products. An offer set constructed assuming that a user made choices to maximize utility would then seek not just to pick products that are likely interesting to the user but would further seek to account for substitution and complementarity effects. There is by now a vast literature dedicated to the estimation of models of choice as well as the associated assortment optimization problems given such models. The assortment optimization algorithms developed in this context are, while typically efficient, not sub-linear. On the other hand, the ANN paradigm while sub-linear is typically unable to account for assortment effects in a principled fashion which typically results in a slew of ad-hoc algorithmic tweaks. Here, we seek to begin bridging this gap. The present paper seeks to develop sub-linear time algorithms for offer-set optimization while allowing for rich, economically grounded models of customer choice. Specifically, like is typical in the ANN paradigm, we are endowed with a metric space. We are given a universe V of n products, wherein each product v ∈ V is a point in the metric space. Similarly, a user U is a random point in this space. Our objective is to solve, in sub-linear time, a problem of the form ... where the expectation is over U. The principle assumptions we place on the functions f(·,U) are that we require these functions be sub-modular and further that f({v},U) be non-increasing in the distance d(U,v). This framework is quite flexible and immediately captures two problems of key interest in assortment optimization: * Finding an assortment with maximum conversion probability (i.e. the probability of a click/purchase) under any random utility choice model. * Finding an assortment which maximizes the revenue under the Mixed Multinomial Logit Model under some assumptions on the range of price of products. Note that any random utility choice model can be approximated to any desired level of precision by the mixed multinomial logit model. Our primary contribution is a sub-linear time algorithm to solve the optimization problem above with uniform performance guarantees. Our key algorithmic contribution is a procedure to construct a specific sub-linear sized subset of products, in sub-linear time, via an approach we dub locality-sensitive sampling. Locality-sensitive sampling is a simple idea motivated by the same locality-sensitive hash functions that underly ANN algorithms. The set we construct enjoys the property that the optimal value of our optimization problem restricted to this set is close to the optimal value of the optimization problem over all products. As such, we then simply solve our optimization problem over this restricted set. A greedy algorithm trivially guarantees both a sub-linear run-time and a constant factor approximation. We also present an empirical study on a large-scale corpus of page-view data (the dataset contains two billion page views of seven hundred million unique users) that establishes the value of our procedure. [ABSTRACT FROM AUTHOR]

We consider the problem of learning the preferences of a heterogeneous population by observing choices from an assortment of products, ads, or other offerings. Our observation model takes a form common in assortment planning applications: each arriving customer is offered an assortment consisting of a subset of all possible offerings; we observe only the assortment and the customer's single choice. In this paper we propose a mixture choice model with a natural underlying low-dimensional structure, and show how to estimate its parameters. In our model, the preferences of each customer or segment follow a separate parametric choice model, but the underlying structure of these parameters over all the models has low dimension. We show that a nuclear-norm regularized maximum likelihood estimator can learn the preferences of all customers using a number of observations much smaller than the number of item-customer combinations. This result shows the potential for structural assumptions to speed up learning and improve revenues in assortment planning and customization. We provide a specialized factored gradient descent algorithm and study the success of the approach empirically. [ABSTRACT FROM AUTHOR]

This paper presents the first polynomial-time algorithm for position and matroid auction environments that learns, from samples from an unknown distribution, an auction with expected revenue arbitrarily close to the maximum possible. In contrast to most previous work, our results do not assume that the unknown distribution is regular, and require only that the distribution does not have an extremely heavy tail (a necessary assumption for any non-trivial results). Our performance guarantee is with respect to the strongest possible benchmark, the Myerson-optimal auction. Learning a near-optimal auction for an irregular distribution is technically challenging because it requires learning the appropriate "ironed intervals," a delicate global property of the distribution. [ABSTRACT FROM AUTHOR]

I introduce a class of algorithms called Deferred Acceptance with Compensation Chains (DACC). DACC algorithms generalize the DA algorithms by Gale and Shapley [1962] by allowing both sides of the market to make offers. The main result is a characterization of the set of stable matchings: a matching is stable if and only if it is the outcome of a DACC algorithm. [ABSTRACT FROM AUTHOR]

In this paper we initiate the study of financial asset design with fairness as an explicit goal. We consider a variation on the classical problem of optimal portfolio design. In our setting, an individual consumer is specified by her risk tolerance, which corresponds to the variance in returns she is willing to accept in exchange for higher expected returns. We must design a (small) collection of portfolios and assign each consumer to a portfolio at lower or approximately equal risk than her tolerance. Fairness is imposed by demanding that the portfolios designed do not discriminate (in terms of expected returns) against less wealthy clients (or other specified protected groups). Our main results are algorithms for optimal and near-optimal portfolio design for both social welfare and fairness objectives, both with and without assumptions on the underlying group structure. We describe an efficient algorithm based on an internal two-player zero-sum game that learns near-optimal fair portfolios ex ante and show experimentally that it can be used to obtain a small set of fair portfolios ex post as well. For the special but natural case in which group structure coincides with risk tolerances (which models the reality that wealthy consumers generally tolerate greater risk), we give an efficient and optimal fair algorithm. We also provide generalization guarantees for the underlying risk distribution that has no dependence on the number of portfolios and illustrate the theory with simulation results. [ABSTRACT FROM AUTHOR]

The secretary problem is probably the purest model of decision making under uncertainty. In this paper we ask which advice can we give the algorithm to improve its success probability? We propose a general model that unifies a broad range of problems: from the classic secretary problem with no advice, to the variant where the quality of a secretary is drawn from a known distribution and the algorithm learns each candidate's quality on arrival, to more modern versions of advice in the form of samples, to an ML-inspired model where a classifier gives us noisy signal about whether or not the current secretary is the best on the market. Our main technique is a factor revealing LP that captures all of the problems above. We use this LP formulation to gain structural insight into the optimal policy. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries' qualities are drawn from a known distribution, and a new noisy binary advice model. [ABSTRACT FROM AUTHOR]

In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular search auction is the product of a base bid and bid adjustments that are dependent on features of the search (for example, the geographic location of the user, or the platform on which the search is conducted). We consider the task faced by the advertiser when setting these bid adjustments, and establish a foundational optimization problem that captures the core difficulty of bidding under this language. We give matching algorithmic and approximation hardness results for this problem; these results are against an information-theoretic bound, and thus have implications on the power of the multiplicative bidding language itself. Inspired by empirical studies of search engine price data, we then codify the relevant restrictions of the problem, and give further algorithmic and hardness results. Our main technical contribution is an O(log n)-approximation for the case of multiplicative prices and monotone values. We also provide empirical validations of our problem restrictions, and test our algorithms on real data against natural benchmarks. Our experiments show that they perform favorably compared with the baseline. [ABSTRACT FROM AUTHOR]

Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task’s requester, and may be adjusted based on the quality of the completed work, for example, through the use of “bonus” payments. In this paper, we study the requester’s problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each “arm” representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treat- ing each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We provide a full analysis of this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization(which is the only competing approach in the literature). [ABSTRACT FROM AUTHOR]

Technological evolution, so central to the progress of humanity in recent decades, is the process of constantly introducing new technologies to replace old ones. A new technology does not necessarily mean a better technology and so should not always be embraced. How can society learn which novelties present actual improvements over the existing technology? Whereas the quality of status-quo technology is well known, the new one is a pig in a poke. With sufficiently many individuals willing to explore the new technology society can learn whether it is indeed an improvement. However, self motivated agents, often, do not agree to explore. This is true, in particular, if agents observed some predecessors that were disappointed from the new technology. Inspired by the classical multi-armed bandit model we study a setting where agents arrive sequentially and must pull one of two arms in order to receive a reward - a risky arm (representing the new technology) and a safe arm (representing the existing one). A central planner must induce sufficiently many agents to experiment with the risky arm. The central planner observes the actions and rewards of all agents while the agents themselves have partial observation. For the setting where each agent observes his predecessor we provide the central planner with a recommendation algorithm that is (almost) incentive compatible and facilitates social learning. [ABSTRACT FROM AUTHOR]

Managing perishable inventory, such as blood stock awaiting use by patients in need, has been a topic of research for decades. This has been investigated across several disciplines: medical and social scientists have investigated who donates blood, how frequently, and why; management science researchers have long studied the blood supply chain from a logistical perspective. Yet global demand for blood still far exceeds supply, and unmet need is greatest in low- and middle-income countries. Both academics and policy experts suggest that large-scale coordination is necessary to alleviate demand for donor blood. Using the recently deployed Facebook Blood Donation tool, we conduct the first large-scale algorithmic matching of blood donors with donation opportunities. In both simulations and real experiments we match potential donors with opportunities, guided by a machine learning model trained on prior observations of donor behavior. While measuring actual donation rates remains a challenge, we measure donor action (i.e., calling a blood bank or making an appointment) as a proxy for actual donation. Simulations suggest that even a simple matching strategy can increase donor action rate by 10-15%; a pilot experiment with real donors finds a slightly smaller increase of roughly 5%. While overall action rates remain low, even this modest increase among donors in a global network corresponds to many thousands of more potential donors taking action toward donation. Further, observing donor action on a social network can shed light onto donor behavior and response to incentives. Our initial findings align with several observations made in the medical and social science literature regarding donor behavior. Our full paper is available as a pre-print online.1 [ABSTRACT FROM AUTHOR]

The problem of pricing the cloud has attracted much recent attention due to the widespread use of cloud computing and cloud services. From a theoretical perspective, several mechanisms that provide strong efficiency or fairness guarantees and desirable incentive properties have been designed. However, these mechanisms often rely on a rigid model, with several parameters needing to be precisely known in order for the guarantees to hold. In this paper, we consider a stochastic model and show that it is possible to obtain good welfare and revenue guarantees with simple mechanisms that do not make use of the information on some of these parameters. [ABSTRACT FROM AUTHOR]

Algorithms are increasingly used to guide consequential decisions, such as who should be granted bail or be approved for a loan. Motivated by growing empirical evidence, regulators are concerned about the possibility that the errors of these algorithms differ sharply across subgroups of the population. What are the tradeoffs between accuracy and fairness, and how do these tradeoffs depend on the inputs to the algorithm? We propose a model in which a designer chooses an algorithm that maps observed inputs into decisions, and introduce a fairness-accuracy Pareto frontier. We identify how the algorithm's inputs govern the shape of this frontier, showing (for example) that access to group identity reduces the error for the worse-off group everywhere along the frontier. We then apply these results to study an "input-design" problem where the designer controls the algorithm's inputs (for example, by legally banning an input), but the algorithm itself is chosen by another agent. We show that: (1) all designers strictly prefer to allow group identity if and only if the algorithm's other inputs satisfy a condition we call group-balance; (2) all designers strictly prefer to allow any input (including potentially biased inputs such as test scores) so long as group identity is permitted as an input, but may prefer to ban it when group identity is not. [ABSTRACT FROM AUTHOR]

We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on the real line, but other results of ours are more general. A question closely related to candidate selection is that of minimizing the sum of distances for facility location. The difference is that in our setting there is a fixed set of candidates, whereas the large body of work on facility location considers every point in the metric space to be a possible candidate. This setting gives rise to three types of candidate selection mechanisms which differ in the granularity of their input space (single candidate, ranking and location mechanisms). We study the relationships between these three classes of mechanisms. While it may seem that Black's 1948 median algorithm is optimal for candidate selection on the line, this is not the case. We give matching upper and lower bounds for a variety of settings. In particular, when candidates and voters are on the line, our universally truthful spike mechanism gives a [tight] approximation of two. When assessing candidate selection mechanisms, we seek several desirable properties: (a) efficiency (minimizing the social cost) (b) truthfulness (dominant strategy incentive compatibility) and (c) simplicity (a smaller input space). We quantify the effect that truthfulness and simplicity impose on the efficiency. [ABSTRACT FROM AUTHOR]

Gale and Sotomayor [1985] have shown that in the Gale-Shapley matching algorithm [1962], the proposed-to side W (referred to as women there) can strategically force the W-optimal stable matching as theM-optimal one by truncating their preference lists, each woman possibly blacklisting all but one man. As Gusfield and Irving have already noted in 1989, no results are known regarding achieving this feat by means other than such preference-list truncation, i.e. by also permuting preference lists. We answer Gusfield and Irving's open question by providing tight upper bounds on the amount of blacklists and their combined size, that are required by the women to force a given matching as the M-optimal stable matching, or, more generally, as the unique stable matching. Our results show that the coalition of all women can strategically force any matching as the unique stable matching, using preference lists in which at most half of the women have nonempty blacklists, and in which the average blacklist size is less than 1. This allows the women to manipulate the market in a manner that is far more inconspicuous, in a sense, than previously realized. When there are less women than men, we show that in the absence of blacklists for men, the women can force any matching as the unique stable matching without blacklisting anyone, while when there are more women than men, each to-be-unmatched woman may have to blacklist as many as all men. Together, these results shed light on the question of how much, if at all, do given preferences for one side a priori impose limitations on the set of stable matchings under various conditions. All of the results in this paper are constructive, providing efficient algorithms for calculating the desired strategies. [ABSTRACT FROM AUTHOR]

We investigate properties of Thompson Sampling in the stochastic multi-armed bandit problem with delayed feedback. In a setting with i.i.d delays, we establish to our knowledge the first regret bounds for Thompson Sampling with arbitrary delay distributions, including ones with unbounded expectation. Our bounds are qualitatively comparable to the best available bounds derived via ad-hoc algorithms, and only depend on delays via selected quantiles of the delay distributions. Furthermore, in extensive simulation experiments, we find that Thompson Sampling outperforms a number of alternative proposals, including methods specifically designed for settings with delayed feedback. [ABSTRACT FROM AUTHOR]

We study the design of a class of incentive mechanisms that can effectively prevent cheating in a strategic classification and regression problem. A conventional strategic classification or regression problem is modeled as a Stackelberg game, or a principal-agent problem between the designer of a classifier (the principal) and individuals subject to the classifier's decisions (the agents), potentially from different demographic groups. The former benefits from the accuracy of its decisions, whereas the latter may have an incentive to game the algorithm into making favorable but erroneous decisions. While prior works tend to focus on how to design an algorithm to be more robust to such strategic maneuvering, this study focuses on an alternative, which is to design incentive mechanisms to shape the utilities of the agents and induce effort that genuinely improves their skills, which in turn benefits both parties in the Stackelberg game. Specifically, the principal and the mechanism provider (which could also be the principal itself) move together in the first stage, publishing and committing to a classifier and an incentive mechanism. The agents are (simultaneous) second movers and best respond to the published classifier and incentive mechanism. When an agent's strategic action merely changes its observable features, it hurts the performance of the algorithm. However, if the action leads to improvement in the agent's true label, it not only helps the agent achieve better decision outcomes, but also preserves the performance of the algorithm. We study how a subsidy mechanism can induce improvement actions, positively impact a number of social well-being metrics, such as the overall skill levels of the agents (efficiency) and positive or true positive rate differences between different demographic groups (fairness). [ABSTRACT FROM AUTHOR]

We consider the problem of planning with participation constraints introduced in[24]. In this problem, a principal chooses actions in a Markov decision process, resulting in separate utilities for the principal and the agent. However, the agent can and will choose to end the process whenever his expected onward utility becomes negative. The principal seeks to compute and commit to a policy that maximizes her expected utility, under the constraint that the agent should always want to continue participating. We provide the first polynomial-time exact algorithm for this problem for finite-horizon settings, where previously only an additive ε-approximation algorithm was known. Our approach can also be extended to the (discounted) infinite-horizon case, for which we give an algorithm that runs in time polynomial in the size of the input and log(1/ε), and returns a policy that is optimal up to an additive error of ε. [ABSTRACT FROM AUTHOR]

We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ∈ MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 3/4-MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a 3/4-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (3/4 + 1/12n)-MMS allocation. This considerably improves the approximation guarantee for small n. We note that there are works, e.g., [1, 4], exploring better approximation factors for a small number of agents. We note that 3/4 was the best factor known for n > 4. Our algorithms are extremely simple. First, we describe the basic algorithm that shows the existence of 3/4-MMS allocations. Since MMS values are scale-invariant, we scale valuations to make each agent's MMS value 1. Then, we assign high-value items to agents, who value them at least 3/4, with a simple greedy approach based on the pigeonhole principle, and remove the assigned items and the agents receiving these items from further consideration. This reduces the number of high-value items to be at most 2n', where n' is the number of remaining agents. These greedy assignments massively simplify allocation of high-value items, which was the most challenging part of previous algorithms. Next, we prepare n' bags, one for each remaining agent, and put at most two high-value items in each bag. Then, we add low-value items on top of each of these bags one by one using a bag-filling procedure until the value of bag for some agent is at least 3/4. The main technical challenge here is to show that there are enough low-value items to give every agent a bag they value at least 3/4. Next, we extend the basic algorithm to compute a 3/4-MMS allocation without any need to compute the actual MMS values. Here, we define a notion of tentative assignments and a novel way for updating the MMS upper bound. For each agent, we use the average value, that is the value of all items divided by the number of agents, as an upper bound of her MMS value. The only change from the basic algorithm is that some of the greedy assignments are tentative, i.e., they are valid only if the current upper bound of the MMS values is tight enough. We show that this can be checked by using the total valuation of low-value items. If the upper bounds are not tight enough for some agents, then we update the MMS value of such an agent and repeat. We show that we do not need to update the MMS upper bounds more than O(n³) times before we have a good upper bound on all MMS values. Then, we show that the same bag filling procedure, as in the basic algorithm, satisfy every remaining agent. The running time of the entire algorithm is O(nm(n4 + log m)). We also extend the basic algorithm to show the existence of (3/4 + 1/12n)-MMS allocations. The entire algorithm remains exactly the same but with an involved analysis. The analysis is tricky in this case, so we add a set of dummy items to make proofs easy and more intuitive. We use these items to make up for the extra loss for the remaining agents due to the additional factor, and, of course, these items are not assigned to any agent in the algorithm. [ABSTRACT FROM AUTHOR]

Kakade, Kearns, and Ortiz (KKO) introduce a graph-theoretic generalization of the classic Arrow--Debreu (AD) exchange economy. Despite its appeal as a networked version of AD, we argue that the KKO model is too local, in the sense that goods cannot travel more than one hop through the network. We introduce an alternative model in which agents may purchase goods on credit in order to resell them. In contrast to KKO, our model allows for long-range trade, and yields equilibria in more settings than KKO, including sparse endowments. Our model smoothly interpolates between the KKO and AD equilibrium concepts: we recover KKO when the resale capacity is zero, and recover AD when it is sufficiently large. We give general equilibrium existence results, and an auction-based algorithm to compute approximate equilibria when agent utilities satisfy the weak gross-substitutes property. [ABSTRACT FROM AUTHOR]

We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution schemes (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, pricing-based prophet inequalities with comparable competitive ratios are unknown. [ABSTRACT FROM AUTHOR]

We consider a combinatorial variant of the classical ski rental problem -- which we call combinatorial ski rental -- where multiple resources are available to purchase and to rent, and are demanded online. Moreover, the costs of purchasing and renting are potentially combinatorial. The dual problem of combinatorial ski rental, which we call combinatorial online bipartite matching, generalizes the classical online bipartite matching problem into a form where constraints, induced by both offline and online vertices, can be combinatorial. We give a 2-competitive (resp. e/(e - 1)-competitive) deterministic (resp. randomized) algorithm for combinatorial ski rental, and an e/(e - 1)-competitive algorithm for combinatorial online bipartite matching. All these ratios are optimal given simple lower bounds inherited from the respective well-studied special cases. We also prove information-theoretic impossibility of constant-factor algorithms when any part of our assumptions is considerably relaxed. [ABSTRACT FROM AUTHOR]

We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an underlying optimization problem, the goal is to simulate an incentive compatible mechanism. The mechanism will be evaluated on its expected welfare, relative to the algorithm provided, and its complexity is measured by the time (and queries) needed to simulate the mechanism on any input. While it is known that black-box reductions are not possible in many prior-free settings, settings with priors appear more promising: there are known reductions for Bayesian incentive compatible (BIC) mechanism design for general classes of welfare maximization problems. This dichotomy begs the question: which mechanism design problems admit black-box reductions, and which do not? Our main result is that black-box mechanism design is impossible under two of the simplest settings not captured by known positive results. First, for the problem of allocating n goods to a single buyer whose valuation is additive and independent across the goods, subject to a downward-closed constraint on feasible allocations, we show that there is no polytime (in n) BIC black-box reduction for expected welfare maximization. Second, for the setting of multiple single-parameter agents--where polytime BIC reductions are known--we show that no polytime reductions exist when the incentive requirement is tightened to Max-In-Distributional- Range. In each case, we show that achieving a sub-polynomial approximation to the expected welfare requires exponentially many queries, even when the set of feasible allocations is known to be downward-closed. [ABSTRACT FROM AUTHOR]