Search

We study letter grading schemes, which are routinely employed for evaluating student performance. Typically, a numerical score obtained via one or more evaluations is converted into a letter grade (e.g., A+, B-, etc.) by associating a disjoint interval of numerical scores to each letter grade. We propose the first model for studying the (de)motivational effects of such grading on the students and, consequently, on their performance in future evaluations. We use the model to compare uniform letter grading schemes, in which the range of scores is divided into equal-length parts that are mapped to the letter grades, to numerical scoring, in which the score is not converted to any letter grade (equivalently, every score is its own letter grade). Theoretically, we identify realistic conditions under which numerical scoring is better than any uniform letter grading scheme. Our experiments confirm that this holds under even weaker conditions, but also find cases where the converse occurs., Comment: Accepted to IJCAI 2024

In many online platforms, customers' decisions are substantially influenced by product rankings as most customers only examine a few top-ranked products. Concurrently, such platforms also use the same data corresponding to customers' actions to learn how these products must be ranked or ordered. These interactions in the underlying learning process, however, may incentivize sellers to artificially inflate their position by employing fake users, as exemplified by the emergence of click farms. Motivated by such fraudulent behavior, we study the ranking problem of a platform that faces a mixture of real and fake users who are indistinguishable from one another. We first show that existing learning algorithms---that are optimal in the absence of fake users---may converge to highly sub-optimal rankings under manipulation by fake users. To overcome this deficiency, we develop efficient learning algorithms under two informational environments: in the first setting, the platform is aware of the number of fake users, and in the second setting, it is agnostic to the number of fake users. For both these environments, we prove that our algorithms converge to the optimal ranking, while being robust to the aforementioned fraudulent behavior; we also present worst-case performance guarantees for our methods, and show that they significantly outperform existing algorithms. At a high level, our work employs several novel approaches to guarantee robustness such as: (i) constructing product-ordering graphs that encode the pairwise relationships between products inferred from the customers' actions; and (ii) implementing multiple levels of learning with a judicious amount of bi-directional cross-learning between levels., Comment: 65 pages, 4 figures

The design of personalized incentives or recommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for matching incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environment. We design an algorithm that combines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for bandits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demonstrate its performance via both synthetic and realistic (matching supply and demand in a bike-sharing platform) examples., Comment: Published as a conference paper in Conference on Uncertainty in Artificial Intelligence (UAI) 2018

Renewable resources are starting to constitute a growing portion of the total generation mix of the power system. A key difference between renewables and traditional generators is that many renewable resources are managed by individuals, especially in the distribution system. In this paper, we study the capacity investment and pricing problem, where multiple renewable producers compete in a decentralized market. It is known that most deterministic capacity games tend to result in very inefficient equilibria, even when there are a large number of similar players. In contrast, we show that due to the inherent randomness of renewable resources, the equilibria in our capacity game becomes efficient as the number of players grows and coincides with the centralized decision from the social planner's problem. This result provides a new perspective on how to look at the positive influence of randomness in a game framework as well as its contribution to resource planning, scheduling, and bidding. We validate our results by simulation studies using real world data., Comment: Appears in IEEE Transactions on Sustainable Computing

We study a multi-armed bandit problem in a dynamic environment where arm rewards evolve in a correlated fashion according to a Markov chain. Different than much of the work on related problems, in our formulation a learning algorithm does not have access to either a priori information or observations of the state of the Markov chain and only observes smoothed reward feedback following time intervals we refer to as epochs. We demonstrate that existing methods such as UCB and $\varepsilon$-greedy can suffer linear regret in such an environment. Employing mixing-time bounds on Markov chains, we develop algorithms called EpochUCB and EpochGreedy that draw inspiration from the aforementioned methods, yet which admit sublinear regret guarantees for the problem formulation. Our proposed algorithms proceed in epochs in which an arm is played repeatedly for a number of iterations that grows linearly as a function of the number of times an arm has been played in the past. We analyze these algorithms under two types of smoothed reward feedback at the end of each epoch: a reward that is the discount-average of the discounted rewards within an epoch, and a reward that is the time-average of the rewards within an epoch., Comment: Significant revision of prior version including deeper discussion of related work, gap-independent regret bounds, and regret bounds for discounted rewards

A large number of applications such as querying sensor networks, and analyzing protein-protein interaction (PPI) networks, rely on mining uncertain graph and hypergraph databases. In this work we study the following problem: given an uncertain, weighted (hyper)graph, how can we efficiently find a (hyper)matching with high expected reward, and low risk? This problem naturally arises in the context of several important applications, such as online dating, kidney exchanges, and team formation. We introduce a novel formulation for finding matchings with maximum expected reward and bounded risk under a general model of uncertain weighted (hyper)graphs that we introduce in this work. Our model generalizes probabilistic models used in prior work, and captures both continuous and discrete probability distributions, thus allowing to handle privacy related applications that inject appropriately distributed noise to (hyper)edge weights. Given that our optimization problem is NP-hard, we turn our attention to designing efficient approximation algorithms. For the case of uncertain weighted graphs, we provide a $\frac{1}{3}$-approximation algorithm, and a $\frac{1}{5}$-approximation algorithm with near optimal run time. For the case of uncertain weighted hypergraphs, we provide a $\Omega(\frac{1}{k})$-approximation algorithm, where $k$ is the rank of the hypergraph (i.e., any hyperedge includes at most $k$ nodes), that runs in almost (modulo log factors) linear time. We complement our theoretical results by testing our approximation algorithms on a wide variety of synthetic experiments, where we observe in a controlled setting interesting findings on the trade-off between reward, and risk. We also provide an application of our formulation for providing recommendations of teams that are likely to collaborate, and have high impact., Comment: 25 pages

We study the equilibrium behavior in a multi-commodity selfish routing game with many types of uncertain users where each user over- or under-estimates their congestion costs by a multiplicative factor. Surprisingly, we find that uncertainties in different directions have qualitatively distinct impacts on equilibria. Namely, contrary to the usual notion that uncertainty increases inefficiencies, network congestion actually decreases when users over-estimate their costs. On the other hand, under-estimation of costs leads to increased congestion. We apply these results to urban transportation networks, where drivers have different estimates about the cost of congestion. In light of the dynamic pricing policies aimed at tackling congestion, our results indicate that users' perception of these prices can significantly impact the policy's efficacy, and "caution in the face of uncertainty" leads to favorable network conditions., Comment: Currently under review

We study approximation algorithms for revenue maximization based on static item pricing, where a seller chooses prices for various goods in the market, and then the buyers purchase utility-maximizing bundles at these given prices. We formulate two somewhat general techniques for designing good pricing algorithms for this setting: Price Doubling and Item Halving. Using these techniques, we unify many of the existing results in the item pricing literature under a common framework, as well as provide several new item pricing algorithms for approximating both revenue and social welfare. More specifically, for a variety of settings with item pricing, we show that it is possible to deterministically obtain a log-approximation for revenue and a constant-approximation for social welfare simultaneously: thus one need not sacrifice revenue if the goal is to still have decent welfare guarantees. %In addition, we provide a new black-box reduction from revenue to welfare based on item pricing, which immediately gives us new revenue-approximation algorithms (e.g., for gross substitutes valuations). The main technical contribution of this paper is a $O((\log m + \log k)^2)$-approximation algorithm for revenue maximization based on the Item Halving technique, for settings where buyers have XoS valuations, where $m$ is the number of goods and $k$ is the average supply. Surprisingly, ours is the first known item pricing algorithm with polylogarithmic approximations for such general classes of valuations, and partially resolves an important open question from the algorithmic pricing literature about the existence of item pricing algorithms with logarithmic factors for general valuations. We also use the Item Halving framework to form envy-free item pricing mechanisms for the popular setting of multi-unit markets, providing a log-approximation to revenue in this case., Comment: To appear in the proceedings of EC 2017

We study large markets with a single seller which can produce many types of goods, and many multi-minded buyers. The seller chooses posted prices for its many items, and the buyers purchase bundles to maximize their utility. For this setting, we consider the following questions: What fraction of the optimum social welfare does a revenue maximizing solution achieve? Are there pricing mechanisms which achieve both good revenue and good welfare simultaneously? To address these questions, we give efficient pricing schemes which are guaranteed to result in both good revenue and welfare, as long as the buyer valuations for the goods they desire have a nice (although reasonable) structure, e.g., that the aggregate buyer demand has a monotone hazard rate or is not too convex. We also show that our pricing schemes have implications for any pricing which achieves high revenue: specifically that even if the seller cares only about revenue, they can still ensure that their prices result in good social welfare without sacrificing profit. Our results holds for general multi-minded buyers in large markets; we also provide improved guarantees for the important special case of unit-demand buyers., Comment: To appear in the Proceedings of WINE 2016

We study truthful mechanisms for matching and related problems in a partial information setting, where the agents' true utilities are hidden, and the algorithm only has access to ordinal preference information. Our model is motivated by the fact that in many settings, agents cannot express the numerical values of their utility for different outcomes, but are still able to rank the outcomes in their order of preference. Specifically, we study problems where the ground truth exists in the form of a weighted graph of agent utilities, but the algorithm can only elicit the agents' private information in the form of a preference ordering for each agent induced by the underlying weights. Against this backdrop, we design truthful algorithms to approximate the true optimum solution with respect to the hidden weights. Our techniques yield universally truthful algorithms for a number of graph problems: a 1.76-approximation algorithm for Max-Weight Matching, 2-approximation algorithm for Max k-matching, a 6-approximation algorithm for Densest k-subgraph, and a 2-approximation algorithm for Max Traveling Salesman as long as the hidden weights constitute a metric. We also provide improved approximation algorithms for such problems when the agents are not able to lie about their preferences. Our results are the first non-trivial truthful approximation algorithms for these problems, and indicate that in many situations, we can design robust algorithms even when the agents may lie and only provide ordinal information instead of precise utilities., Comment: To appear in the Proceedings of WINE 2016

In the quest for market mechanisms that are easy to implement, yet close to optimal, few seem as viable as posted pricing. Despite the growing body of impressive results, the performance of most posted price mechanisms however, rely crucially on price discrimination when multiple copies of a good are available. For the more general case with non-linear production costs on each good, hardly anything is known for general multi-good markets. With this in mind, we study a Bayesian setting where the seller can produce any number of copies of a good but faces convex production costs for the same, and buyers arrive sequentially. Our main contribution is a framework for non-discriminatory pricing in the presence of production costs: the framework yields posted price mechanisms with O(1)-approximation factors for fractionally subadditive (XoS) buyers, logarithmic approximations for subadditive buyers, and also extends to settings where the seller is oblivious to buyer valuations. Our work presents the first known results for Bayesian settings with production costs and is among the few posted price mechanisms that do not charge buyers differently for the same good., Comment: The manuscript is currently under review

We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items with uncertain individual performances to maximize their expected group value. Although near-optimal algorithms have been proposed for this problem, practical concerns regarding scalability, compatibility with distributed implementation, and expensive oracle queries persist in large-scale applications. Motivated by online platforms that rely on individual item scores for content recommendation and team selection, we propose a special class of algorithms that select items based solely on individual performance measures known as test scores. The central contribution of this work is a novel and systematic framework for designing test score based algorithms for a broad class of naturally occurring utility functions. We introduce a new scoring mechanism that we refer to as replication test scores and prove that as long as the objective function satisfies a diminishing returns property, one can leverage these scores to compute solutions that are within a constant factor of the optimum. We then extend our results to the more general stochastic submodular welfare maximization problem, where the goal is to select items and assign them to multiple groups to maximize the sum of the expected group values. For this more difficult problem, we show that replication test scores can be used to develop an algorithm that approximates the optimum solution up to a logarithmic factor. The techniques presented in this work bridge the gap between the rigorous theoretical work on submodular optimization and simple, scalable heuristics that are useful in certain domains., Comment: Under review

We study Matching and other related problems in a partial information setting where the agents' utilities for being matched to other agents are hidden and the mechanism only has access to ordinal preference information. Our model is motivated by the fact that in many settings, agents cannot express the numerical values of their utility for different outcomes, but are still able to rank the outcomes in their order of preference. Specifically, we study problems where the ground truth exists in the form of a weighted graph, and look to design algorithms that approximate the true optimum matching using only the preference orderings for each agent (induced by the hidden weights) as input. If no restrictions are placed on the weights, then one cannot hope to do better than the simple greedy algorithm, which yields a half optimal matching. Perhaps surprisingly, we show that by imposing a little structure on the weights, we can improve upon the trivial algorithm significantly: we design a 1.6-approximation algorithm for instances where the hidden weights obey the metric inequality. Using our algorithms for matching as a black-box, we also design new approximation algorithms for other closely related problems: these include a a 3.2-approximation for the problem of clustering agents into equal sized partitions, a 4-approximation algorithm for Densest k-subgraph, and a 2.14-approximation algorithm for Max TSP. These results are the first non-trivial ordinal approximation algorithms for such problems, and indicate that we can design robust algorithms even when we are agnostic to the precise agent utilities., Comment: This paper contains the results that appeared in a AAAI'16 paper along with some new results for other problems

Consider a setting where selfish agents are to be assigned to coalitions or projects from a fixed set P. Each project k is characterized by a valuation function; v_k(S) is the value generated by a set S of agents working on project k. We study the following classic problem in this setting: "how should the agents divide the value that they collectively create?". One traditional approach in cooperative game theory is to study core stability with the implicit assumption that there are infinite copies of one project, and agents can partition themselves into any number of coalitions. In contrast, we consider a model with a finite number of non-identical projects; this makes computing both high-welfare solutions and core payments highly non-trivial. The main contribution of this paper is a black-box mechanism that reduces the problem of computing a near-optimal core stable solution to the purely algorithmic problem of welfare maximization; we apply this to compute an approximately core stable solution that extracts one-fourth of the optimal social welfare for the class of subadditive valuations. We also show much stronger results for several popular sub-classes: anonymous, fractionally subadditive, and submodular valuations, as well as provide new approximation algorithms for welfare maximization with anonymous functions. Finally, we establish a connection between our setting and the well-studied simultaneous auctions with item bidding; we adapt our results to compute approximate pure Nash equilibria for these auctions., Comment: Under Review

We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of this problem have resisted good approximation factors for maximizing revenue; this is true even for the classic unit-demand case. In this paper we study envy-free pricing with unit-demand buyers, but unlike previous work we focus on large markets: ones in which the demand of each buyer is infinitesimally small compared to the size of the overall market. We assume that the buyer valuations for the items they desire have a nice (although reasonable) structure, i.e., that the aggregate buyer demand has a monotone hazard rate and that the values of every buyer type come from the same support. For such large markets, our main contribution is a 1.88 approximation algorithm for maximizing revenue, showing that good pricing schemes can be computed when the number of buyers is large. We also give a (e,2)-bicriteria algorithm that simultaneously approximates both maximum revenue and welfare, thus showing that it is possible to obtain both good revenue and welfare at the same time. We further generalize our results by relaxing some of our assumptions, and quantify the necessary tradeoffs between revenue and welfare in our setting. Our results are the first known approximations for large markets, and crucially rely on new lower bounds which we prove for the revenue-maximizing prices., Comment: ACM Transactions on Economics and Computation (TEAC), to appear. Conference version appeared in ICALP 2015

We study the efficiency of allocations in large markets with a network structure where every seller owns an edge in a graph and every buyer desires a path connecting some nodes. While it is known that stable allocations in such settings can be very inefficient, the exact properties of equilibria in markets with multiple sellers are not fully understood even in single-source single-sink networks. In this work, we show that for a large class of natural buyer demand functions, we are guaranteed the existence of an equilibrium with several desirable properties. The crucial insight that we gain into the equilibrium structure allows us to obtain tight bounds on efficiency in terms of the various parameters governing the market, especially the number of monopolies M. All of our efficiency results extend to markets without the network structure. While it is known that monopolies can cause large inefficiencies in general, our main results for single-source single-sink networks indicate that for several natural demand functions the efficiency only drops linearly with M. For example, for concave demand we prove that the efficiency loss is at most a factor 1+M/2 from the optimum, for demand with monotone hazard rate it is at most 1+M, and for polynomial demand the efficiency decreases logarithmically with M. In contrast to previous work that showed that monopolies may adversely affect welfare, our main contribution is showing that monopolies may not be as `evil' as they are made out to be; the loss in efficiency is bounded in many natural markets. Finally, we consider more general, multiple-source networks and show that in the absence of monopolies, mild assumptions on the network topology guarantee an equilibrium that maximizes social welfare., Comment: To appear in Proceedings of WINE 2015: 11th Conference on Web and Internet Economics

We study techniques to incentivize self-interested agents to form socially desirable solutions in scenarios where they benefit from mutual coordination. Towards this end, we consider coordination games where agents have different intrinsic preferences but they stand to gain if others choose the same strategy as them. For non-trivial versions of our game, stable solutions like Nash Equilibrium may not exist, or may be socially inefficient even when they do exist. This motivates us to focus on designing efficient algorithms to compute (almost) stable solutions like Approximate Equilibrium that can be realized if agents are provided some additional incentives. Our results apply in many settings like adoption of new products, project selection, and group formation, where a central authority can direct agents towards a strategy but agents may defect if they have better alternatives. We show that for any given instance, we can either compute a high quality approximate equilibrium or a near-optimal solution that can be stabilized by providing small payments to some players. We then generalize our model to encompass situations where player relationships may exhibit complementarities and present an algorithm to compute an Approximate Equilibrium whose stability factor is linear in the degree of complementarity. Our results imply that a little influence is necessary in order to ensure that selfish players coordinate and form socially efficient solutions., Comment: A preliminary version of this work will appear in AAAI-14: Twenty-Eighth Conference on Artificial Intelligence

Maintaining high quality content is one of the foremost objectives of any web-based collaborative service that depends on a large number of users. In such systems, it is nearly impossible for automated scripts to judge semantics as it is to expect all editors to review the content. This catalyzes the need for trust-based mechanisms to ensure quality of an article immediately after an edit. In this paper, we build on previous work and develop a framework based on the `web of trust' concept to calculate satisfaction scores for all users without the need for perusing the article. We derive some bounds for systems based on our mechanism and show that the optimization problem of selecting the best users to review an article is NP-Hard. Extensive simulations validate our model and results, and show that trust-based mechanisms are essential to improve efficiency in any online collaborative editing platform.