skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 15

Search for: All records

Award ID contains: 1733556

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ( , EC'22)
    Free, publicly-accessible full text available January 1, 2023
  2. ( , EC'22)
    Free, publicly-accessible full text available January 1, 2023
  3. ( , SODA'22)
    Free, publicly-accessible full text available January 1, 2023
  4. ( , Knowledge and information systems)
    Free, publicly-accessible full text available January 1, 2023
  5. ; ; ; ( , ACM Conference on Economics and Computation)
    The classical Perceptron algorithm provides a simple and elegant procedure for learning a linear classifier. In each step, the algorithm observes the sample's position and label and updates the current predictor accordingly if it makes a mistake. However, in presence of strategic agents that desire to be classified as positive and that are able to modify their position by a limited amount, the classifier may not be able to observe the true position of agents but rather a position where the agent pretends to be. Unlike the original setting with perfect knowledge of positions, in this situation the Perceptron algorithmmore »fails to achieve its guarantees, and we illustrate examples with the predictor oscillating between two solutions forever, making an unbounded number of mistakes even though a perfect large-margin linear classifier exists. Our main contribution is providing a modified Perceptron-style algorithm which makes a bounded number of mistakes in presence of strategic agents with both $\ell_2$ and weighted $\ell_1$ manipulation costs. In our baseline model, knowledge of the manipulation costs (i.e., the extent to which an agent may manipulate) is assumed. In our most general model, we relax this assumption and provide an algorithm which learns and refines both the classifier and its cost estimates to achieve good mistake bounds even when manipulation costs are unknown.« less
    Full Text Available 
  6. ; ; ( , Journal of Artificial Intelligence Research)
    We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegationmore »mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a non-local delegation mechanism that does provably outperform direct voting under mild assumptions about voters.« less
    Full Text Available 
  7. ; ; ( , Proceedings of the National Academy of Sciences of the United States of America)
    Accepted Manuscript Full Text Available
  8. ; ( , AAAI Workshop on Reinforcement Learning in Games)
    Accepted Manuscript Full Text Available
  9. ; ( , AAAI Workshop on Reinforcement Learning in Games)
    Accepted Manuscript Full Text Available
  10. ; ; ( , AAAI Workshop on Reinforcement Learning in Games)
    Accepted Manuscript Full Text Available