Workshop on Mechanism Design and Auctions on Monday – 9th April, 2018

Workshop on Game Theory, Auctions, Mechanism Design and Operations Research

Monday, April 9^th, 2018

Workshop Program

ADDRESS: Indira Gandhi Institute of Development Research, Gen. A.K. Vaidya Marg, Santosh Nagar, Goregaon East, Mumbai, 400065.

Contact: Shubhro Sarkar (90046 33043), Mallikarjuna Rao (98694 42869).

Abstracts

1. Umang Bhaskar, TIFR

Title: Bounds on the Welfare of Truthful Voting Mechanisms

Abstract: Mechanisms for aggregating the preferences of agents in elections need to balance many different considerations, including efficiency, information elicited from agents, and manipulability. We consider the utilitarian social welfare of mechanisms for preference aggregation, measured by the distortion. We show that for a particular input format called threshold approval voting, there is a mechanism with nearly optimal distortion when the number of voters is large. However, threshold mechanisms are potentially manipulable. We then consider truthful ordinal and cardinal mechanisms, and present nearly matching upper and lower bounds on the distortions for these.

2. Prof. Gaurav Kasbekar
   Title: Truthful Reverse Auction for Relay Selection with High Data Rate and Base Station Utility in D2D Networks.

Abstract: Device-to-Device (D2D) communication allows a mobile device (node) to relay data between a base station and another mobile device (destination) with poor direct channel conditions. However, the battery energy of a node serving as a relay gets depleted, and hence, to compensate for this loss, relays need to be provided incentives. Also, for a given destination, there usually exist multiple nodes in the network capable of providing relaying services. In this paper, we propose a reverse auction mechanism to select a node from among the available nodes to act as a relay for a destination in each of the following three scenarios: 1) when nodes are allocated a fixed transmission power, 2) when nodes are allocated the transmission power required to achieve a desired data rate, and 3) when the transmission power of nodes is selected so as to approximately maximize the base station’s utility. Monetary payments (incentives) are provided to the selected node in each of the above three scenarios. We prove that all the proposed reverse auctions can be truthfully implemented as well as satisfy the individual rationality property. Finally, using numerical computations, we show that in the fixed transmission power scenario, our proposed auction significantly outperforms an auction based on the widely used Vickrey-Clarke-Groves (VCG) mechanism in terms of the data rate achieved by the destination node as well as the utility of the base station.

3. Anuj Bhowmik

Title: On the Existence of Rational Expectations-Equilibria in a class of Discrete Sequential-Choice Social-Interactions Models

4. Prof. Arunava Sen

Title: Matching with Partners and Projects

5. Prof. Manjesh Hanawal

Title: Differential Pricing of Traffic in the Internet.
Abstract: ​The ongoing net neutrality debate has generated a lot of heated discussions on whether or not monetary interactions should be regulated between content and access providers. Among the several topics discussed, ‘differential pricing’ has recently received attention due to ‘zero-rating’ platforms proposed by some service providers. In the differential pricing scheme, Internet Service Providers (ISPs) can exempt data traffic charges for accessing content from certain CPs or applications (zero-rated) and apply regular charges for accessing content from other CPs. This allows the possibility for Content Providers (CPs) to make ‘sponsorship’ agreements to zero-rate their content and attract more user traffic. In this paper, we study the effect of differential pricing on various players in the Internet. We consider a model with a single ISP and multiple CPs where users select CPs based on the quality of service (QoS) and applicable traffic charges. We show that in a differential pricing regime 1) a CP offering low QoS can make more revenues than a CP offering better QoS through sponsorships. 2) QoS (mean delay) for end users can degrade compared to the case where no differential pricing is allowed

Bio: Manjesh K. Hanawal received the M.S. degree in ECE from the Indian Institute of Science, Bangalore, India, in 2009, and the Ph.D. degree from INRIA, Sophia Antipolis, France, and the University of Avignon, Avignon, France, in 2013. After spending two years as a postdoctoral associate at Boston University, he is now an Assistant Professor in Industrial Engineering and Operations Research at the Indian Institute of Technology Bombay, Mumbai, India. His research interests include communication networks, machine learning and network economics.

6. Prof. N. Hemachandra

Title: Equilibrium points and Equilibrium Sets in some Quality of Service Sensitive Markets.

Abstract:  We first settle a conjecture regarding the optimal joint pricing and scheduling problem in a 2-class M/G/1 queue: Any stable M/G/1 has a surplus server capacity of 1 – \rho and earlier we proposed a model to admit mean waiting time sensitive secondary class of to use this surplus. This leads to an interpretation of this optimal price and schedule as unique Nash Equilibrium of a one-period game between the queue (service-provider) and user-set (secondary class of customers). This Nash Equilibrium can be computed in finite number of steps. Next, we outline a convex constrained best response dynamics algo, that we are currently investigating, to compute this NE; this may be of independent interest in related constrained games.
The remaining part of the talk is about two models wherein the service-provider uses a Markov decision model to identify a revenue optimal operational policy to allocate its finite resources for its operations. In our framework, the user-set offers demand with a mean that is based on the QoS it experiences; since the offered QoS depends on the demand, this leads to the question of existence of an equilibrium in this QoS based interaction. Under a mild assumption, we show that there exist an Equilibrium Sets if there is no Equilibrium point. A vehicle relocation problem is an illustration of this. Equilibrium Sets offer one possible explanation for the business cycles of high demand followed by low demand regimes in tech/engineering service

markets; these cycles are due to QoS aspect in contrast to prices.
In the 3rd part, we consider admission control of a M/G/1 queue when the queue decides to admit a customer paying r units of money, but incurs a holding cost in return. It is known that threshold policies are optimal when the queue uses average cost criteria or discounted cost criteria; the former is a socially optimal policy while the second one captures the queue’s time value of money. We investigate the nature of the Equilibrium Sets in this setting, contributed by queue as well as by user-sets; again these sets illustrate the role of QoS in equilibrium of such service markets.

7. Prof. Debasis Mishra

Title: Selling to a Naïve Agent with Two Rationales.