We present a polynomial-time algorithm that computes an ex-ante envy-free lottery over envy-free up to one item (EF1) deterministic allocations. It has the following advantages over a recently proposed algorithm: it does not rely on the linear programming machinery including separation oracles; it is SD-efficient (both ex-ante and ex-post); and the ex-ante outcome is equivalent to the outcome returned by the well-known probabilistic serial rule. As a result, we answer a question raised by Freeman, Shah, and Vaish (2020) whether the outcome of the probabilistic serial rule can be implemented by ex-post EF1 allocations. In the light of a couple of impossibility results that we prove, our algorithm can be viewed as satisfying a maximal set of properties. Under binary utilities, our algorithm is also ex-ante group-strategyproof and ex-ante Pareto optimal. Finally, we also show that checking whether a given random allocation can be implemented by a lottery over EF1 and Pareto optimal allocations is NP-hard.

A principal faces a decision and asks an expert for a recommendation and a probabilistic prediction about what outcome will occur if the recommendation were implemented. The principal then follows the recommendation and observes an outcome. Finally, the principal pays the expert based on the prediction and the outcome, according to some decision scoring rule. In this paper, we characterize decision scoring rules that incentivize the expert to report honestly as ones that can be interpreted as giving or selling the expert shares in the principal's project. Each share pays, e.g., $1 per unit of utility obtained by the principal. Owning these shares makes the expert want to maximize the principal's utility by giving the best-possible recommendation. Furthermore, if shares are offered at a continuum of prices, this makes the expert reveal the value of a share and therefore the expected utility of the principal conditional on following the recommendation.

A two-sided market consists of two sets of agents, each of whom have preferences over the other (Airbnb, Upwork, Lyft, Uber, etc.). We propose and analyze a repeated matching problem, where some set of matches occur on each time step, and our goal is to ensure fairness with respect to the cumulative allocations over an infinite time horizon. Our main result is a polynomial-time algorithm for additive, symmetric (vi(j)=v_j(i)), and binary (v_i(j)∈{a,1}) valuations that both (1)guarantees envy-freeness up to a single match (EF1) and (2) selects a maximum weight matching on each time step. Thus for this class of valuations, fairness can be achieved without sacrificing economic efficiency. This result holds even for dynamic valuations, i.e., valuations that change over time. Although symmetry is a strong assumption, we show that this result cannot be extended to asymmetric binary valuations: (1) and (2) together are impossible even when valuations do not change over time, and for dynamic valuations, even (1) alone is impossible. To our knowledge, this is the first analysis of envy-freeness in a repeated matching setting.

In bandwidth allocation, competing agents wish to transmit data along paths of links in a network, and each agent's utility is equal to the minimum bandwidth she receives among all links in her desired path. Recent market mechanisms for this problem have either focused on only Nash welfare [9], or ignored strategic behavior [21]. We propose a nonlinear variant of the classic trading post mechanism, and show that for almost the entire family of CES welfare functions (which includes maxmin welfare, Nash welfare, and utilitarian welfare), every Nash equilibrium of our mechanism is optimal. We also prove that fully strategyproof mechanisms for this problem are impossible in general, with the exception of maxmin welfare. More broadly, our work shows that even small modi cations (such as allowing nonlinear constraints) can dramatically increase the power of market mechanisms like trading post.

We study market mechanisms for allocating divisible goods to competing agents with quasilinear utilities. For linear pricing (i.e., the cost of a good is proportional to the quantity purchased), the First Welfare Theorem states that Walrasian equilibria maximize the sum of agent valuations. This ensures efficiency, but can lead to extreme inequality across individuals. Many real-world markets - especially for water - use convex pricing instead, often known as increasing block tariffs (IBTs). IBTs are thought to promote equality, but there is a dearth of theoretical support for this claim.

In this paper, we study a simple convex pricing rule and show that the resulting equilibria are guaranteed to maximize a CES welfare function. Furthermore, a parameter of the pricing rule directly determines which CES welfare function is implemented; by tweaking this parameter, the social planner can precisely control the tradeoff between equality and efficiency. Our result holds for any valuations that are homogeneous, differentiable, and concave. We also give an iterative algorithm for computing these pricing rules, derive a truthful mechanism for the case of a single good, and discuss Sybil attacks.

Prior work considering random matching markets has suggested that, when agents have uniformly-distributed preferences, the fraction of agents with incentives to manipulate core-selecting mechanisms generally tends to vanish as markets become large. Contrasting these results, I present a class of models for non-homogeneous agent preferences (drawn from the computer science literature on network structure) that support significant incentives for agents to manipulate matching outcomes, even as markets become large and unbalanced. Specifically, I consider agent preference structures that exhibit locality, with focus on a simple model of spatial locality for the main results. In an appendix, I discuss an extension of these results to a broader class of preference-structure models, with a generalized locality condition. A constructive probabilistic technique, similar to Hassidim et al. [1], shows that a non-vanishing fraction of agents can improve their outcomes by misreporting their true preferences, in a market with simple spatial locality. Simulation results demonstrate that the fraction of such agents is substantial in practice under market specifications between 60 and 12,000 agents. These results contrast prior work which assumed homogeneous preferences, finding a vanishing fraction and little scope for manipulation.

Furthermore, this scope for manipulation corresponds directly to core size and differences in agents' welfare between core outcomes. These results suggest that largeness and cross-side imbalance may be insufficient to explain empirical observations of small cores in matching markets; I discuss alternative explanations.

In load balancing problems there is a set of clients, each wishing to select a resource from a set of permissible ones, in order to execute a certain task. Each resource has a latency function, which depends on its workload, and a client's cost is the completion time of her chosen resource. Two fundamental variants of load balancing problems are selfish load balancing (aka. load balancing games), where clients are non-cooperative selfish players aimed at minimizing their own cost solely, and online load balancing, where clients appear online and have to be irrevocably assigned to a resource without any knowledge about future requests. We revisit both selfish and online load balancing under the objective of minimizing the Nash Social Welfare, i.e., the geometric mean of the clients' costs. To the best of our knowledge, despite being a celebrated welfare estimator in many social contexts, the Nash Social Welfare has not been considered so far as a benchmarking quality measure in load balancing problems. We provide tight bounds on the price of anarchy of pure Nash equilibria and on the competitive ratio of the greedy algorithm under very general latency functions, including polynomial ones. For this particular class, we also prove that the greedy strategy is optimal as it matches the performance of any possible online algorithm.