Web and Internet Economics

In this work we consider general facility location and social choice problems, in which sets of agents \(\mathcal {A}\) and facilities \(\mathcal {F}\) are located in a metric space, and our goal is to assign agents to facilities (as well as choose which facilities to open) in order to optimize the social cost. We form new algorithms to do this in the presence of only ordinal information, i.e., when the true costs or distances from the agents to the facilities are unknown, and only the ordinal preferences of the agents for the facilities are available. The main difference between our work and previous work in this area is that while we assume that only ordinal information about agent preferences is known, we know the exact locations of the possible facilities \(\mathcal {F}\). Due to this extra information about the facilities, we are able to form powerful algorithms which have small distortion, i.e., perform almost as well as omniscient algorithms but use only ordinal information about agent preferences. For example, we present natural social choice mechanisms for choosing a single facility to open with distortion of at most 3 for minimizing both the total and the median social cost; this factor is provably the best possible. We analyze many general problems including matching, k-center, and k-median, and present black-box reductions from omniscient approximation algorithms with approximation factor \(\beta \) to ordinal algorithms with approximation factor \(1+2\beta \); doing this gives new ordinal algorithms for many important problems, and establishes a toolkit for analyzing such problems in the future.

In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. Such games are central in formal verification since they model the interaction between a non-terminating system and its environment. We study bidding games in which the players bid for the right to move the token. Two bidding rules have been defined. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the “bank” rather than the other player. While poorman reachability games have been studied before, we present, for the first time, results on infinite-duration poorman games. A central quantity in these games is the ratio between the two players’ initial budgets. The questions we study concern a necessary and sufficient ratio with which a player can achieve a goal. For reachability objectives, such threshold ratios are known to exist for both bidding rules. We show that the properties of poorman reachability games extend to complex qualitative objectives such as parity, similarly to the Richman case. Our most interesting results concern quantitative poorman games, namely poorman mean-payoff games, where we construct optimal strategies depending on the initial ratio, by showing a connection with random-turn based games. The connection in itself is interesting, because it does not hold for reachability poorman games. We also solve the complexity problems that arise in poorman bidding games.

We study a variant of Vickrey’s classic bottleneck model. In our model there are n agents and each agent strategically chooses when to join a first-come-first-served observable queue. Agents dislike standing in line and they take actions in discrete time steps: we assume that each agent has a cost of 1 for every time step he waits before joining the queue and a cost of \(w>1\) for every time step he waits in the queue. At each time step a single agent can be processed. Before each time step, every agent observes the queue and strategically decides whether or not to join, with the goal of minimizing his expected cost.

In this paper we focus on symmetric strategies which are arguably more natural as they require less coordination. This brings up the following twist to the usual price of anarchy question: what is the main source for the inefficiency of symmetric equilibria? is it the players’ strategic behavior or the lack of coordination?

We present results for two different parameter regimes that are qualitatively very different: (i) when w is fixed and n grows, we prove a tight bound of 2 and show that the entire loss is due to the players’ selfish behavior (ii) when n is fixed and w grows, we prove a tight bound of \(\varTheta \left( \sqrt{\frac{w}{n}}\right) \) and show that it is mainly due to lack of coordination: the same order of magnitude of loss is suffered by any symmetric profile.

Our aim is to design mechanisms that motivate all agents to reveal their predictions truthfully and promptly. For myopic agents, proper scoring rules induce truthfulness. However, when agents have multiple opportunities for revealing information, and take into account long-term effects of their actions, deception and reticence may appear. Such situations have been described in the literature. No simple rules exist to distinguish between the truthful and the untruthful situations, and a determination has been done in isolated cases only. This is of relevance to prediction markets, where the market value is a common prediction, and more generally in informal public prediction forums, such as stock-market estimates by analysts. We describe three different mechanisms that are strategy-proof with non-myopic considerations, and show that one of them, a discounted market scoring rule, meets all our requirements from a mechanism in almost all prediction settings. To illustrate, we extensively analyze a prediction setting with continuous outcomes, and show how our suggested mechanism restores prompt truthfulness where incumbent mechanisms fail.

Given a data-set of consumer behaviour, the Revealed Preference Graph succinctly encodes inferred relative preferences between observed outcomes as a directed graph. Not all graphs can be constructed as revealed preference graphs when the market dimension is fixed. This paper solves the open problem of determining exactly which graphs are attainable as revealed preference graphs in d-dimensional markets. This is achieved via an exact characterization which closely ties the feasibility of the graph to the Matrix Sign Rank of its signed adjacency matrix. The paper also shows that when the preference relations form a partially ordered set with order-dimension k, the graph is attainable as a revealed preference graph in a k-dimensional market.

This paper studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution at equilibrium. This implies that the central controller must have some control over the timing of agent arrivals and departures in order to ensure efficiency of the system at equilibrium. Indeed, we give a complementary result showing that if the central controller is allowed to restore equilibrium after every set of arrivals/departures via improving moves, the eventual equilibrium states reached have exponentially better efficiency.

We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has a budget and additive valuations drawn independently for each item from (non-identical) distributions. We show that when the buyer’s budget is publicly known, the better of selling each item separately and selling the grand bundle extracts a constant fraction of the optimal revenue. When the budget is private, we consider a standard Bayesian setting where buyer’s budget b is drawn from a known distribution B. We show that if b is independent of the valuations and distribution B satisfies monotone hazard rate condition, then selling items separately or in a grand bundle is still approximately optimal. We give a complementary example showing that no constant approximation simple mechanism is possible if budget b can be interdependent with valuations.

We consider the problem of deciding the existence of pure Nash equilibrium and the problem of finding mixed Nash equilibrium in graphical games defined on the two dimensional \(d \times m\) grid graph. Unlike previous works focusing on the computational complexity of centralized algorithms, we study the communication complexity of distributed protocols for these problems, in the setting that each player initially knows only his private input of constant length describing his utility function and each player can only communicate directly with his neighbors. For the pure Nash equilibrium problem, we show that in any protocol, the players in some game must communicate a total of at least \(\varOmega (dm^2)\) bits when \(d \ge \log m\) and at least \(\varOmega (d 2^d m)\) bits when \(d < \log m\). For the mixed Nash equilibrium problem, we show that in any protocol, the players in some game must communicate at least \(\varOmega (d^2 m^2)\) bits in total, and moreover, every player must communicate at least \(\varOmega (dm)\) bits. We also provide protocols with matching or almost matching upper bounds.

The existential theory of the reals (ETR) consists of existentially quantified boolean formulas over equalities and inequalities of real-valued polynomials. We propose the approximate existential theory of the reals (\(\epsilon \)-ETR), in which the constraints only need to be satisfied approximately. We first show that unconstrained \(\epsilon \)-ETR = ETR, and then study the \(\epsilon \)-ETR problem when the solution is constrained to lie in a given convex set. Our main theorem is a sampling theorem, similar to those that have been proved for approximate equilibria in normal form games. It states that if an ETR problem has an exact solution, then it has a k-uniform approximate solution, where k depends on various properties of the formula. A consequence of our theorem is that we obtain a quasi-polynomial time approximation scheme (QPTAS) for a fragment of constrained \(\epsilon \)-ETR. We use our theorem to create several new PTAS and QPTAS algorithms for problems from a variety of fields.

We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer’s information and agents’ valuations. Our results provide insights about the relative power of uniform and non-uniform prices, the relative difficulty of different valuation classes, and the implications of different informational assumptions. Among other results, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices.

We study the performance of anonymous posted-price selling mechanisms for a standard Bayesian auction setting, where n bidders have i.i.d. valuations for a single item. We show that for the natural class of Monotone Hazard Rate (MHR) distributions, offering the same, take-it-or-leave-it price to all bidders can achieve an (asymptotically) optimal revenue. In particular, the approximation ratio is shown to be \(1+O(\ln {\ln {n}}/ \ln {n})\), matched by a tight lower bound for the case of exponential distributions. This improves upon the previously best-known upper bound of \(e/(e-1)\approx 1.58\) for the slightly more general class of regular distributions. In the worst case (over n), we still show a global upper bound of 1.35. We give a simple, closed-form description of our prices which, interestingly enough, relies only on minimal knowledge of the prior distribution, namely just the expectation of its second-highest order statistic.

Suppose that an m-simplex is partitioned into n convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance \(\varepsilon \) from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant m uses \(poly(n, \log \left( \frac{1}{\varepsilon } \right) )\) queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant n uses \(poly(m, \log \left( \frac{1}{\varepsilon } \right) )\) queries. We show via Kakutani’s fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies.

We consider multi-product (m products) Cournot games played by n firms where products are substitutable goods. Such games can arise in network markets and in general is motivated by markets with differentiated goods and differing producer costs that can be arbitrary, especially due to subsidies. We provide strongly polynomial algorithms for computing the Nash equilibrium for Cournot games with quadratic utility functions. To study the inefficiency, we provide a characterization of Nash equilibrium in multi-product oligopolies with concave utilities and uniform substitutability in terms of games with quadratic utilities. We show that the Price of Anarchy in these games is bounded below by 2/3.

Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a choice model in which each consumer selects a utility-maximizing bundle subject to a private valuation function, and study the complexity of the resulting optimization problem. Our main result is an exact algorithm for k-additive valuations, under a model of vertical differentiation in which customers agree on the relative value of each pair of items but differ in their absolute willingness to pay. For valuations that are vertically differentiated but not necessarily k-additive, we show how to obtain constant approximations under a “well-priced” condition, where each product’s price is sufficiently high. We further show that even for a single customer with known valuation, any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS, and that no FPTAS exists even when the valuation is succinctly representable.

We study the problem of a budget limited buyer who wants to buy a set of items, each from a different seller, to maximize her value. The budget feasible mechanism design problem requires the design a mechanism which incentivizes the sellers to truthfully report their cost and maximizes the buyer’s value while guaranteeing that the total payment does not exceed her budget. Such budget feasible mechanisms can model a buyer in a crowdsourcing market interested in recruiting a set of workers (sellers) to accomplish a task for her.

This budget feasible mechanism design problem was introduced by Singer in 2010. We consider the general case where the buyer’s valuation is a monotone submodular function. There are a number of truthful mechanisms known for this problem. We offer two general frameworks for simple mechanisms, and by combining these frameworks, we significantly improve on the best known results, while also simplifying the analysis. For example, we improve the approximation guarantee for the general monotone submodular case from 7.91 to 5; and for the case of large markets (where each individual item has negligible value) from 3 to 2.58. More generally, given an r approximation algorithm for the optimization problem (ignoring incentives), our mechanism is a \(r+1\) approximation mechanism for large markets, an improvement from \(2r^2\). We also provide a mechanism without the large market assumption, where we achieve a \(4r+1\) approximation guarantee. We also show how our results can be used for the problem of a principal hiring in a Crowdsourcing Market to select a set of tasks subject to a total budget.

Consider the seller’s problem of finding optimal prices for her n (divisible) goods when faced with a set of m consumers, given that she can only observe their purchased bundles at posted prices, i.e., revealed preferences. We study both social welfare and profit maximization with revealed preferences. Although social welfare maximization is a seemingly non-convex optimization problem in prices, we show that (i) it can be reduced to a dual convex optimization problem in prices, and (ii) the revealed preferences can be interpreted as supergradients of the concave conjugate of valuation, with which subgradients of the dual function can be computed. We thereby obtain a simple subgradient-based algorithm for strongly concave valuations and convex cost, with query complexity \(O(m^2/\epsilon ^2)\), where \(\epsilon \) is the additive difference between the social welfare induced by our algorithm and the optimum social welfare. We also study social welfare maximization under the online setting, specifically the random permutation model, where consumers arrive one-by-one in a random order. For the case where consumer valuations can be arbitrary continuous functions, we propose a price posting mechanism that achieves an expected social welfare up to an additive factor of \(O(\sqrt{mn})\) from the maximum social welfare. Finally, for profit maximization (which may be non-convex in simple cases), we give nearly matching upper and lower bounds on the query complexity for separable valuations and cost (i.e., each good can be treated independently).

We study opinion formation games based on the Friedkin-Johnsen (FJ) model. We are interested in simple and natural variants of the FJ model that use limited information exchange in each round and converge to the same stable point. As in the FJ model, we assume that each agent i has an intrinsic opinion \(s_i \in [0,1]\) and maintains an expressed opinion \(x_i(t) \in [0,1]\) in each round t. To model limited information exchange, we assume that each agent i meets with one random friend j at each round t and learns only \(x_j(t)\). The amount of influence j imposes on i is reflected by the probability \(p_{ij}\) with which i meets j. Then, agent i suffers a disagreement cost that is a convex combination of \((x_i(t) - s_i)^2\) and \((x_i(t) - x_j(t))^2\).

An important class of dynamics in this setting are no regret dynamics. We show an exponential gap between the convergence rate of no regret dynamics and of more general dynamics that do not ensure no regret. We prove that no regret dynamics require roughly \({\varOmega }(1/\varepsilon )\) rounds to be within distance \(\varepsilon \) from the stable point \(x^*\) of the FJ model. On the other hand, we provide an opinion update rule that does not ensure no regret and converges to \(x^*\) in \({\tilde{O}}(\log ^2(1/\varepsilon ))\) rounds. Finally, we show that the agents can adopt a simple opinion update rule that ensures no regret and converges to \(x^*\) in \(\mathrm {poly}(1/\varepsilon )\) rounds.

We consider the fair division of indivisible items using the maximin shares measure. Recent work on the topic has focused on extending results beyond the class of additive valuation functions. In this spirit, we study the case where the items form an hereditary set system. We present a simple algorithm that allocates each agent a bundle of items whose value is at least 0.3667 times the maximin share of the agent. This improves upon the current best known guarantee of 0.2 due to Ghodsi et al. The analysis of the algorithm is almost tight; we present an instance where the algorithm provides a guarantee of at most 0.3738. We also show that the algorithm can be implemented in polynomial time given a valuation oracle for each agent.

Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In this paper we seek to identify structural properties of instances of stable matching problems which will allow us to design efficient algorithms using elementary techniques. We focus on the setting in which all agents involved in some matching problem can be partitioned into k different types, where the type of an agent determines his or her preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation would arise in practice if agents form preferences solely based on some small collection of agents’ attributes. We also consider a generalisation in which each agent may consider some small collection of other agents to be exceptional, and rank these in a way that is not consistent with their types; this could happen in practice if agents have prior contact with a small number of candidates. We show that (for the case without exceptions), the well-known NP-hard matching problem Max SMTI (that of finding the maximum cardinality stable matching in an instance of stable marriage with ties and incomplete lists) belongs to the parameterised complexity class FPT when parameterised by the number of different types of agents needed to describe the instance. This tractability result can be extended to the setting in which each agent promotes at most one “exceptional” candidate to the top of his/her list (when preferences within types are not refined), but the problem remains NP-hard if preference lists can contain two or more exceptions and the exceptional candidates can be placed anywhere in the preference lists.

In the Byzantine agreement problem, n nodes with possibly different input values aim to reach agreement on a common value in the presence of \(t<n/3\) Byzantine nodes which represent arbitrary failures in the system. This paper introduces a generalization of Byzantine agreement, where the input values of the nodes are preference rankings of three or more candidates. We show that consensus on preferences, which is an important question in social choice theory, complements already known results from Byzantine agreement. In addition, preferential voting raises new questions about how to approximate consensus vectors. We propose a deterministic algorithm to solve Byzantine agreement on rankings under a generalized validity condition, which we call Pareto-Validity. These results are then extended by considering a special voting rule which chooses the Kemeny median as the consensus vector. For this rule, we derive a lower bound on the approximation ratio of the Kemeny median that can be guaranteed by any deterministic algorithm. We then provide an algorithm matching this lower bound. To our knowledge, this is the first non-trivial generalization of multi-valued Byzantine agreement to multiple dimensions which can tolerate a constant fraction of Byzantine nodes.

We study the stable marriage problem in the partial information setting where the agents, although they have an underlying true strict linear order, are allowed to specify partial orders either because their true orders are unknown to them or they are unwilling to completely disclose the same. Specifically, we focus on the case where the agents are allowed to submit strict weak orders and we try to address the following questions from the perspective of a market-designer: (i) How can a designer generate matchings that are robust—in the sense that they are “good” with respect to the underlying unknown true orders? (ii) What is the trade-off between the amount of missing information and the “quality” of solution one can get? With the goal of resolving these questions through a simple and prior-free approach, we suggest looking at matchings that minimize the maximum number of blocking pairs with respect to all the possible underlying true orders as a measure of “goodness” or “quality”, and subsequently provide results on finding such matchings. In particular, we first restrict our attention to matchings that have to be stable with respect to at least one of the completions (i.e., weakly-stable matchings) and show that in this case arbitrarily filling-in the missing information and computing the resulting stable matching can give a non-trivial approximation factor for our problem in certain cases. We complement this result by showing that, even under severe restrictions on the preferences of the agents, the factor obtained is asymptotically tight in many cases. We then investigate a special case, where only agents on one side provide strict weak orders and all the missing information is at the bottom of their preference orders, and show that in this special case the negative result mentioned above can be circumvented in order to get a much better approximation factor; this result, too, is tight in many cases. Finally, we move away from the restriction on weakly-stable matchings and show a general hardness of approximation result and also discuss one possible approach that can lead us to a near-tight approximation bound.

We revisit the classic prophet inequality problem, where the goal is selling a single item to an arriving sequence of buyers whose values are drawn from independent distributions, to maximize the expected allocated value. The usual benchmark is the expected value that an omniscient prophet who knows the future can attain. We diverge from this framework and compare the performance of the best single pricing mechanism with the best optimum online mechanism.

Somewhat surprisingly, we show that the original tight prophet inequality bounds comparing the single-pricing with the optimum offline are tight even when we use the optimum online as a benchmark, both for the identical and non-identical distributions. Moreover, we incorporate linear programming to characterize this benchmark, and show how this approach leads to a modular way of designing prophet inequalities, hence reconstructing the results of [31] and [13] with somewhat simpler proofs.

One of the most celebrated results in mechanism design is Myerson’s characterization of the revenue optimal auction for selling a single item. However, this result relies heavily on the assumption that buyers are indifferent to risk. In this paper we investigate the case where the buyers are risk-loving, i.e. they prefer gambling to being rewarded deterministically. We use the standard model for risk from expected utility theory, where risk-loving behavior is represented by a convex utility function.

We focus our attention on the special case of exponential utility functions. We characterize the optimal auction and show that randomization can be used to extract more revenue than when buyers are risk-neutral. Most importantly, we show that the optimal auction is simple: the optimal revenue can be extracted using a randomized take-it-or-leave-it price for a single buyer and using a loser-pay auction, a variant of the all-pay auction, for multiple buyers. Finally, we show that these results no longer hold for convex utility functions beyond exponential.

Tournament solutions provide methods for selecting the “best” alternatives from a tournament and have found applications in a wide range of areas. Previous work has shown that several well-known tournament solutions almost never rule out any alternative in large random tournaments. Nevertheless, all analytical results thus far have assumed a rigid probabilistic model, in which either a tournament is chosen uniformly at random, or there is a linear order of alternatives and the orientation of all edges in the tournament is chosen with the same probabilities according to the linear order. In this work, we consider a significantly more general model where the orientation of different edges can be chosen with different probabilities. We show that a number of common tournament solutions, including the top cycle and the uncovered set, are still unlikely to rule out any alternative under this model. This corresponds to natural graph-theoretic conditions such as irreducibility of the tournament. In addition, we provide tight asymptotic bounds on the boundary of the probability range for which the tournament solutions select all alternatives with high probability.

In this paper, we present a new routing model with edge priorities. We consider network users that route packages selfishly through a network over time and try to reach their destinations as fast as possible. If the number of packages that want to enter an edge at the same time exceeds the inflow capacity of this edge, edge priorities with respect to the preceding edge solve these conflicts. For this class of games, we show the existence of equilibrium solutions for single-source-single-sink games and we analyze structural properties of these solutions. We present an algorithm that computes Nash equilibria and we prove bounds both on the Price of Stability and on the Price of Anarchy. Moreover, we introduce the new concept of the Price of Mistrust and analyze the connection to earliest arrival flows.

The jobs processed in a specific time-slot cover the server’s activation cost in this slot, with the cost being shared proportionally to the jobs’ weights. Known result on cost-sharing games do not exploit the special interval-structure of the strategy space in our game, and are therefore not tight. We present a complete analysis of equilibrium existence, computation, and inefficiency in real-time scheduling cost-sharing games. Our tight analysis covers various classes of instances, and distinguishes between unilateral and coordinated deviations.