ﻻ يوجد ملخص باللغة العربية
We study combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC14] and its follow-ups) the focus was on analyzing the implications and mitigating their negative consequences. In contrast, in this paper we show how in some cases cognitive biases can be harnessed to obtain better outcomes. Specifically, we study Walrasian equilibria in combinatorial markets. It is well known that Walrasian equilibria exist only in limited settings, e.g., when all valuations are gross substitutes, but fails to exist in more general settings, e.g., when the valuations are submodular. We consider combinatorial settings in which bidders exhibit the endowment effect, that is, their value for items increases with ownership. Our main result shows that when the valuations are submodular, even a mild degree of endowment effect is sufficient to guarantee the existence of Walrasian equilibria. In fact, we show that in contrast to Walrasian equilibria with standard utility maximizing bidders -- in which the equilibrium allocation must be efficient -- when bidders exhibit endowment effect any local optimum can be an equilibrium allocation. Our techniques reveal interesting connections between the LP relaxation of combinatorial auctions and local maxima. We also provide lower bounds on the intensity of the endowment effect that the bidders must have in order to guarantee the existence of a Walrasian equilibrium in various settings.
The market economy deals with many interacting agents such as buyers and sellers who are autonomous intelligent agents pursuing their own interests. One such multi-agent system (MAS) that plays an important role in auctions is the combinatorial aucti
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with respect to a single item. Babaioff et al. [EC18] took a fir
Mechanism design for one-sided markets has been investigated for several decades in economics and in computer science. More recently, there has been an increased attention on mechanisms for two-sided markets, in which buyers and sellers act strategic
We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non
In this note we study the greedy algorithm for combinatorial auctions with submodular bidders. It is well known that this algorithm provides an approximation ratio of $2$ for every order of the items. We show that if the valuations are vertex cover f