The Computer Science and Economics departments of Ashoka University will be hosting a workshop on Computation and Economics during September 9-11 on the University campus. A preliminary programme is given below.
Ratul Lahkar, An Evolutionary Interpretation of Dominant Strategy Implementation
Abstract: We consider dominant strategy implementation in a large population aggregative game. Strategic complementarities or, equivalently, positive externalities in the model generate multiple Nash equilibria, all of which are socially inefficient. The planner, therefore, constructs a direct mechanism and assigns efficient strategies and transfer levels to agents. Truthful revelation then becomes strictly dominant, which implements efficiency. In our new evolutionary approach to this mechanism, the reported type distribution evolves under dynamics satisfying monotone percentage growth. Such dynamics eliminate dominated strategies thereby ensuring convergence to truthful revelation by all agents. Our evolutionary approach differs from existing models of evolutionary implementation based on potential games. That approach may fail to implement efficiency under strategic complementarities as a Pareto inferior Nash equilibrium can remain asymptotically stable under evolutionary dynamics. Our evolutionary approach is effective even under such strategic complementarities.
Rohit Vaish, Best of Both Worlds in Fair Division
Abstract: Fairness is a fundamental human endeavor. In times when an increasing amount of decision-making is being handed over to automated systems, it is more important than ever to provide solutions with provable, mathematically rigorous guarantees. The area of fair division provides a formal theoretical framework to reason about such questions in the context of resource allocation.
In this talk, I will focus on fair allocation of indivisible resources, which arise in real-world settings such as inheritance division and course allocation at universities. Traditional approaches towards this problem focus either on randomized allocations that are fair in expectation or deterministic allocations that are approximately fair. I will discuss an algorithmic framework that reconciles randomization and approximation. Specifically, I will present an algorithm for finding a randomized allocation of indivisible goods that is ex-ante fair (i.e., envy- free) and ex-post approximately fair (i.e., envy-free up to one good).
The talk will focus on an EC 2020 paper based on joint work with Rupert Freeman (Univ. of Virginia) and Nisarg Shah (Univ. of Toronto), and a WINE 2020 paper by Haris Aziz (UNSW Sydney).
Herve Moulin , Ex Ante Fair Division
Abstract: Ex Ante fairness, first appearing in Steinhaus' seminal model of cake division, is key to secure the participation of agents who are worst-case minimising or simply unwilling to approach the division rule as a strategic game.
The best ex ante guarantees a mechanism can offer are unique and very easily described in some problems, but multiple and extremely hard to identify in others. We illustrate the former situation in a simple congestion model and for the allocation of divisible commodities, and the latter in probabilistic voting and the moneyless allocation of indivisible items.
Kavitha Telikepalli, The Popular Assignment Problem
Abstract: Computing an optimal matching in a bipartite graph where vertices have preferences over neighbors is an old and well-studied problem. We consider a model where vertices on only one side of the bipartite graph have preferences over their neighbors. Moreover, the size of the matching is more important than vertex preferences. So any maximum matching is better than one that is not maximum and any pair of maximum matchings can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute a maximum matching such that there is no better matching. This talk is primarily on an efficient algorithm for this problem.
Shweta Jain, Multi-armed Bandit Mechanisms and their applications to demand response.
Abstract: There are various applications such as smart grids, crowdsourcing, sponsored search auctions, etc. which involve strategic agents with private information and stochastic rewards. On one hand, machine learning tools are useful to learn the Stochastic rewards, while on the other hand, one needs game-theoretic machinery to elicit private information truthfully from the agents. The mechanisms that learn the stochastic rewards and truthfully elicit private information can be modeled as multi-armed bandit mechanisms. After a brief introduction to multi-armed bandit mechanisms, we will talk about their application to demand response in smart grids. In this problem, the distributor company wishes to design incentives for the consumers to reduce the peak load. These incentives are to be given to a subset of consumers to minimize the loss to the distributor company and may vary from time to time, based on consumers’ behavior towards these incentives. We will see how the existing theory of the multi-armed bandit mechanism needs to be extended for this application and requires novel theoretical contributions to the area.
Sandeep Juneja, Learning to ask the right questions using multi-armed bandits
Abstract: We consider the problem of designing an adaptive sequence of questions that optimally classify a candidate’s ability into one of several categories or discriminative grades. A candidate’s ability is modeled as an unknown parameter, which, together with the difficulty of the question asked, determines the likelihood with which s/he is able to answer a question correctly. The learning algorithm is only able to observe these noisy responses to its queries. We consider this problem from a fixed confidence framework, that in our setting seeks to arrive at the correct ability discrimination at the fastest possible rate while guaranteeing that the probability of error is less than a pre-specified and small δ. In this setting we develop lower bounds on any sequential questioning strategy and develop geometrical insights into the problem structure both from the primal and dual formulation. In addition, we arrive at algorithms that essentially match these lower bounds. Our key conclusions are that, asymptotically, any candidate needs to be asked questions at most at two (candidate ability-specific) levels, although, in a reasonably general framework, questions need to be asked only at a single level.
Bhaskar Dutta, Selecting a Winner with Impartial Referees
Abstract: We consider a problem of mechanism design without money, where a planner selects a winner among a set of agents with binary types. We show that the planner can leverage an outside signal (e.g. a report by an im- partial referee) to elicit information about the agents' types. The optimal Bayesian Incentive (BIC) mechanisms are lexicographic mechanisms, where the planner _first shortlists agents who receive high reports from the external referees and then uses agents' reports to break ties among agents in the shortlist. We compare the “self-evaluation" mechanism with a “peer evaluation" mechanism where agents evaluate other agents, and show that for the same signal precision, the self-evaluation mechanism outperforms the peer evaluation mechanism.
Ankur Kulkarni, Shannon meets Myerson: Extracting Information from a Strategic Sender
Abstract: The COVID-19 pandemic has brought to the fore the need for segregating travellers, visitors and the general population based on answers given to standardized questionnaires. However, not all such answers can be relied upon to be truthful and therefore the design of such questionnaires for extracting true information becomes a strategic question.
We introduce a setting where a receiver aims to perfectly recover a source known privately to a strategic sender by means of such questionnaires. The sender is endowed with a utility function and sends signals to the receiver with the aim of maximizing this utility. Due to the strategic nature of the sender, not all the transmitted information is truthful, and signals sent by the sender are not codewords. This leads to the question: how much true information can be extracted by the receiver from such a sender? And how does it extract this information? This talk will study this question in an information-theoretic setting.
We show that, in spite of the sender being strategic and the presence of noise in the channel, there is a strategy for the receiver by which it can perfectly recover an exponentially large number of source sequences. Our analysis leads to the notion of the information extraction capacity of the sender. Operationally, this capacity can be thought of as the (exponent of the) optimal length of a questionnaire to be provided to a strategic sender. We show that the information extraction capacity generalizes the Shannon capacity of a graph, and establish bounds on this capacity. We also identify cases where this capacity is equal to its theoretical maximum, and also when it is strictly less than the maximum. In the latter case, we show that the capacity is sandwiched between the independence number and the Shannon capacity of a suitably defined graph. These results lead to an exact characterization of the information extraction capacity in a large number of cases. We show that in the presence of a noisy channel, the rate of information extraction achieved by the receiver is the minimum of the zero-error capacity of the channel and the information extraction capacity of the sender. Our analysis leads to insights into a novel regime of communication involving strategic agents.
All members and (visitors) of Ashoka university are invited to participate in the workshop. However, you are requested to register in order to help us in planning the logistics. Participation of others is by invitation only. Please register using this link: https://forms.gle/Ss5pPKL2qfZMDRgh7.
Subhashish Banerjee (Ashoka)
Sidharth Barman (IISc, Bangalore)
Umang Bhaskar (TIFR)
Bhaskar Dutta (Ashoka)