More Like this

1. Sequential Veto Bargaining With Incomplete Information

   https://doi.org/10.3982/ECTA20658  

   Ali, S. Nageeb; Kartik, Navin; Kleiner, Andreas (January 2023, Econometrica)

   We study sequential bargaining between a proposer and a veto player. Both have single‐peaked preferences, but the proposer is uncertain about the veto player's ideal point. The proposer cannot commit to future proposals. When players are patient, there can be equilibria with Coasian dynamics: the veto player's private information can largely nullify proposer's bargaining power. Our main result, however, is that under some conditions there also are equilibria in which the proposer obtains the high payoff that he would with commitment power. The driving force is that the veto player's single‐peaked preferences give the proposer an option to “leapfrog,” that is, to secure agreement from only low‐surplus types early on to credibly extract surplus from high types later. Methodologically, we exploit the connection between sequential bargaining and static mechanism design. 

   more » « less
2. Optimal Auction Design With Common Values: An Informationally Robust Approach

   https://doi.org/10.3982/ECTA16297  

   Brooks, Benjamin; Du, Songzi (January 2021, Econometrica)

   null (Ed.)

   A profit‐maximizing seller has a single unit of a good to sell. The bidders have a pure common value that is drawn from a distribution that is commonly known. The seller does not know the bidders' beliefs about the value and thinks that beliefs are designed adversarially by Nature to minimize profit. We construct a strong maxmin solution to this joint mechanism design and information design problem, consisting of a mechanism, an information structure, and an equilibrium, such that neither the seller nor Nature can move profit in their respective preferred directions, even if the deviator can select the new equilibrium. The mechanism and information structure solve a family of maxmin mechanism design and minmax information design problems, regardless of how an equilibrium is selected. The maxmin mechanism takes the form of a proportional auction : each bidder submits a one‐dimensional bid, the aggregate allocation and aggregate payment depend on the aggregate bid, and individual allocations and payments are proportional to bids. We report a number of additional properties of the maxmin mechanisms, including what happens as the number of bidders grows large and robustness with respect to the prior over the value. 

   more » « less
3. A Truthful Cardinal Mechanism for One-Sided Matching

   https://doi.org/10.1137/1.9781611975994.129  

   Abebe, Rediet; Cole, Richard; Gkatzelis, Vasilis; Hartline, Jason D. (January 2020, ACM-SIAM Symposium on Discrete Algorithms)

   We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value vij for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the vij values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest. 

   more » « less
4. Nash Social Welfare Approximation for Strategic Agents

   https://doi.org/10.1287/opre.2020.2056  

   Brânzei, Simina; Gkatzelis, Vasilis; Mehta, Ruta (January 2022, Operations Research)

   A central goal in the long literature on fair division is the design of mechanisms that implement fair outcomes, despite the participants’ strategic behavior. We study this question by measuring the fairness of an allocation using the geometric mean of the agents’ values, known as the Nash social welfare (NSW). This objective is maximized by widely known concepts such as the Nash bargaining solution, proportional fairness, and the competitive equilibrium with equal incomes; we focus on (approximately) implementing this objective and analyze the Trading Post mechanism. We consider allocating goods that are substitutes or complements and show that this mechanism achieves an approximation of two for concave utility functions and becomes essentially optimal for complements, where it can reach [Formula: see text] for any [Formula: see text]. Moreover, we show that the Nash equilibria of this mechanism are pure and provide individual fairness in the sense of proportionality. 

   more » « less
5. Multi-agent motion planning using differential games with lexicographic preferences

   Kristina Miller and Sayan Mitra (December 2022, IEEE Conference on Decision and Control)

   Multi-player games with lexicographic cost functions can capture a variety of driving and racing scenarios and under certain conditions are known to have pure-strategy Nash Equilibria. The standard Iterated Best Response (IBR) procedure for finding such equilibria can be slow because, in general, computing the best response for each agent involves solving a non-convex optimization problem. In this paper, we introduce a type of game which uses a lexicographic cost function. We show that for this class of games, the best responses can be effectively computed through piece-wise linear approximations. This in turn enables us to approximate the Nash Equilibria using a linearized version of IBR. We show that the gap between the linear approximations returned by our linearized IBR and the true best response drops asymptotically. We have implemented the algorithm and our experiments show that it can find approximate Nash Equilibria for handful of agents driving in realistic scenarios in less than 10 seconds. 

   more » « less