Social effect on Envy-Freeness and discrimination of prices in multi-unit markets

Multi-unit markets model the real-world scenario in which a seller is willing to sell multiple copies of a single good to many buyers, like in the case of commodities, retailer goods, subscriptions, etc., but they are also a powerful abstraction for resource allocation problems, such as power supply in manufacture systems, cargo space in transportation industry, bandwidths in the radio spectrum, and many more. The basic model is commonly enriched with a number of constraints in order to more closely describe settings typically arising in practice, such as a limited supply of items, customers’ intelligent behavior (envy-freeness), a seller aiming at revenue or social welfare maximization, etc. The literature is rich of results for this specific and more general kinds of markets, but only recently researchers have started investigating relationships and knowledge shared among buyers. Seminal works have considered buyers as individuals of a population who transfer their knowledge and thus behave accordingly. In the present thesis we extend or introduce concepts related to sociality among buyers in multi-unit markets and study problems of revenue and social welfare maximization from an algorithmic game theory perspective. Sociality and price discrimination are the focus of our work, with resulting frameworks for a more accurate description of the real-world scenarios related to multi-unit markets and a picture of the computational complexity of the challenges arising from the interplay of the various requirements considered in the model. The contribution of this work can be broadly divided into two different respects. One concerns a suitable relaxation of the envy-freeness notion induced by social relationships, obtained by restricting the corresponding constraints only to known peers, instead of the whole population of buyers. The related results are presented in Chapter 2. The second line concerns forms of price discrimination that buyers can consider as fair. More precisely, the prices proposed to neighbor buyers cannot be arbitrarily, but they should be reasonably close. The original results obtained in this setting are described in Chapter 3 and Chapter 4. In both cases, we propose suitable frameworks for representing the arising scenarios, and provide optimal efficient algorithms, and hardness and approximation results concerning the sellers’ revenue and the social welfare maximization.