13 citations · 66 across the 39 of their papers we have counts for
29 papers · 1 filter
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…
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…
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…
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),…
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…
Two Birds With One Stone: Fairness and Welfare via Transfers
Vishnu V. Narayan, Mashbat Suzuki, Adrian Vetta
We study the question of dividing a collection of indivisible goods amongst a set of agents. The main objective of research in the area is to achieve one of two goals: fairness or…
Pirates in Wonderland: Liquid Democracy has Bicriteria Guarantees
Jonathan A. Noel, Mashbat Suzuki, Adrian Vetta
Liquid democracy has a natural graphical representation, the delegation graph. Consequently, the strategic aspects of liquid democracy can be studied as a game over delegation grap…
Improved Two Sample Revenue Guarantees via Mixed-Integer Linear Programming
Mete Şeref Ahunbay, Adrian Vetta
We study the performance of the Empirical Revenue Maximizing (ERM) mechanism in a single-item, single-seller, single-buyer setting. We assume the buyer's valuation is drawn from a…
The Price of Anarchy of Two-Buyer Sequential Multiunit Auctions
Mete Şeref Ahunbay, Adrian Vetta
We study the efficiency of sequential multiunit auctions with two-buyers and complete information. For general valuation functions, we show that the price of anarchy is exactly $1/…
Two-Buyer Sequential Multiunit Auctions with No Overbidding
Mete Şeref Ahunbay, Brendan Lucier, Adrian Vetta
We study equilibria in two-buyer sequential second-price (or first-price) auctions for identical goods. Buyers have weakly decreasing incremental values, and we make a behavioural…
How Many Freemasons Are There? The Consensus Voting Mechanism in Metric Spaces
Mashbat Suzuki, Adrian Vetta
We study the evolution of a social group when admission to the group is determined via consensus or unanimity voting. In each time period, two candidates apply for membership and a…
One Dollar Each Eliminates Envy
Johannes Brustle, Jack Dippel, Vishnu V. Narayan +2
We study the fair division of a collection of indivisible goods amongst a set of agents. Whilst envy-free allocations typically do not exist in the indivisible goods settin…
The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is)
Vishnu V. Narayan, Enguerrand Prebet, Adrian Vetta
The declining price anomaly states that the price weakly decreases when multiple copies of an item are sold sequentially over time. The anomaly has been observed in a plethora of p…
Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Ascending Auction
Nicolas Bousquet, Yang Cai, Adrian Vetta
The simultaneous multiple-round auction (SMRA) and the combinatorial clock auction (CCA) are the two primary mechanisms used to sell bandwidth. Under truthful bidding, the SMRA is…
Pricing Policies for Selling Indivisible Storable Goods to Strategic Consumers
Gerardo Berbeglia, Gautam Rayaprolu, Adrian Vetta
We study the dynamic pricing problem faced by a monopolistic retailer who sells a storable product to forward-looking consumers. In this framework, the two major pricing policies (…
On the Economic Efficiency of the Combinatorial Clock Auction
Nicolas Bousquet, Yang Cai, Christoph Hunkenschröder +1
Since the 1990s spectrum auctions have been implemented world-wide. This has provided for a practical examination of an assortment of auction mechanisms and, amongst these, two sim…
The Combinatorial World (of Auctions) According to GARP
Shant Boodaghians, Adrian Vetta
Revealed preference techniques are used to test whether a data set is compatible with rational behaviour. They are also incorporated as constraints in mechanism design to encourage…