13 citations · 66 across the 39 of their papers we have counts for
48 papers
The Tiered Clinching Auction with Applications to Carbon Offset Markets
Tessa Davis, Agnès Totschnig, Adrian Vetta
Voluntary carbon offsetting is a strategy which has been pursued globally by corporations to reduce their effective carbon emissions. Carbon offset markets currently suffer from lo…
Random Serial Dictatorship is -Envy-Free
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin +4
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem i…
Computing Thiele Rules on Interval Elections and their Generalizations
Dimitris Avramidis, Alexandra Lassota, Ulrike Schmidt-Kraepelin +1
Approval-based committee voting has received significant attention in the social choice community. Among the studied rules, Thiele rules, and especially Proportional Approval Votin…
Cities at Play: Improving Equilibria in Urban Neighbourhood Games
Martin Gairing, Adrian Vetta, Zhanzhan Zhao
How should cities invest to improve social welfare when individuals respond strategically to local conditions? We model this question using a game-theoretic version of Schelling's…
Finding a Nash equilibrium of a random win-lose game in expected polynomial time
Andrea Collevecchio, Gabor Lugosi, Adrian Vetta +1
A long-standing open problem in algorithmic game theory asks whether or not there is a polynomial time algorithm to compute a Nash equilibrium in a random bimatrix game. We study r…
The Popular Dimension of Matchings
Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye +3
We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching problem, (a subset of…
A Direct Proof of the Short-Side Advantage in Random Matching Markets
Simon Mauras, Pawel Pralat, Adrian Vetta
We study the stable matching problem under the random matching model where the preferences of the doctors and hospitals are sampled uniformly and independently at random. In a bala…
Six Candidates Suffice to Win a Voter Majority
Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan +2
A cornerstone of social choice theory is Condorcet's paradox which says that in an election where voters rank candidates it is possible that, no matter which candidate is d…
The Condorcet Dimension of Metric Spaces
Alexandra Lassota, Adrian Vetta, Bernhard von Stengel
A Condorcet winning set is a set of candidates such that no other candidate is preferred by at least half the voters over all members of the set. The Condorcet dimension, which is…
FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
Klaus Jansen, Alexandra Lassota, Malte Tutas +1
We study the computational complexity of fairly allocating indivisible, mixed-manna items. For basic measures of fairness, this problem is hard in general. Thus, research has flour…
Discrete-time treatment number
N. E. Clarke, K. L. Collins, M. E. Messinger +2
We introduce the discrete-time treatment number of a graph, in which each vertex is in exactly one of three states at any given time-step: compromised, vulnerable, or treated. Our…
Eliminating Majority Illusion is Easy
Jack Dippel, Max Dupré la Tour, April Niu +2
Majority Illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an i…
-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye +1
A graph is a -leaf power if there is a tree whose leaves are the vertices of with the property that a pair of leaves and induce an edge in if and o…
Matrix Rationalization via Partial Orders
Agnes Totschnig, Rohit Vasishta, Adrian Vetta
A preference matrix has an entry for each pair of candidates in an election whose value represents the proportion of voters that prefer candidate over candidate $j…
Robot Positioning Using Torus Packing for Multisets
Chung Shue Chen, Peter Keevash, Sean Kennedy +2
We consider the design of a positioning system where a robot determines its position from local observations. This is a well-studied problem of considerable practical importance an…
Gerrymandering Planar Graphs
Jack Dippel, Max Dupré la Tour, April Niu +2
We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a wei…
One n Remains to Settle the Tree Conjecture
Jack Dippel, Adrian Vetta
In the famous network creation game of Fabrikant et al. a set of agents play a game to build a connected graph. The agents form the vertex set of the graph and each vertex…
Penalties and Rewards for Fair Learning in Paired Kidney Exchange Programs
Margarida Carvalho, Alison Caulfield, Yi Lin +1
A kidney exchange program, also called a kidney paired donation program, can be viewed as a repeated, dynamic trading and allocation mechanism. This suggests that a dynamic algorit…
The Price of Anarchy of the Asymmetric One-Sided Allocation Problem
Sissi Jiang, Ndiame Ndiaye, Adrian Vetta +1
We study fair mechanisms for the (asymmetric) one-sided allocation problem with m items and n multi-unit demand agents with additive, unit-sum valuations. The symmetric case (m=n),…
The Blocker Postulates for Measures of Voting Power
Arash Abizadeh, Adrian Vetta
A proposed measure of voting power should satisfy two conditions to be plausible: first, it must be conceptually justified, capturing the intuitive meaning of what voting power is;…
A General Framework for a Class of Quarrels: The Quarrelling Paradox Revisited
Arash Abizadeh, Adrian Vetta
If a measure of voting power assigns players greater voting power because they no longer effectively cooperate, then it displays the quarrelling paradox and violates the quarrel po…
Fair Algorithm Design: Fair and Efficacious Machine Scheduling
April Niu, Agnes Totschnig, Adrian Vetta
Motivated by a plethora of practical examples where bias is induced by automated-decision making algorithms, there has been strong recent interest in the design of fair algorithms.…
Risk-Free Bidding in Complement-Free Combinatorial Auctions
Vishnu V. Narayan, Gautam Rayaprolu, Adrian Vetta
We study risk-free bidding strategies in combinatorial auctions with incomplete information. Specifically, what is the maximum profit that a complement-free (subadditive) bidder ca…
An Improved Bound for the Tree Conjecture in Network Creation Games
Jack Dippel, Adrian Vetta
We study Nash equilibria in the network creation game of Fabrikant et al.[10]. In this game a vertex can buy an edge to another vertex for a cost of , and the objective of each…