**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