Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Our research
Content type
+
Downloads (445)
+
Events (409)
 
Groups (152)
+
News (2620)
 
People (736)
 
Projects (1066)
+
Publications (12095)
+
Videos (5320)
Labs
Research areas
Algorithms and theory47205 (290)
Communication and collaboration47188 (189)
Computational linguistics47189 (189)
Computational sciences47190 (198)
Computer systems and networking47191 (691)
Computer vision208594 (876)
Data mining and data management208595 (73)
Economics and computation47192 (95)
Education47193 (79)
Gaming47194 (71)
Graphics and multimedia47195 (207)
Hardware and devices47196 (196)
Health and well-being47197 (78)
Human-computer interaction47198 (792)
Machine learning and intelligence47200 (769)
Mobile computing208596 (35)
Quantum computing208597 (20)
Search, information retrieval, and knowledge management47199 (625)
Security and privacy47202 (273)
Social media208598 (26)
Social sciences47203 (247)
Software development, programming principles, tools, and languages47204 (564)
Speech recognition, synthesis, and dialog systems208599 (78)
Technology for emerging markets208600 (27)
1–25 of 95
Sort
Show 25 | 50 | 100
1234Next 
Moshe Babaioff, Moran Feldman, and Moshe Tennenholtz

We consider the problem of designing mechanisms that interact with strategic agents through strategic intermediaries (or mediators), and investigate the cost to society due to the mediators' strategic behavior. Selfish agents with private information are each associated with exactly one strategic mediator, and can interact with the mechanism exclusively through that mediator. Each mediator aims to optimize the combined utility of his agents, while the mechanism aims to optimize the combined utility of...

Publication details
Date: 11 January 2015
Type: Inproceeding
Publisher: ACM – Association for Computing Machinery
Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and his value for a set of items is additive. The seller aims to maximize his revenue. It is known that an optimal mechanism in this setting may be quite complex, requiring randomization [HR12] and menus of infinite size [DDT13]. Hart and Nisan [HN12] have initiated a study of two very simple pricing schemes for this...

Publication details
Date: 1 October 2014
Type: Inproceeding
Publisher: IEEE – Institute of Electrical and Electronics Engineers
Yoram Bachrach, Vasilis Syrgkanis, Eva Tardos, and Milan Vojnovic

We introduce a framework for studying the effect of cooperation on the quality of outcomes in utility games. Our framework is a coalitional analog of the smoothness framework of non-cooperative games. Coalitional smoothness implies bounds on the strong price of anarchy, the loss of quality of coalitionally stable outcomes. Our coalitional smoothness framework captures existing results bounding the strong price of anarchy of network design games. Moreover, we give novel strong price of anarchy results...

Publication details
Date: 1 September 2014
Type: Inproceeding
Publisher: Springer
Nihar B. Shah and Dengyong Zhou

Many fields of science and engineering, ranging from predicting protein structures to building machine translation systems, require large amounts of labeled data. These labeling tasks have traditionally been performed by experts; the limited pool of experts would limit the size of the datasets, and make the process slow and expensive. In recent years, there is a rapidly increasing interest in using crowds of semi-skilled workers recruited through the Internet. While this 'crowdsourcing' can cheaply...

Publication details
Date: 1 August 2014
Type: Technical report
Number: MSR-TR-2014-117
Long Tran-Thanh, Lampros Stavrogiannis, Victor Naroditskiy, Valentin Robu, Nicholas R Jennings, and Peter Key

We study the problem of an advertising agent who needs to intelligently distribute her budget across a sequence of online keyword bidding auctions. We assume the closing price of each auction is governed by the same unknown distribution, and study the problem of making provably optimal bidding decisions. Learning the distribution is done under censored observations, i.e. the closing price of an auction is revealed only if the bid we place is above it. We consider three algorithms, namely...

Publication details
Date: 1 July 2014
Type: Inproceeding
Publisher: AUAI
Moshe Babaioff, Brendan Lucier, Noam Nisan, and Renato Paes Leme

Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported...

Publication details
Date: 10 June 2014
Type: Inproceeding
Publisher: ACM
Moshe Babaioff and Eyal Winter

We study the complexity required for the implementation of multi-agent contracts under a variety of solution concepts. A contract is a mapping from strategy profiles to outcomes. Practical implementation of a contract requires it to be ”simple”, an illusive concept that needs to be formalized. A major source of complexity is the burden involving verifying the contract fulfillment (for example in a court of law). Contracts which specify a small number of outcomes are easier to verify and are less prone...

Publication details
Date: 10 June 2014
Type: Inproceeding
Publisher: ACM
Daniel G. Goldstein, R. Preston McAfee, and Siddharth Suri

The “wisdom of crowds” refers to the phenomenon that aggregated predictions from a large group of people can rival or even beat the accuracy of experts. In domains with substantial stochastic elements, such as stock picking, crowd strategies (e.g. indexing) are difficult to beat. However, in domains in which some crowd members have demonstrably more skill than others, smart sub-crowds could possibly outperform the whole. The central question this work addresses is whether such smart subsets of a crowd...

Publication details
Date: 8 June 2014
Type: Inproceeding
Publisher: ACM
Winter Mason, Siddharth Suri, and Duncan J. Watts

Cooperation in repeated games has been widely studied in experimental settings; however, the duration over which players participate in such experiments is typically confined to at most hours, and often to a single game. Given that in real world settings people may have years of experience, it is natural to ask how behavior in cooperative games evolves over the long run. Here we analyze behavioral data from three distinct games involving 571 individual experiments conducted over a two-year interval....

Publication details
Date: 8 June 2014
Type: Inproceeding
Publisher: ACM
Shipra Agrawal and Nikhil R. Devanur

In this paper, we consider a very general model for exploration-exploitation tradeoff which allows arbitrary concave rewards and convex constraints on the decisions across time, in addition to the customary limitation on the time horizon. This model subsumes the classic multi-armed bandit (MAB) model, and the Bandits with Knapsacks (BwK) model of Badanidiyuru et al.[2013]. We also consider an extension of this model to allow linear contexts, similar to the linear contextual extension of the MAB model....

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: ACM conference on Economics and Computation
Yoram Bachrach, Sofia Ceppi, Ian A. Kash, Peter Key, and David Kurokawa

We examine trade-offs among stakeholders in ad auctions. Our metrics are the revenue for the utility of the auctioneer, the number of clicks for the utility of the users and the welfare for the utility of the advertisers. We show how to optimize linear combinations of the stakeholder utilities, showing that these can be tackled through a GSP auction with a per-click reserve price. We then examine constrained optimization of stakeholder utilities.

We use simulations and analysis of real-world...

Publication details
Date: 1 June 2014
Type: Proceedings
Publisher: ACM
Frank Kelly, Peter Key, and Neil Walton

We consider a large-scale Ad-auction where adverts are assigned over a potentially infinite number of searches. We capture the intrinsic asymmetries in information between advertisers, the advert platform and the space of searches: advertisers know and can optimize the average performance of their advertisement campaign; the platform knows and can optimize on each search instance; and, neither party knows the distribution of the infinite number of searches that can occur. We look at maximizing the...

Publication details
Date: 1 June 2014
Type: Inproceeding
Publisher: ACM Electronic Commerce
Publication details
Date: 1 January 2014
Type: Inproceeding
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins
Publication details
Date: 1 January 2014
Type: Inproceeding
Leon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X. Charles, D. Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson

This work shows how to leverage causal inference to understand the behavior of complex learning systems interacting with their environment and predict the consequences of changes to the system. Such predictions allow both humans and algorithms to select the changes that would have improved the system performance. This work is illustrated by experiments on the ad placement system associated with the Bing search engine.

Publication details
Date: 1 November 2013
Type: Article
Publisher: Journal of Machine Learning Research
Number: Nov
Brendan Lucier, Ishai Menache, Joseph Naor, and Jonathan Yaniv

We consider mechanisms for online deadline-aware scheduling in large computing clusters. Batch jobs that run on such clusters often require guarantees on their completion time (i.e., deadlines). However, most existing scheduling systems implement fair-share resource allocation between users, an approach that ignores heterogeneity in job requirements and may cause deadlines to be missed. In our framework, jobs arrive dynamically and are characterized by their value and total resource demand (or...

Publication details
Date: 1 July 2013
Type: Inproceeding
Mahyar Salek, Yoram Bachrach, and Peter Key

Object localization is an image annotation task which consists of finding the location of a target object in an image. It is common to crowdsource annotation tasks and aggregate responses to estimate the true annotation. While for other kinds of annotations consensus is simple and powerful, it cannot be applied to object localization as effectively due to the task’s rich answer space and inherent noise in responses. We propose a probabilistic graphical model to localize objects in images based on...

Publication details
Date: 1 July 2013
Type: Inproceeding
Publisher: AAAI
Yuezhou Lv and Thomas Moscibroda

We study Incentive Trees for motivating the participation of people in crowdsourcing or human tasking systems. In an Incentive Tree, each participant is rewarded for contributing to the system, as well as for soliciting new participants into the system, who then themselves contribute to it and/or themselves solicit new participants. An Incentive Tree mechanism is an algorithm that determines how much reward each individual participant receives based on all the participants’ contributions, as well as the...

Publication details
Date: 1 July 2013
Type: Inproceeding
Publisher: ACM
Kshipra Bhawalkar, Sreenivas Gollapudi, and Kamesh Munagala

We present game-theoretic models of opinion formation in social networks where opinions themselves co-evolve with friendships. In these models, nodes form their opinions by maximizing agreements with friends weighted by the strength of the relationships, which in turn depend on difference in opinion with the respective friends. We define a social cost of this process by generalizing recent work of Bindel et al., FOCS 2011. We tightly bound the price of anarchy of the resulting dynamics via local...

Publication details
Date: 1 June 2013
Type: Inproceeding
Publisher: ACM
Ben Roberts, Ian Kash, and Peter Key

In a sponsored search auction, decisions about how to rank ads impose tradeoffs between objectives such as revenue and welfare. In this paper, we examine how these tradeoffs should be made. We begin by arguing that the most natural solution concept to evaluate these tradeoffs is the lowest symmetric Nash equilibrium (SNE). As part of this argument, we generalize the well known connection between the lowest SNE and the VCG outcome. We then propose a new ranking algorithm, loosely based on the...

Publication details
Date: 1 June 2013
Type: Inproceeding
Publisher: ACM
Anand Bhalgat, Sreenivas Gollapudi, and Kamesh Munagala

We show that the multiplicative weight update method provides a simple recipe for designing and analyzing optimal Bayesian Incentive Compatible (BIC) auctions, and reduces the time complexity of the problem to polynomial in parameters that depend on single agent instead of on the joint type space. We use this framework to design the first computationally efficient optimal auctions that satisfy ex-post Individual Rationality in the presence of constraints such as (hard, private) budgets and...

Publication details
Date: 1 June 2013
Type: Inproceeding
Publisher: ACM Conference on Electronic Commerce
Publication details
Date: 1 January 2013
Type: Article
Number: 99
Yiling Chen, Stephen Chong, Ian A. Kash, Tal Moran, and Salil Vadhan
Publication details
Date: 1 January 2013
Type: Inproceeding
Yoram Bachrach, Michael Zuckerman, Michael Wooldridge, and Jeffrey S. Rosenschein

We introduce Transformation Games (TGs), a form of coalitional game in which players are endowed with sets of initial resources, and have capabilities allowing them to derive certain output resources, given certain input resources. The aim of a TG is to generate a particular target resource; players achieve this by forming a coalition capable of performing a sequence of transformations from a combined set of initial resources to the target resource. TGs can model a number of natural settings, such as...

Publication details
Date: 1 January 2013
Type: Article
Dipanjan Chakraborty, Indrani Medhi, Edward Cutrell, and William Thies

Many organizations in the developing world need to conduct phone surveys to collect data from low-income respondents. Such organizations generally have two options: employ a live operator, or utilize interactive voice response (IVR). Despite the relevance of this question, we are unaware of any work that rigorously compares the accuracy, speed, and cost of an IVR survey relative to a live operator. In this paper, we address these questions by giving two identical interviews one using IVR, and one...

Publication details
Date: 1 January 2013
Type: Proceedings
Publisher: ACM Symposium on Computing for Development (ACM DEV)
1–25 of 95
Sort
Show 25 | 50 | 100
1234Next 
> Our research