2020: The 16th Conference on Web and Internet Economics

December 7-11, 2020, Peking University, Beijing


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