In this article, we study the Provision-after-Wait problem in healthcare (Braverman, Chen, and Kannan, 2016). In this setting, patients seek a medical procedure that can be performed by different hospitals of different costs. Each patient has a value for each hospital and a budget-constrained government/planner pays for the expenses of the patients. Patients are free to choose hospitals, but the planner controls how much money each hospital gets paid and thus how many patients each hospital can serve (in one budget period, say, one month or one year). Waiting times are used in order to balance the patients’ demand, and the planner’s goal is to find a stable assignment that maximizes the social welfare while keeping the expenses within the budget. PubDate: Mon, 27 Mar 2017 00:00:00 GMT

We consider a dynamic auction model, where bidders sequentially arrive to the market. The values of the bidders for the item for sale are independently drawn from a distribution, but this distribution is unknown to the seller. The seller offers a personalized take-it-or-leave-it price for each arriving bidder and aims to maximize revenue. We study how well can such sequential posted-price mechanisms approximate the optimal revenue that would be achieved if the distribution was known to the seller. On the negative side, we show that sequential posted-price mechanisms cannot guarantee a constant fraction of this revenue when the class of candidate distributions is unrestricted. PubDate: Mon, 13 Mar 2017 00:00:00 GMT

Abstract: Amos Azaria, David Sarne, Yonatan Aumann

In this article, we study distributed agent matching with search friction in environments characterized by costly exploration, where each agent’s utility from forming a partnership is influenced by some linear combination of the maximum and the minimum among the two agents’ competence. The article provides a cohesive analysis for such case, proving the equilibrium structure for the different min-max linear combinations that may be used. The article presents an extensive equilibrium analysis of such settings, proving three distinct resulting patterns of the acceptance thresholds used by the different agents. The first relates to settings where a greater emphasis is placed on the minimum type, or in the extreme case where the minimum type solely determines the output. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

Two common criticisms of Nash equilibrium are its dependence on very demanding epistemic assumptions and its computational intractability. We study the computational properties of less demanding set-valued solution concepts that are based on varying notions of dominance. These concepts are intuitively appealing, always exist, and admit unique minimal solutions in important subclasses of games. Examples include Shapley’s saddles, Harsanyi and Selten’s primitive formations, Basu and Weibull’s CURB sets, and Dutta and Laslier’s minimal covering set. Based on a unifying framework proposed by Duggan and Le Breton, we formulate two generic algorithms for computing these concepts and investigate for which classes of games and which properties of the underlying dominance notion the algorithms are sound and efficient. PubDate: Tue, 25 Oct 2016 00:00:00 GMT

Abstract: Mallesh M. Pai, Aaron Roth, Jonathan Ullman

In this article, we study infinitely repeated games in settings of imperfect monitoring. We first prove a family of theorems showing that when the signals observed by the players satisfy a condition known as (ε, γ)-differential privacy, the folk theorem has little bite: for values of ε and γ sufficiently small, for a fixed discount factor, any equilibrium of the repeated game involves players playing approximate equilibria of the stage game in every period. Next we argue that in large games (n player games in which unilateral deviations by single players have only a small impact on the utility of other players), many monitoring settings naturally lead to signals that satisfy (ε, γ)-differential privacy for ε and γ tending to zero as the number of players n grows large. PubDate: Wed, 12 Oct 2016 00:00:00 GMT