Simultaneously Achieving Ex-ante and Ex-post Fairness
Haris Aziz
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 All
Decision Scoring Rules
Caspar Oesterheld and Vincent Conitzer
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 deci... All
Almost Envy-free Repeated Matching in Two-sided Markets
Sreenivas Gollapudi, Kostas Kollias and Benjamin Plaut
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 ad... All
Optimal Nash Equilibria for Bandwidth Allocation
Benjamin Plaut
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 mechan... All
Counteracting Inequality in Markets via Convex Pricing
Ashish Goel and Benjamin Plaut
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 -... All
Large random matching markets with localized preference structures can exhibit large cores
Ross Rheingans-Yoo
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 ... All
Nash Social Welfare in Selfish and Online Load Balancing
Vittorio Bilò, Gianpiero Monaco, Luca Moscardelli and Cosimo Vinci
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... All