Ariel D. Procaccia

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (98)

Clone-Robust AI Alignment

2025-01-15

Ariel D. Procaccia , Benjamin F. Schiffer , Shirley Zhang

A key challenge in training Large Language Models (LLMs) is properly aligning them with human preferences. Reinforcement Learning with Human Feedback (RLHF) uses pairwise comparisons from human annotators to train … A key challenge in training Large Language Models (LLMs) is properly aligning them with human preferences. Reinforcement Learning with Human Feedback (RLHF) uses pairwise comparisons from human annotators to train reward functions and has emerged as a popular alignment method. However, input datasets in RLHF are not necessarily balanced in the types of questions and answers that are included. Therefore, we want RLHF algorithms to perform well even when the set of alternatives is not uniformly distributed. Drawing on insights from social choice theory, we introduce robustness to approximate clones, a desirable property of RLHF algorithms which requires that adding near-duplicate alternatives does not significantly change the learned reward function. We first demonstrate that the standard RLHF algorithm based on regularized maximum likelihood estimation (MLE) fails to satisfy this property. We then propose the weighted MLE, a new RLHF algorithm that modifies the standard regularized MLE by weighting alternatives based on their similarity to other alternatives. This new algorithm guarantees robustness to approximate clones while preserving desirable theoretical properties.

Chat View PDF

How will advanced AI systems impact democracy?

2024-08-27

Christopher Summerfield , Lisa P. Argyle , Michiel A. Bakker +7 more

Advanced AI systems capable of generating humanlike text and multimodal content are now widely available. In this paper, we discuss the impacts that generative artificial intelligence may have on democratic … Advanced AI systems capable of generating humanlike text and multimodal content are now widely available. In this paper, we discuss the impacts that generative artificial intelligence may have on democratic processes. We consider the consequences of AI for citizens' ability to make informed choices about political representatives and issues (epistemic impacts). We ask how AI might be used to destabilise or support democratic mechanisms like elections (material impacts). Finally, we discuss whether AI will strengthen or weaken democratic principles (foundational impacts). It is widely acknowledged that new AI systems could pose significant challenges for democracy. However, it has also been argued that generative AI offers new opportunities to educate and learn from citizens, strengthen public discourse, help people find common ground, and to reimagine how democracies might work better.

Chat View PDF

Honor Among Bandits: No-Regret Learning for Online Fair Division

2024-07-01

Ariel D. Procaccia , Benjamin F. Schiffer , Shirley Zhang

We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions … We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player's value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves $\tilde{O}(T^{2/3})$ regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space.

Chat View PDF

Federated Assemblies

2024-05-29

Daniel Halpern , Ariel D. Procaccia , Ehud Shapiro +1 more

A citizens' assembly is a group of people who are randomly selected to represent a larger population in a deliberation. While this approach has successfully strengthened democracy, it has certain … A citizens' assembly is a group of people who are randomly selected to represent a larger population in a deliberation. While this approach has successfully strengthened democracy, it has certain limitations that suggest the need for assemblies to form and associate more organically. In response, we propose federated assemblies, where assemblies are interconnected, and each parent assembly is selected from members of its child assemblies. The main technical challenge is to develop random selection algorithms that meet new representation constraints inherent in this hierarchical structure. We design and analyze several algorithms that provide different representation guarantees under various assumptions on the structure of the underlying graph.

Chat View PDF

Bias Detection Via Signaling

2024-05-27

Yiling Chen , Tao Lin , Ariel D. Procaccia +2 more

We introduce and study the problem of detecting whether an agent is updating their prior beliefs given new evidence in an optimal way that is Bayesian, or whether they are … We introduce and study the problem of detecting whether an agent is updating their prior beliefs given new evidence in an optimal way that is Bayesian, or whether they are biased towards their own prior. In our model, biased agents form posterior beliefs that are a convex combination of their prior and the Bayesian posterior, where the more biased an agent is, the closer their posterior is to the prior. Since we often cannot observe the agent's beliefs directly, we take an approach inspired by information design. Specifically, we measure an agent's bias by designing a signaling scheme and observing the actions they take in response to different signals, assuming that they are maximizing their own expected utility; our goal is to detect bias with a minimum number of signals. Our main results include a characterization of scenarios where a single signal suffices and a computationally efficient algorithm to compute optimal signaling schemes.

Chat View PDF

Learning Social Welfare Functions

2024-05-27

Kanad Shrikar Pardeshi , Itai Shapira , Ariel D. Procaccia +1 more

Is it possible to understand or imitate a policy maker's rationale by looking at past decisions they made? We formalize this question as the problem of learning social welfare functions … Is it possible to understand or imitate a policy maker's rationale by looking at past decisions they made? We formalize this question as the problem of learning social welfare functions belonging to the well-studied family of power mean functions. We focus on two learning tasks; in the first, the input is vectors of utilities of an action (decision or policy) for individuals in a group and their associated social welfare as judged by a policy maker, whereas in the second, the input is pairwise comparisons between the welfares associated with a given pair of utility vectors. We show that power mean functions are learnable with polynomial sample complexity in both cases, even if the comparisons are social welfare information is noisy. Finally, we design practical algorithms for these tasks and evaluate their performance.

Chat View PDF

Axioms for AI Alignment from Human Feedback

2024-05-23

Luise Ge , Daniel Halpern , Evi Micha +4 more

In the context of reinforcement learning from human feedback (RLHF), the reward function is generally derived from maximum likelihood estimation of a random utility model based on pairwise comparisons made … In the context of reinforcement learning from human feedback (RLHF), the reward function is generally derived from maximum likelihood estimation of a random utility model based on pairwise comparisons made by humans. The problem of learning a reward function is one of preference aggregation that, we argue, largely falls within the scope of social choice theory. From this perspective, we can evaluate different aggregation methods via established axioms, examining whether these methods meet or fail well-known standards. We demonstrate that both the Bradley-Terry-Luce Model and its broad generalizations fail to meet basic axioms. In response, we develop novel rules for learning reward functions with strong axiomatic guarantees. A key innovation from the standpoint of social choice is that our problem has a linear structure, which greatly restricts the space of feasible rules and leads to a new paradigm that we call linear social choice.

Chat View PDF

Optimal Engagement-Diversity Tradeoffs in Social Media

2024-05-08

Fabian Baumann , Daniel Halpern , Ariel D. Procaccia +3 more

Social media platforms are known to optimize user engagement with the help of algorithms. It is widely understood that this practice gives rise to echo chambers - users are mainly … Social media platforms are known to optimize user engagement with the help of algorithms. It is widely understood that this practice gives rise to echo chambers - users are mainly exposed to opinions that are similar to their own. In this paper, we ask whether echo chambers are an inevitable result of high engagement; we address this question in a novel model. Our main theoretical results establish bounds on the maximum engagement achievable under a diversity constraint, for suitable measures of engagement and diversity; we can therefore quantify the worst-case tradeoff between these two objectives. Our empirical results, based on real data from Twitter, chart the Pareto frontier of the engagement-diversity tradeoff.

Chat View PDF

Dynamic Placement in Refugee Resettlement

2024-03-22

Narges Ahani , Paul Gölz , Ariel D. Procaccia +2 more

Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. While the U.S. sets refugee capacities for communities on an annual basis, refugees arrive … Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. While the U.S. sets refugee capacities for communities on an annual basis, refugees arrive and must be placed over the course of the year. We introduce a dynamic allocation system based on potentials derived from dual prices of a linear programming (LP) relaxation to improve employment outcomes. Our algorithm achieves over 98% of the hindsight- optimal employment compared to under 90% of current greedy-like approaches. This dramatic improvement persists even when we incorporate a vast array of practical features of the refugee resettlement process including indivisible families, batching, and uncertainty with respect to the number of future arrivals. Our algorithm is now part of the Annie ™ Moore optimization software used by a leading American refugee resettlement agency.

Chat View PDF

Multi-Apartment Rent Division

2024-03-12

Ariel D. Procaccia , Benjamin F. Schiffer , Shirley Zhang

Rent division is the well-studied problem of fairly assigning rooms and dividing rent among a set of roommates within a single apartment. A shortcoming of existing solutions is that renters … Rent division is the well-studied problem of fairly assigning rooms and dividing rent among a set of roommates within a single apartment. A shortcoming of existing solutions is that renters are assumed to be considering apartments in isolation, whereas in reality, renters can choose among multiple apartments. In this paper, we generalize the rent division problem to the multi-apartment setting, where the goal is to both fairly choose an apartment among a set of alternatives and fairly assign rooms and rents within the chosen apartment. Our main contribution is a generalization of envy-freeness called rearrangeable envy-freeness. We show that a solution satisfying rearrangeable envy-freeness is guaranteed to exist and that it is possible to optimize over all rearrangeable envy-free solutions in polynomial time. We also define an even stronger fairness notion called universal envy-freeness and study its existence when values are drawn randomly.

Chat View PDF

Dynamic Placement in Refugee Resettlement

2023-09-28

Narges Ahani , Paul Gölz , Ariel D. Procaccia +2 more

Boosting Employment of Resettled Refugees Whether a resettled refugee finds employment in the United States depends in no small part on which host community they are first welcomed to. Every … Boosting Employment of Resettled Refugees Whether a resettled refugee finds employment in the United States depends in no small part on which host community they are first welcomed to. Every week, resettlement agencies are assigned a group of refugees who they are required to place in communities around the country. In “Dynamic Placement in Refugee Resettlement,” Ahani, Gölz, Procaccia, Teytelboym, and Trapp develop an allocation system that recommends where to place an incoming refugee family with the aim of boosting the overall employment success. Should capacities in high-employment areas be used up as quickly as possible, or does it make sense to hold back for a perfect match? The simple algorithm, based on two-stage stochastic programming, achieves over 98% of the hindsight-optimal employment, compared with under 90% for the greedy-like approaches that were previously used in practice. Their algorithm is now part of the Annie™ MOORE optimization software used by a leading American refugee resettlement agency.

Chat View PDF

You Can Have Your Cake and Redistrict It Too

2023-07-07

Gerdus Benadè , Ariel D. Procaccia , Jamie Tucker-Foltz

Chat View PDF

In Defense of Liquid Democracy

2023-07-07

Daniel Halpern , Joseph Y. Halpern , Ali Jadbabaie +3 more

Liquid democracy is a voting paradigm that is conceptually situated between direct democracy, in which voters have direct influence over decisions, and representative democracy, where voters choose delegates who represent … Liquid democracy is a voting paradigm that is conceptually situated between direct democracy, in which voters have direct influence over decisions, and representative democracy, where voters choose delegates who represent them for a period of time. Under liquid democracy, voters have a choice: they can either vote directly on an issue like in direct democracy, or delegate their vote to another voter, entrusting them to vote on their behalf. The defining feature of liquid democracy is that these delegations are transitive: if voter 1 delegates to voter 2 and voter 2 delegates to voter 3, then voter 3 votes (or delegates) on behalf of all three voters.

Chat View PDF

Welfare-Maximizing Pooled Testing

2023-07-07

Simon Finster , Michelle González Amador , Edwin Lock +3 more

In an epidemic, how should an organization with limited testing resources safely return to in-person activities after a lockdown? We study this question in a setting where the population is … In an epidemic, how should an organization with limited testing resources safely return to in-person activities after a lockdown? We study this question in a setting where the population is heterogeneous in both utility for in-person activities and probability of infection. During a period of re-integration, tests can be used as a certificate of non-infection, whereby those in negative tests are permitted to return to in-person activities for a designated amount of time. Under the assumption that samples can be pooled, the question of how to allocate a limited testing budget in the population to maximize the aggregate utility (i.e. welfare) of negatively-tested individuals who return to in-person activities is non-trivial, with a large space of potential testing allocations.

Chat View PDF

Distortion Under Public-Spirited Voting

2023-07-07

Bailey Flanigan , Ariel D. Procaccia , Sven Wang

A key promise of voting is that, by accounting for all constituents' preferences, it produces decisions that benefit society overall. It is alarming, then, that all deterministic voting rules have … A key promise of voting is that, by accounting for all constituents' preferences, it produces decisions that benefit society overall. It is alarming, then, that all deterministic voting rules have unbounded distortion (i.e., arbitrarily suboptimal social welfare). Existing work usually circumvents this stark impossibility by assuming restrictions on voters' possible latent utilities [Anshelevich et al. 2021]; however, it is not clear whether such assumptions reliably hold in practice, because voters' utilities are, to a large degree, inherent.

Chat View PDF

Representation with Incomplete Votes

2023-06-26

Daniel Halpern , Gregory Kehne , Ariel D. Procaccia +2 more

Platforms for online civic participation rely heavily on methods for condensing thousands of comments into a relevant handful, based on whether participants agree or disagree with them. These methods should … Platforms for online civic participation rely heavily on methods for condensing thousands of comments into a relevant handful, based on whether participants agree or disagree with them. These methods should guarantee fair representation of the participants, as their outcomes may affect the health of the conversation and inform impactful downstream decisions. To that end, we draw on the literature on approval-based committee elections. Our setting is novel in that the approval votes are incomplete since participants will typically not vote on all comments. We prove that this complication renders non-adaptive algorithms impractical in terms of the amount of information they must gather. Therefore, we develop an adaptive algorithm that uses information more efficiently by presenting incoming participants with statements that appear promising based on votes by previous participants. We prove that this method satisfies commonly used notions of fair representation, even when participants only vote on a small fraction of comments. Finally, an empirical evaluation using real data shows that the proposed algorithm provides representative outcomes in practice.

Chat View PDF

Optimal Engagement-Diversity Tradeoffs in Social Media

2023-01-01

Fabian Baumann , Daniel Halpern , Ariel D. Procaccia +3 more

Social media platforms are known to optimize user engagement with the help of algorithms. It is widely understood that this practice gives rise to echo chambers\emdash users are mainly exposed … Social media platforms are known to optimize user engagement with the help of algorithms. It is widely understood that this practice gives rise to echo chambers\emdash users are mainly exposed to opinions that are similar to their own. In this paper, we ask whether echo chambers are an inevitable result of high engagement; we address this question in a novel model. Our main theoretical results establish bounds on the maximum engagement achievable under a diversity constraint, for suitable measures of engagement and diversity; we can therefore quantify the worst-case tradeoff between these two objectives. Our empirical results, based on real data from Twitter, chart the Pareto frontier of the engagement-diversity tradeoff.

Chat View PDF

Distortion Under Public-Spirited Voting

2023-01-01

Bailey Flanigan , Ariel D. Procaccia , Sven Wang

A key promise of democratic voting is that, by accounting for all constituents' preferences, it produces decisions that benefit the constituency overall. It is alarming, then, that all deterministic voting … A key promise of democratic voting is that, by accounting for all constituents' preferences, it produces decisions that benefit the constituency overall. It is alarming, then, that all deterministic voting rules have unbounded distortion: all such rules - even under reasonable conditions - will sometimes select outcomes that yield essentially no value for constituents. In this paper, we show that this problem is mitigated by voters being public-spirited: that is, when deciding how to rank alternatives, voters weigh the common good in addition to their own interests. We first generalize the standard voting model to capture this public-spirited voting behavior. In this model, we show that public-spirited voting can substantially - and in some senses, monotonically - reduce the distortion of several voting rules. Notably, these results include the finding that if voters are at all public-spirited, some voting rules have constant distortion in the number of alternatives. Further, we demonstrate that these benefits are robust to adversarial conditions likely to exist in practice. Taken together, our results suggest an implementable approach to improving the welfare outcomes of elections: democratic deliberation, an already-mainstream practice that is believed to increase voters' public spirit.

Chat View PDF

You Can Have Your Cake and Redistrict It Too

2023-01-01

Gerdus Benadè , Ariel D. Procaccia , Jamie Tucker-Foltz

The design of algorithms for political redistricting generally takes one of two approaches: optimize an objective such as compactness or, drawing on fair division, construct a protocol whose outcomes guarantee … The design of algorithms for political redistricting generally takes one of two approaches: optimize an objective such as compactness or, drawing on fair division, construct a protocol whose outcomes guarantee partisan fairness. We aim to have the best of both worlds by optimizing an objective subject to a binary fairness constraint. As the fairness constraint we adopt the geometric target, which requires the number of seats won by each party to be at least the average (rounded down) of its outcomes under the worst and best partitions of the state. To study the feasibility of this approach, we introduce a new model of redistricting that closely mirrors the classic model of cake-cutting. This model has two innovative features. First, in any part of the state there is an underlying 'density' of voters with political leanings toward any given party, making it impossible to finely separate voters for different parties into different districts. This captures a realistic constraint that previously existing theoretical models of redistricting tend to ignore. Second, parties may disagree on the distribution of voters - whether by genuine disagreement or attempted strategic behavior. In the absence of a 'ground truth' distribution, a redistricting algorithm must therefore aim to simultaneously be fair to each party with respect to its own reported data. Our main theoretical result is that, surprisingly, the geometric target is always feasible with respect to arbitrarily diverging data sets on how voters are distributed. Any standard for fairness is only useful if it can be readily satisfied in practice. Our empirical results, which use real election data and maps of six US states, demonstrate that the geometric target is always feasible, and that imposing it as a fairness constraint comes at almost no cost to three well-studied optimization objectives.

Chat View PDF

The Distortion of Binomial Voting Defies Expectation

2023-01-01

Yannai A. Gonczarowski , Gregory Kehne , Ariel D. Procaccia +2 more

In computational social choice, the distortion of a voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outcome. This concept has … In computational social choice, the distortion of a voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outcome. This concept has been investigated extensively, but only through a worst-case lens. Instead, we study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting, which provides strong distribution-independent guarantees for both expected distortion and expected welfare.

Chat View PDF

Generative Social Choice

2023-01-01

Sara Fish , Paul Gölz , David C. Parkes +4 more

Traditionally, social choice theory has only been applicable to choices among a few predetermined alternatives but not to more complex decisions such as collectively selecting a textual statement. We introduce … Traditionally, social choice theory has only been applicable to choices among a few predetermined alternatives but not to more complex decisions such as collectively selecting a textual statement. We introduce generative social choice, a framework that combines the mathematical rigor of social choice theory with the capability of large language models to generate text and extrapolate preferences. This framework divides the design of AI-augmented democratic processes into two components: first, proving that the process satisfies rigorous representation guarantees when given access to oracle queries; second, empirically validating that these queries can be approximately implemented using a large language model. We apply this framework to the problem of generating a slate of statements that is representative of opinions expressed as free-form text; specifically, we develop a democratic process with representation guarantees and use this process to represent the opinions of participants in a survey about chatbot personalization. We find that 93 out of 100 participants feel "mostly" or "perfectly" represented by the slate of five statements we extracted.

Chat View PDF

In This Apportionment Lottery, the House Always Wins

2022-07-12

Paul Gölz , Dominik Peters , Ariel D. Procaccia

Apportionment is the problem of distributing h indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a … Apportionment is the problem of distributing h indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett [2004] suggested to apportion seats in a randomized way such that each state receives exactly their proportional share qi of seats in expectation (ex ante proportionality) and receives either ↾qi↿ or ⇂qi⇃ many seats ex post (quota). However, there is a vast space of randomized apportionment methods satisfying these two axioms, and so we additionally consider prominent axioms from the apportionment literature. Our main result is a randomized method satisfying quota, ex ante proportionality and house monotonicity — a property that prevents paradoxes when the number of seats changes and which we require to hold ex post. This result is based on a generalization of dependent rounding on bipartite graphs, which we call cumulative rounding and which might be of independent interest, as we demonstrate via applications beyond apportionment.

Chat View PDF

The phantom steering effect in Q&A websites

2022-01-08

Nicholas Hoernle , Gregory Kehne , Ariel D. Procaccia +1 more

Abstract Virtual rewards, such as badges, are commonly used in online platforms as incentives for promoting contributions from a userbase. It is widely accepted that such rewards “steer” people’s behaviour … Abstract Virtual rewards, such as badges, are commonly used in online platforms as incentives for promoting contributions from a userbase. It is widely accepted that such rewards “steer” people’s behaviour towards increasing their rate of contributions before obtaining the reward. This paper provides a new probabilistic model of user behaviour in the presence of threshold rewards, such a badges. We find, surprisingly, that while steering does affect a minority of the population, the majority of users do not change their behaviour around the achievement of these virtual rewards. In particular, we find that only approximately 5–30% of Stack Overflow users who achieve the rewards appear to respond to the incentives. This result is based on the analysis of thousands of users’ activity patterns before and after they achieve the reward. Our conclusion is that the phenomenon of steering is less common than has previously been claimed. We identify a statistical phenomenon, termed “Phantom Steering”, that can account for the interaction data of the users who do not respond to the reward. The presence of phantom steering may have contributed to some previous conclusions about the ubiquity of steering. We conduct a qualitative survey of the users on Stack Overflow which supports our results, suggesting that the motivating factors behind user behaviour are complex, and that some of the online incentives used in Stack Overflow may not be solely responsible for changes in users’ contribution rates.

Chat View PDF

Compact Redistricting Plans Have Many Spanning Trees

2022-01-01

Ariel D. Procaccia , Jamie Tucker-Foltz

Previous chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Compact Redistricting Plans Have Many Spanning TreesAriel D. Procaccia and Jamie Tucker-FoltzAriel D. Procaccia and Jamie … Previous chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Compact Redistricting Plans Have Many Spanning TreesAriel D. Procaccia and Jamie Tucker-FoltzAriel D. Procaccia and Jamie Tucker-Foltzpp.3754 - 3771Chapter DOI:https://doi.org/10.1137/1.9781611977073.148PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. There are influential Markov chain Monte Carlo methods for doing so that are based on sampling and splitting random spanning trees. Empirical evidence suggests that the distributions such algorithms sample from place higher weight on more "compact" redistricting plans, which is a practically useful and desirable property. In this paper, we confirm these observations analytically, establishing an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled. This result provides theoretical underpinnings for algorithms that are already making a significant real-world impact. Previous chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771

Chat View PDF

In This Apportionment Lottery, the House Always Wins

2022-01-01

Paul Gölz , Dominik Peters , Ariel D. Procaccia

Apportionment is the problem of distributing $h$ indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a … Apportionment is the problem of distributing $h$ indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett (2004) suggested to apportion seats in a randomized way such that each state receives exactly their proportional share $q_i$ of seats in expectation (ex ante proportionality) and receives either $\lfloor q_i \rfloor$ or $\lceil q_i \rceil$ many seats ex post (quota). However, there is a vast space of randomized apportionment methods satisfying these two axioms, and so we additionally consider prominent axioms from the apportionment literature. Our main result is a randomized method satisfying quota, ex ante proportionality and house monotonicity - a property that prevents paradoxes when the number of seats changes and which we require to hold ex post. This result is based on a generalization of dependent rounding on bipartite graphs, which we call cumulative rounding and which might be of independent interest, as we demonstrate via applications beyond apportionment.

Chat View PDF

Welfare-Maximizing Pooled Testing

2022-01-01

Edwin Lock , Francisco J. Marmolejo-Cossío , Evi Micha +1 more

Large-scale testing is crucial in pandemic containment, but resources are often prohibitively constrained. We study the optimal application of pooled testing for populations that are heterogeneous with respect to an … Large-scale testing is crucial in pandemic containment, but resources are often prohibitively constrained. We study the optimal application of pooled testing for populations that are heterogeneous with respect to an individual's infection probability and utility that materializes if included in a negative test. We show that the welfare gain from overlapping testing over non-overlapping testing is bounded. Moreover, non-overlapping allocations, which are both conceptually and logistically simpler to implement, are empirically near-optimal, and we design a heuristic mechanism for finding these near-optimal test allocations. In numerical experiments, we highlight the efficacy and viability of our heuristic in practice. We also implement and provide experimental evidence on the benefits of utility-weighted pooled testing in a real-world setting. Our pilot study at a higher education research institute in Mexico finds no evidence that performance and mental health outcomes of participants in our testing regime are worse than under the first-best counterfactual of full access for individuals without testing.

Chat View PDF

Representation with Incomplete Votes

2022-01-01

Daniel Halpern , Gregory Kehne , Ariel D. Procaccia +2 more

Chat View PDF

The Fluid Mechanics of Liquid Democracy

2021-10-16

Paul Gölz , Anson Kahng , Simon Mackenzie +1 more

Liquid democracy is the principle of making collective decisions by letting agents transitively delegate their votes. Despite its significant appeal, it has become apparent that a weakness of liquid democracy … Liquid democracy is the principle of making collective decisions by letting agents transitively delegate their votes. Despite its significant appeal, it has become apparent that a weakness of liquid democracy is that a small subset of agents may gain massive influence. To address this, we propose to change the current practice by allowing agents to specify multiple delegation options instead of just one. Much like in nature, where—fluid mechanics teaches us—liquid maintains an equal level in connected vessels, we seek to control the flow of votes in a way that balances influence as much as possible. Specifically, we analyze the problem of choosing delegations to approximately minimize the maximum number of votes entrusted to any agent by drawing connections to the literature on confluent flow. We also introduce a random graph model for liquid democracy and use it to demonstrate the benefits of our approach both theoretically and empirically.

Chat View PDF

Compact Redistricting Plans Have Many Spanning Trees.

2021-09-27

Ariel D. Procaccia , Jamie Tucker-Foltz

In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks … In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. There are influential Markov chain Monte Carlo methods for doing so that are based on sampling and splitting random spanning trees. Empirical evidence suggests that the distributions such algorithms sample from place higher weight on more compact redistricting plans, which is a practically useful and desirable property. In this paper, we confirm these observations analytically, establishing an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled. This result provides theoretical underpinnings for algorithms that are already making a significant real-world impact.

In Defense of Fluid Democracy.

2021-07-25

Daniel Halpern , Joseph Y. Halpern , Ali Jadbabaie +3 more

Fluid democracy is a voting paradigm that allows voters to choose between directly voting and transitively delegating their votes to other voters. While fluid democracy has been viewed as a … Fluid democracy is a voting paradigm that allows voters to choose between directly voting and transitively delegating their votes to other voters. While fluid democracy has been viewed as a system that can combine the best aspects of direct and representative democracy, it can also result in situations where few voters amass a large amount of influence. To analyze the impact of this shortcoming, we consider what has been called an epistemic setting, where voters decide on a binary issue for which there is a ground truth. Previous work has shown that under certain assumptions on the delegation mechanism, the concentration of power is so severe that fluid democracy is less likely to identify the ground truth than direct voting. We examine different, arguably more realistic, classes of mechanisms, and prove they behave well by ensuring that (with high probability) there is a limit on concentration of power. Our proofs demonstrate that delegations can be treated as stochastic processes and that they can be compared to well-known processes from the literature -- such as preferential attachment and multi-types branching process -- that are sufficiently bounded for our purposes. Our results suggest that the concerns raised about fluid democracy can be overcome, thereby bolstering the case for this emerging paradigm.

Chat View PDF

Dynamic Placement in Refugee Resettlement

2021-07-18

Narges Ahani , Paul Gölz , Ariel D. Procaccia +2 more

Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. Each week, a resettlement agency is assigned a batch of refugees by the United … Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. Each week, a resettlement agency is assigned a batch of refugees by the United States government. The agency must place these refugees in its local affiliates, while respecting the affiliates' yearly capacities. We develop an allocation system that suggests where to place an incoming refugee, in order to improve total employment success. Our algorithm is based on two-stage stochastic programming and achieves over 98 percent of the hindsight-optimal employment, compared to under 90 percent of current greedy-like approaches. This dramatic improvement persists even when we incorporate a vast array of practical features of the refugee resettlement process including indivisible families, batching, and uncertainty with respect to the number of future arrivals. Our algorithm is now part of the Annie MOORE optimization software used by a leading American refugee resettlement agency.

Chat View PDF

District-Fair Participatory Budgeting

2021-05-18

D Ellis Hershkowitz , Anson Kahng , Dominik Peters +1 more

Participatory budgeting is a method used by city governments to select public projects to fund based on residents' votes. Many cities use participatory budgeting at a district level. Typically, a … Participatory budgeting is a method used by city governments to select public projects to fund based on residents' votes. Many cities use participatory budgeting at a district level. Typically, a budget is divided among districts proportionally to their population, and each district holds an election over local projects and then uses its budget to fund the projects most preferred by its voters. However, district-level participatory budgeting can yield poor social welfare because it does not necessarily fund projects supported across multiple districts. On the other hand, decision making that only takes global social welfare into account can be unfair to districts: A social-welfare-maximizing solution might not fund any of the projects preferred by a district, despite the fact that its constituents pay taxes to the city. Thus, we study how to fairly maximize social welfare in a participatory budgeting setting with a single city-wide election. We propose a notion of fairness that guarantees each district at least as much welfare as it would have received in a district-level election. We show that, although optimizing social welfare subject to this notion of fairness is NP-hard, we can efficiently construct a lottery over welfare-optimal outcomes that is fair in expectation. Moreover, we show that, when we are allowed to slightly relax fairness, we can efficiently compute a fair solution that is welfare-maximizing, but which may overspend the budget.

Chat View PDF

Loss Functions, Axioms, and Peer Review

2021-04-25

Ritesh Noothigattu , Nihar B. Shah , Ariel D. Procaccia

It is common to see a handful of reviewers reject a highly novel paper, because they view, say, extensive experiments as far more important than novelty, whereas the community as … It is common to see a handful of reviewers reject a highly novel paper, because they view, say, extensive experiments as far more important than novelty, whereas the community as a whole would have embraced the paper. More generally, the disparate mapping of criteria scores to final recommendations by different reviewers is a major source of inconsistency in peer review. In this paper we present a framework inspired by empirical risk minimization (ERM) for learning the community's aggregate mapping. The key challenge that arises is the specification of a loss function for ERM. We consider the class of L(p,q) loss functions, which is a matrix-extension of the standard class of Lp losses on vectors; here the choice of the loss function amounts to choosing the hyperparameters p and q. To deal with the absence of ground truth in our problem, we instead draw on computational social choice to identify desirable values of the hyperparameters p and q. Specifically, we characterize p=q=1 as the only choice of these hyperparameters that satisfies three natural axiomatic properties. Finally, we implement and apply our approach to reviews from IJCAI 2017.

Chat View PDF

Fairly Allocating Many Goods with Few Queries

2021-01-01

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 16 January 2020Accepted: 10 January 2021Published online: 15 April 2021Keywordsenvy-freeness, fair division, algorithms, … Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 16 January 2020Accepted: 10 January 2021Published online: 15 April 2021Keywordsenvy-freeness, fair division, algorithms, query complexityAMS Subject Headings68Q25, 91B32Publication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec

Chat View PDF

In Defense of Liquid Democracy

2021-01-01

Daniel Halpern , Joseph Y. Halpern , Ali Jadbabaie +3 more

Chat View PDF

District-Fair Participatory Budgeting

2021-01-01

D Ellis Hershkowitz , Anson Kahng , Dominik Peters +1 more

Chat View PDF

Neutralizing Self-Selection Bias in Sampling for Sortition

2020-06-18

Bailey Flanigan , Paul Gölz , Anupam Gupta +1 more

Sortition is a political system in which decisions are made by panels of randomly selected citizens. The process for selecting a sortition panel is traditionally thought of as uniform sampling … Sortition is a political system in which decisions are made by panels of randomly selected citizens. The process for selecting a sortition panel is traditionally thought of as uniform sampling without replacement, which has strong fairness properties. In practice, however, sampling without replacement is not possible since only a fraction of agents is willing to participate in a panel when invited, and different demographic groups participate at different rates. In order to still produce panels whose composition resembles that of the population, we develop a sampling algorithm that restores close-to-equal representation probabilities for all agents while satisfying meaningful demographic quotas. As part of its input, our algorithm requires probabilities indicating how likely each volunteer in the pool was to participate. Since these participation probabilities are not directly observable, we show how to learn them, and demonstrate our approach using data on a real sortition panel combined with information on the general population in the form of publicly available survey data.

The Goal-Gradient Hypothesis in Stack Overflow.

2020-02-14

Nicholas Hoernle , Gregory Kehne , Ariel D. Procaccia +1 more

Chat View PDF

The Phantom Steering Effect in Q&A Websites

2020-01-01

Nicholas Hoernle , Gregory Kehne , Ariel D. Procaccia +1 more

Badges are commonly used in online platforms as incentives for promoting contributions. It is widely accepted that badges "steer" people's behavior toward increasing their rate of contributions before obtaining the … Badges are commonly used in online platforms as incentives for promoting contributions. It is widely accepted that badges "steer" people's behavior toward increasing their rate of contributions before obtaining the badge. This paper provides a new probabilistic model of user behavior in the presence of badges. By applying the model to data from thousands of users on the Q&A site Stack Overflow, we find that steering is not as widely applicable as was previously understood. Rather, the majority of users remain apathetic toward badges, while still providing a substantial number of contributions to the site. An interesting statistical phenomenon, termed "Phantom Steering," accounts for the interaction data of these users and this may have contributed to some previous conclusions about steering. Our results suggest that a small population, approximately 20%, of users respond to the badge incentives. Moreover, we conduct a qualitative survey of the users on Stack Overflow which provides further evidence that the insights from the model reflect the true behavior of the community. We argue that while badges might contribute toward a suite of effective rewards in an online system, research into other aspects of reward systems such as Stack Overflow reputation points should become a focus of the community.

Chat View PDF

Fair Division with Binary Valuations: One Rule to Rule Them All

2020-01-01

Daniel Halpern , Ariel D. Procaccia , Alexandros Psomas +1 more

Chat View PDF

Learning and Planning in the Feature Deception Problem

2020-01-01

Zheyuan Ryan Shi , Ariel D. Procaccia , Kevin Chan +5 more

Chat View PDF

Fair Division with Binary Valuations: One Rule to Rule Them All

2020-01-01

Daniel Halpern , Ariel D. Procaccia , Alexandros Psomas +1 more

We study fair allocation of indivisible goods among agents. Prior research focuses on additive agent preferences, which leads to an impossibility when seeking truthfulness, fairness, and efficiency. We show that … We study fair allocation of indivisible goods among agents. Prior research focuses on additive agent preferences, which leads to an impossibility when seeking truthfulness, fairness, and efficiency. We show that when agents have binary additive preferences, a compelling rule -- maximum Nash welfare (MNW) -- provides all three guarantees. Specifically, we show that deterministic MNW with lexicographic tie-breaking is group strategyproof in addition to being envy-free up to one good and Pareto optimal. We also prove that fractional MNW -- known to be group strategyproof, envy-free, and Pareto optimal -- can be implemented as a distribution over deterministic MNW allocations, which are envy-free up to one good. Our work establishes maximum Nash welfare as the ultimate allocation rule in the realm of binary additive preferences.

Chat View PDF

Neutralizing Self-Selection Bias in Sampling for Sortition

2020-01-01

Bailey Flanigan , Paul Gölz , Anupam Gupta +1 more

Chat View PDF

The Provable Virtue of Laziness in Motion Planning

2019-07-28

Nika Haghtalab , Simon Mackenzie , Ariel D. Procaccia +2 more

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the … The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm such as manipulation in cluttered environments and planning for robots in surgical settings; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

Chat View PDF

Fairly Allocating Many Goods with Few Queries

2019-07-17

Hoon Oh , Ariel D. Procaccia , Warut Suksompong

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up … We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

Chat View PDF

Migration as Submodular Optimization

2019-07-17

Paul Gölz , Ariel D. Procaccia

Migration presents sweeping societal challenges that have recently attracted significant attention from the scientific community. One of the prominent approaches that have been suggested employs optimization and machine learning to … Migration presents sweeping societal challenges that have recently attracted significant attention from the scientific community. One of the prominent approaches that have been suggested employs optimization and machine learning to match migrants to localities in a way that maximizes the expected number of migrants who find employment. However, it relies on a strong additivity assumption that, we argue, does not hold in practice, due to competition effects; we propose to enhance the data-driven approach by explicitly optimizing for these effects. Specifically, we cast our problem as the maximization of an approximately submodular function subject to matroid constraints, and prove that the worst-case guarantees given by the classic greedy algorithm extend to this setting. We then present three different models for competition effects, and show that they all give rise to submodular objectives. Finally, we demonstrate via simulations that our approach leads to significant gains across the board.

Chat View PDF

Learning and Planning in Feature Deception Games.

2019-05-13

Zheyuan Ryan Shi , Ariel D. Procaccia , Kevin Chan +5 more

Today's high-stakes adversarial interactions feature attackers who constantly breach the ever-improving security measures. Deception mitigates the defender's loss by misleading the attacker to make suboptimal decisions. In order to formally … Today's high-stakes adversarial interactions feature attackers who constantly breach the ever-improving security measures. Deception mitigates the defender's loss by misleading the attacker to make suboptimal decisions. In order to formally reason about deception, we introduce the feature deception game (FDG), a domain-independent game-theoretic model and present a learning and planning framework. We make the following contributions. (1) We show that we can uniformly learn the adversary's preferences using data from a modest number of deception strategies. (2) We propose an approximation algorithm for finding the optimal deception strategy and show that the problem is NP-hard. (3) We perform extensive experiments to empirically validate our methods and results.

Chat View PDF

Strategyproof linear regression in high dimensions

2019-05-07

Yiling Chen , Chara Podimata , Ariel D. Procaccia +1 more

In this letter, we outline some of the results from our recent work, which is part of an emerging line of research at the intersection of machine learning and mechanism … In this letter, we outline some of the results from our recent work, which is part of an emerging line of research at the intersection of machine learning and mechanism design aiming to avoid noise in training data by correctly aligning the incentives of data sources. Specifically, we focus on the ubiquitous problem of linear regression, where strategyproof mechanisms have previously been identified in two dimensions. In our setting, agents have single-peaked preferences and can manipulate only their response variables. Our main contribution is the discovery of a family of group strategyproof linear regression mechanisms in any number of dimensions, which we call generalized resistant hyperplane mechanisms. The game-theoretic properties of these mechanisms --- and, in fact, their very existence --- are established through a connection to a discrete version of the Ham Sandwich Theorem.

Chat View PDF

Envy-Free Classification

2019-01-01

Maria-Florina Balcan , Travis Dick , Ritesh Noothigattu +1 more

In classic fair division problems such as cake cutting and rent division, envy-freeness requires that each individual (weakly) prefer his allocation to anyone else's. On a conceptual level, we argue … In classic fair division problems such as cake cutting and rent division, envy-freeness requires that each individual (weakly) prefer his allocation to anyone else's. On a conceptual level, we argue that envy-freeness also provides a compelling notion of fairness for classification tasks, especially when individuals have heterogeneous preferences. Our technical focus is the generalizability of envy-free classification, i.e., understanding whether a classifier that is envy free on a sample would be almost envy free with respect to the underlying distribution with high probability. Our main result establishes that a small sample is sufficient to achieve such guarantees, when the classifier in question is a mixture of deterministic classifiers that belong to a family of low Natarajan dimension.

Chat View PDF

Learning and Planning in the Feature Deception Problem

2019-01-01

Zheyuan Ryan Shi , Ariel D. Procaccia , Kevin Chan +5 more

Today's high-stakes adversarial interactions feature attackers who constantly breach the ever-improving security measures. Deception mitigates the defender's loss by misleading the attacker to make suboptimal decisions. In order to formally … Today's high-stakes adversarial interactions feature attackers who constantly breach the ever-improving security measures. Deception mitigates the defender's loss by misleading the attacker to make suboptimal decisions. In order to formally reason about deception, we introduce the feature deception problem (FDP), a domain-independent model and present a learning and planning framework for finding the optimal deception strategy, taking into account the adversary's preferences which are initially unknown to the defender. We make the following contributions. (1) We show that we can uniformly learn the adversary's preferences using data from a modest number of deception strategies. (2) We propose an approximation algorithm for finding the optimal deception strategy given the learned preferences and show that the problem is NP-hard. (3) We perform extensive experiments to validate our methods and results. In addition, we provide a case study of the credit bureau network to illustrate how FDP implements deception on a real-world problem.

Chat View PDF

Common Coauthors

Coauthor	Papers Together
Daniel Halpern	11
Ritesh Noothigattu	11
Paul Gölz	11
Nika Haghtalab	9
Jeremiah Blocki	8
Nisarg Shah	7
Simina Brânzei	6
Jamie Tucker-Foltz	6
Anson Kahng	6
Gregory Kehne	6
Elchanan Mossel	6
Arunesh Sinha	5
Iyad Rahwan	5
Siddhartha S Srinivasa	5
Manuel Wüthrich	5
Simon Mackenzie	5
Ioannis Caragiannis	5
Anupam Datta	5
Nicolas Christin	5
Yiling Chen	4
Bailey Flanigan	4
Maria-Florina Balcan	4
Oren Salzman	4
Shirley Zhang	4
Dominik Peters	4
D Ellis Hershkowitz	4
Itai Shapira	4
Chara Podimata	3
Or Sheffet	3
Andrew C. Trapp	3
Sohan Dsouza	3
Joseph Y. Halpern	3
Charles Kamhoua	3
Kobi Gal	3
Fei Fang	3
Nicholas Hoernle	3
David Kurokawa	3
Ali Jadbabaie	3
Saranga Komanduri	3
Nihar B. Shah	3
Narges Ahani	3
Evi Micha	3
Noam Ben‐Asher	3
Snehalkumar S. Gaikwad	3
Zheyuan Ryan Shi	3
Pradeep Ravikumar	3
Edmond Awad	3
Manon Revel	3
Alexander Teytelboym	3
Kevin Chan	3

Commonly Cited References

Mechanism design for fair division

2013-06-16

Richard Cole , Vasilis Gkatzelis , Gagan Goel

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution … We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option.

Chat View PDF

Common voting rules as maximum likelihood estimators

2005-07-26

Vincent Conitzer , Tüomas Sandholm

Voting is a very general method of preference aggregation. A voting rule takes as input every voter's vote (typically, a ranking of the alternatives), and produces as output either just … Voting is a very general method of preference aggregation. A voting rule takes as input every voter's vote (typically, a ranking of the alternatives), and produces as output either just the winning alternative or a ranking of the alternatives. One potential view of voting is the following. There exists a outcome (winner/ranking), and each voter's vote corresponds to a noisy perception of this correct outcome. If we are given the noise model, then for any vector of votes, we can compute the maximum likelihood estimate of the correct outcome. This maximum likelihood estimate constitutes a voting rule. In this paper, we ask the following question: For which common voting rules does there exist a noise model such that the rule is the maximum likelihood estimate for that noise model? We require that the votes are drawn independently given the correct outcome (we show that without this restriction, all voting rules have the property). We study the question both for the case where outcomes are winners and for the case where outcomes are rankings. In either case, only some of the common voting rules have the property. Moreover, the sets of rules that satisfy the property are incomparable between the two cases (satisfying the property in the one case does not imply satisfying it in the other case).

Chat View PDF

NON-NULL RANKING MODELS. I

1957-01-01

C. L. Mallows

Journal Article NON-NULL RANKING MODELS. I Get access C. L. MALLOWS C. L. MALLOWS University CollegeLondon Search for other works by this author on: Oxford Academic Google Scholar Biometrika, Volume … Journal Article NON-NULL RANKING MODELS. I Get access C. L. MALLOWS C. L. MALLOWS University CollegeLondon Search for other works by this author on: Oxford Academic Google Scholar Biometrika, Volume 44, Issue 1-2, June 1957, Pages 114–130, https://doi.org/10.1093/biomet/44.1-2.114 Published: 01 June 1957

Uneven Splitting of Ham Sandwiches

2009-04-14

Felix Breuer

Chat View PDF

The Resistant Line and Related Regression Methods

1985-12-01

Iain M. Johnstone , Paul F. Velleman

Abstract In a bivariate (x, y) scatterplot the three-group resistant line is that line for which the median residual in each outer third of the data (ordered on x) is … Abstract In a bivariate (x, y) scatterplot the three-group resistant line is that line for which the median residual in each outer third of the data (ordered on x) is zero. It was proposed by Tukey as an exploratory method resistant to outliers in x and y and suited to hand calculation. A dual plot representation of the procedure yields a fast, convergent algorithm, nonparametric confidence intervals for the slope, consistency, influence function, and asymptotic normality results. Monte Carlo results show that small sample efficiencies exceed their asymptotic values in important cases. Both breakdown and efficiency are adequate for exploratory work. Replacing medians by other M-estimators of location increases efficiency substantially without affecting breakdown or computational complexity. The method thus combines bounded influence and acceptable efficiency with conceptual and computational simplicity.

Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy

2017-07-25

Zoé Christoff , Davide Grossi

The paper provides an analysis of the voting method known as delegable proxy voting, or liquid democracy. The analysis first positions liquid democracy within the theory of binary aggregation. It … The paper provides an analysis of the voting method known as delegable proxy voting, or liquid democracy. The analysis first positions liquid democracy within the theory of binary aggregation. It then focuses on two issues of the system: the occurrence of delegation cycles; and the effect of delegations on individual rationality when voting on logically interdependent propositions. It finally points to proposals on how the system may be modified in order to address the above issues.

Chat View PDF

Quizz

2014-04-07

Panagiotis G. Ipeirotis , Evgeniy Gabrilovich

We describe Quizz, a gamified crowdsourcing system that simultaneously assesses the knowledge of users and acquires new knowledge from them. Quizz operates by asking users to complete short quizzes on … We describe Quizz, a gamified crowdsourcing system that simultaneously assesses the knowledge of users and acquires new knowledge from them. Quizz operates by asking users to complete short quizzes on specific topics; as a user answers the quiz questions, Quizz estimates the user's competence. To acquire new knowledge, Quizz also incorporates questions for which we do not have a known answer; the answers given by competent users provide useful signals for selecting the correct answers for these questions. Quizz actively tries to identify knowledgeable users on the Internet by running advertising campaigns, effectively leveraging the targeting capabilities of existing, publicly available, ad placement services. Quizz quantifies the contributions of the users using information theory and sends feedback to the advertisingsystem about each user. The feedback allows the ad targeting mechanism to further optimize ad placement.

Chat View PDF

Truthful Linear Regression

2015-06-10

Rachel Cummings , Stratis Ioannidis , Katrina Ligett

We consider the problem of fitting a linear model to data held by individuals who are concerned about their privacy. Incentivizing most players to truthfully report their data to the … We consider the problem of fitting a linear model to data held by individuals who are concerned about their privacy. Incentivizing most players to truthfully report their data to the analyst constrains our design to mechanisms that provide a privacy guarantee to the participants; we use differential privacy to model individuals' privacy losses. This immediately poses a problem, as differentially private computation of a linear model necessarily produces a biased estimation, and existing approaches to design mechanisms to elicit data from privacy-sensitive individuals do not generalize well to biased estimators. We overcome this challenge through an appropriate design of the computation and payment scheme.

Chat View PDF

Engaging with massive online courses

2014-04-07

Ashton Anderson , Daniel P. Huttenlocher , Jon Kleinberg +1 more

The Web has enabled one of the most visible recent developments in education---the deployment of massive open online courses. With their global reach and often staggering enrollments, MOOCs have the … The Web has enabled one of the most visible recent developments in education---the deployment of massive open online courses. With their global reach and often staggering enrollments, MOOCs have the potential to become a major new mechanism for learning. Despite this early promise, however, MOOCs are still relatively unexplored and poorly understood.

Chat View PDF

Generalized “sandwich” theorems

1942-06-01

A. H. Stone , John W. Tukey

Generalized Ham-Sandwich Cuts

2009-09-10

William Steiger , Jihui Zhao

Chat View PDF

A stronger conclusion to the classical ham sandwich theorem

2011-03-08

John H. Elton , Theodore P. Hill

Slicing Convex Sets and Measures by a Hyperplane

2007-09-17

Imre Bárány , Alfredo Hubard , Jesús Jerónimo

Chat View PDF

Stochastic variational inference

2013-01-01

Matthew D. Hoffman , David M. Blei , Chong Wang +1 more

We develop stochastic variational inference, a scalable algorithm for approximating posterior distributions. We develop this technique for a large class of probabilistic models and we demonstrate it with two probabilistic … We develop stochastic variational inference, a scalable algorithm for approximating posterior distributions. We develop this technique for a large class of probabilistic models and we demonstrate it with two probabilistic topic models, latent Dirichlet allocation and the hierarchical Dirichlet process topic model. Using stochastic variational inference, we analyze several large collections of documents: 300K articles from Nature, 1.8M articles from The New York Times, and 3.8M articles from Wikipedia. Stochastic inference can easily handle data sets of this size and outperforms traditional variational inference, which can only handle a smaller subset. (We also show that the Bayesian nonparametric topic model outperforms its parametric counterpart.) Stochastic variational inference lets us apply complex Bayesian models to massive data sets.

Weighted Electoral Control

2015-04-20

Piotr Faliszewski , Edith Hemaspaandra , Lane A. Hemaspaandra

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting … Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.

Chat View PDF

The geometry of manipulation — A quantitative proof of the Gibbard-Satterthwaite theorem

2012-03-01

Marcus Isaksson , Guy Kindler , Elchanan Mossel

Chat View PDF

Asymptotically-optimal Motion Planning using lower bounds on cost

2015-05-01

Oren Salzman , Dan Halperin

Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply … Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply similar techniques to speed up sampling-based motion-planning algorithms, we use effective lower bounds on the cost between configurations to tightly estimate the cost-to-go. We then use these estimates in an anytime asymptotically-optimal algorithm which we call Motion Planning using Lower Bounds (MPLB). MPLB is based on the Fast Marching Trees (FMT*) algorithm [1] recently presented by Janson and Pavone. An advantage of our approach is that in many cases (especially as the number of samples grows) the weight of collision detection in the computation is almost negligible compared to the weight of nearest-neighbor queries. We prove that MPLB performs no more collision-detection calls than an anytime version of FMT*. Additionally, we demonstrate in simulations that for certain scenarios, the algorithmic tools presented here enable efficiently producing low-cost paths while spending only a small fraction of the running time on collision detection.

Chat View PDF

Notes on Convex Sets, Polytopes, Polyhedra, Combinatorial Topology, Voronoi Diagrams and Delaunay Triangulations

2008-01-01

Jean Gallier

Some basic mathematical tools such as convex sets, polytopes and combinatorial topology, are used quite heavily in applied fields such as geometric modeling, meshing, computer vision, medical imaging and robotics. … Some basic mathematical tools such as convex sets, polytopes and combinatorial topology, are used quite heavily in applied fields such as geometric modeling, meshing, computer vision, medical imaging and robotics. This report may be viewed as a tutorial and a set of notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi Diagrams and Delaunay Triangulations. It is intended for a broad audience of mathematically inclined readers. I have included a rather thorough treatment of the equivalence of V-polytopes and H-polytopes and also of the equivalence of V-polyhedra and H-polyhedra, which is a bit harder. In particular, the Fourier-Motzkin elimination method (a version of Gaussian elimination for inequalities) is discussed in some detail. I also included some material on projective spaces, projective maps and polar duality w.r.t. a nondegenerate quadric in order to define a suitable notion of ``projective polyhedron'' based on cones. To the best of our knowledge, this notion of projective polyhedron is new. We also believe that some of our proofs establishing the equivalence of V-polyhedra and H-polyhedra are new.

Chat View PDF

The number of spanning trees in graphs with a given degree sequence

1995-03-01

Alexandr Kostochka

Abstract Alon's [1] idea is slightly refined to prove that for each connected graph G with degree sequence 1<k = d 1 ≦d 2 ≦…≦d n the number C(G) of … Abstract Alon's [1] idea is slightly refined to prove that for each connected graph G with degree sequence 1<k = d 1 ≦d 2 ≦…≦d n the number C(G) of spanning trees of G satisfies the inequality. d(G)k −nO(log k/k ) ≦ C(G) ≦ d(G)/(n ‐ 1),. where d(G) = (II n i=1 d i ). An almost exact lower bound for C(G) for 3‐regular G on n vertices is also given. © 1994 John Wiley & Sons, Inc.

Chat View PDF

Approximately optimal mechanism design via differential privacy

2012-01-08

Kobbi Nissim , Rann Smorodinsky , Moshe Tennenholtz

We study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a generic mechanism that allows for approximate optimal implementation of insensitive objective … We study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a generic mechanism that allows for approximate optimal implementation of insensitive objective functions in ex-post Nash equilibrium. If, furthermore, values are private then the same mechanism is strategy proof. We cast our results onto two specific models: pricing and facility location. The mechanism we design is optimal up to an additive factor of the order of magnitude of one over the square root of the number of agents and involves no utility transfers.

Chat View PDF

Entropy estimate for high-dimensional monotonic functions

2006-10-31

Fuchang Gao , Jon A. Wellner

Chat View PDF

Clustering and preferential attachment in growing networks

2001-07-26

M. E. J. Newman

We study empirically the time evolution of scientific collaboration networks in physics and biology. In these networks, two scientists are considered connected if they have coauthored one or more papers … We study empirically the time evolution of scientific collaboration networks in physics and biology. In these networks, two scientists are considered connected if they have coauthored one or more papers together. We show that the probability of a pair of scientists collaborating increases with the number of other collaborators they have in common, and that the probability of a particular scientist acquiring new collaborators increases with the number of his or her past collaborators. These results provide experimental evidence in favor of previously conjectured mechanisms for clustering and power-law degree distributions in networks.

Chat View PDF

A quantitative gibbard-satterthwaite theorem without neutrality

2012-05-19

Elchanan Mossel , Miklós Z. Rácz

Recently, quantitative versions of the Gibbard-Satterthwaite theorem were proven for k=3 alternatives by Friedgut, Kalai, Keller and Nisan and for neutral functions on k ≥ 4 alternatives by Isaksson, Kindler … Recently, quantitative versions of the Gibbard-Satterthwaite theorem were proven for k=3 alternatives by Friedgut, Kalai, Keller and Nisan and for neutral functions on k ≥ 4 alternatives by Isaksson, Kindler and Mossel. In the present paper we prove a quantitative version of the Gibbard-Satterthwaite theorem for general social choice functions for any number k ≥ 3 of alternatives. In particular we show that for a social choice function f on k ≥ 3 alternatives and n voters, which is ε-far from the family of nonmanipulable functions, a uniformly chosen voter profile is manipulable with probability at least inverse polynomial in n, k, and ε-1.

Chat View PDF

A Dynamic Near-Optimal Algorithm for Online Linear Programming

2014-06-13

Shipra Agrawal , Zizhuo Wang , Yinyu Ye

A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP) problem in which the constraint matrix is revealed column by column along with … A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP) problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst case example showing that the performance of our algorithm is near optimal.

Chat View PDF

Incentive Compatible Two Player Cake Cutting

2012-01-01

Avishay Maya , Noam Nisan

Chat View PDF

Sampling-based algorithms for optimal motion planning

2011-06-01

Sertaç Karaman , Emilio Frazzoli

During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical … During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g. as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g. showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT* , which are provably asymptotically optimal, i.e. such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.

Chat View PDF

Investigating the distribution of password choices

2012-04-16

David Malone , Kevin Maher

The distribution of passwords chosen by users has implications for site security, password-handling algorithms and even how users are permitted to select passwords. Using password lists from four different web … The distribution of passwords chosen by users has implications for site security, password-handling algorithms and even how users are permitted to select passwords. Using password lists from four different web sites, we investigate if Zipf's law is a good description of the frequency with which passwords are chosen. We use a number of standard statistics, which measure the security of password distributions, to see if modelling the data using a simple distribution is effective. We then consider how much the password distributions from each site have in common, using password cracking as a metric. This shows that these distributions have enough high-frequency passwords in common to provide effective speed-ups for cracking passwords. Finally, as an alternative to a deterministic banned list, we will show how to stochastically shape the distribution of passwords, by occasionally asking users to choose a different password.

Chat View PDF

The asymptotic determinant of the discrete Laplacian

2000-01-01

Richard Kenyon

We compute the asymptotic determinant of the discrete Laplacian on a simply-connected rectilinear region in R^2. As an application of this result, we prove that the growth exponent of the … We compute the asymptotic determinant of the discrete Laplacian on a simply-connected rectilinear region in R^2. As an application of this result, we prove that the growth exponent of the loop-erased random walk in Z^2 is 5/4.

Chat View PDF

Analyzing and Modeling Rank Data

1996-11-01

David J. Groggel , John I. Marden

Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix Introduction Looking at data Formal tests of uniformity: summary statistics and distances Comparing several samples Overview of models Some axiomatics Likelihood methods and exponential families Distance-based models Appendix

The<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si33.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math>penalized LAD estimator for high dimensional linear regression

2013-04-17

Lie Wang

Chat View PDF

Fairness through awareness

2012-01-08

Cynthia Dwork , Moritz Hardt , Toniann Pitassi +2 more

We study fairness in classification, where individuals are classified, e.g., admitted to a university, and the goal is to prevent discrimination against individuals based on their membership in some group, … We study fairness in classification, where individuals are classified, e.g., admitted to a university, and the goal is to prevent discrimination against individuals based on their membership in some group, while maintaining utility for the classifier (the university). The main conceptual contribution of this paper is a framework for fair classification comprising (1) a (hypothetical) task-specific metric for determining the degree to which individuals are similar with respect to the classification task at hand; (2) an algorithm for maximizing utility subject to the fairness constraint, that similar individuals are treated similarly. We also present an adaptation of our approach to achieve the complementary goal of "fair affirmative action," which guarantees statistical parity (i.e., the demographics of the set of individuals receiving any classification are the same as the demographics of the underlying population), while treating similar individuals as similarly as possible. Finally, we discuss the relationship of fairness to privacy: when fairness implies privacy, and how tools developed in the context of differential privacy may be applied to fairness.

Chat View PDF

Interior Analysis for the Minimum Sum of Absolute Errors Regression

1985-05-01

Subhash C. Narula , John F. Wellington

Abstract In this article we study the effect of each observation in a data set on the minimum sum of absolute errors (MSAE) regression. First, we study the extent to … Abstract In this article we study the effect of each observation in a data set on the minimum sum of absolute errors (MSAE) regression. First, we study the extent to which the value of a response variable for an observation can be changed without affecting the MSAE regression fit and then show that MSAE regression is less sensitive to certain types of discrepant observations. Second, we study the effect of deleting an observation on parameter estimation. We illustrate the analysis with examples. KEY WORDS: Case analysisDiagnostic techniqueInfluential observation L 1-normLeast absolute valueLinear programmingSensitivity analysis

On Median Tests for Linear Hypotheses

1951-12-31

G. W. Brown , Alexander M. Mood

Chat View PDF

The number of spanning trees in regular graphs

1990-06-01

Noga Alon

Abstract Let C ( G ) denote the number of spanning trees of a graph G . It is shown that there is a function ϵ( k ) that tends … Abstract Let C ( G ) denote the number of spanning trees of a graph G . It is shown that there is a function ϵ( k ) that tends to zero as k tends to infinity such that for every connected, k ‐regular simple graph G on n vertices C ( G ) = { k [1 − δ( G )]} n . where 0 ≤ δ( G ) ≤ ϵ( k ).

Chat View PDF

A Quantitative Version of the Gibbard–Satterthwaite Theorem for Three Alternatives

2011-01-01

Ehud Friedgut , Gil Kalai , Nathan Keller +1 more

The Gibbard–Satterthwaite theorem states that every nondictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard–Satterthwaite theorem: a random manipulation … The Gibbard–Satterthwaite theorem states that every nondictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard–Satterthwaite theorem: a random manipulation by a single random voter will succeed with a nonnegligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range.

Chat View PDF

Voting Behaviour and Power in Online Democracy: A Study of LiquidFeedback in Germany's Pirate Party

2021-08-03

Christoph Kling , Jérôme Kunegis , H. Hartmann +2 more

In recent years, political parties have adopted Online Delegative Democracy platforms such as LiquidFeedback to organise themselves and their political agendas via a grassroots approach. A common objection against the … In recent years, political parties have adopted Online Delegative Democracy platforms such as LiquidFeedback to organise themselves and their political agendas via a grassroots approach. A common objection against the use of these platforms is the delegation system, where a user can delegate his vote to another user, giving rise to so-called super-voters, i.e. powerful users who receive many delegations. It has been asserted in the past that the presence of these super-voters undermines the democratic process, and therefore delegative democracy should be avoided. In this paper, we look at the emergence of super-voters in the largest delegative online democracy platform worldwide, operated by Germany’s Pirate Party. We investigate the distribution of power within the party systematically, study whether super-voters exist, and explore the influence they have on the outcome of votings conducted online. While we find that the theoretical power of super-voters is indeed high, we also observe that they use their power wisely. Super-voters do not fully act on their power to change the outcome of votes, but they vote in favour of proposals with the majority of voters in many cases thereby exhibiting a stabilising effect on the system. We use these findings to present a novel class of power indices that considers observed voting biases and gives significantly better predictions than state-of-the-art measures.

Chat View PDF

Spanning Trees in Regular Graphs

1983-06-01

Brendan D. McKay

Optimizing password composition policies

2013-06-16

Jeremiah Blocki , Saranga Komanduri , Ariel D. Procaccia +1 more

A password composition policy restricts the space of allowable passwords to eliminate weak passwords that are vulnerable to statistical guessing attacks. Usability studies have demonstrated that existing password composition policies … A password composition policy restricts the space of allowable passwords to eliminate weak passwords that are vulnerable to statistical guessing attacks. Usability studies have demonstrated that existing password composition policies can sometimes result in weaker password distributions; hence a more principled approach is needed. We introduce the first theoretical model for optimizing password composition policies. We study the computational and sample complexity of this problem under different assumptions on the structure of policies and on users' preferences over passwords. Our main positive result is an algorithm that -- with high probability --- constructs almost optimal policies (which are specified as a union of subsets of allowed passwords), and requires only a small number of samples of users' preferred passwords. We complement our theoretical results with simulations using a real-world dataset of 32 million passwords.

Chat View PDF

Emergence of Scaling in Random Networks

1999-10-15

Albert‐László Barabási , Réka Albert

Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex … Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

Chat View PDF

Justified representation in approval-based committee voting

2017-01-09

Haris Aziz , Markus Brill , Vincent Conitzer +3 more

Chat View PDF

Mixtures of distance-based models for ranking data

2003-01-01

Thomas Brendan Murphy , Donal Martin

Pattern Recognition and Machine Learning

2007-01-01

Christopher Bishop

The <i>Journal of Electronic Imaging</i> (JEI), copublished bimonthly with the Society for Imaging Science and Technology, publishes peer-reviewed papers that cover research and applications in all areas of electronic imaging … The <i>Journal of Electronic Imaging</i> (JEI), copublished bimonthly with the Society for Imaging Science and Technology, publishes peer-reviewed papers that cover research and applications in all areas of electronic imaging science and technology.

Complexity of mechanism design

2002-08-01

Vincent Conitzer , Tüomas Sandholm

The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of … The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing-on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominantstrategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.

Chat View PDF

Optimal Impartial Selection

2015-01-01

Felix R. Fischer , Max Klimm

We study a fundamental problem in social choice theory, the selection of a member of a set of agents based on impartial nominations by agents from that set. Studied previously … We study a fundamental problem in social choice theory, the selection of a member of a set of agents based on impartial nominations by agents from that set. Studied previously by Alon et al. [Proceedings of TARK, 2011, pp. 101--110] and by Holzman and Moulin [Econometrica, 81 (2013), pp. 173--196], this problem arises when representatives are selected from within a group or when publishing or funding decisions are made based on a process of peer review. Our main result concerns a randomized mechanism that in expectation selects an agent with at least half the maximum number of nominations. This is best possible subject to impartiality and resolves a conjecture of Alon et al. Further results are given for the case where some agent receives many nominations and the case where each agent casts at least one nomination.

Chat View PDF

A discrete and bounded envy-free cake cutting protocol for four agents

2016-06-10

Haris Aziz , Simon Mackenzie

We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has … We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem to obtain a bounded envy-free protocol for more than three agents. The problem has been termed the central open problem in cake cutting. We solve this problem by proposing a discrete and bounded envy-free protocol for four agents.

Chat View PDF

Truthful assignment without money

2010-06-07

Shaddin Dughmi , Arpita Ghosh

We study the design of truthful mechanisms that do not use payments for the generalized assignment problem (GAP) and its variants. An instance of the GAP consists of a bipartite … We study the design of truthful mechanisms that do not use payments for the generalized assignment problem (GAP) and its variants. An instance of the GAP consists of a bipartite graph with jobs on one side and machines on the other. Machines have capacities and edges have values and sizes; the goal is to construct a welfare maximizing feasible assignment. In our model of private valuations, motivated by impossibility results, the value and sizes on all job-machine pairs are public information; however, whether an edge exists or not in the bipartite graph is a job's private information. That is, the selfish agents in our model are the jobs, and their private information is their edge set. We want to design mechanisms that are truthful without money (henceforth strategyproof), and produce assignments whose welfare is a good approximation to the optimal omniscient welfare.

Chat View PDF