- A General Framework for a Class of Quarrels: The Quarrelling Paradox Revisited
To appear in Journal of Theoretical Politics
A. Abizadeh and A. Vetta
- Finding a Nash Equilibrium of a Random Win-Lose Game
in Expected Polynomial Time
Preprint 2025
A. Collevecchio, G. Lugosi, A. Vetta and R. Zhang
- The Popular Dimension of Matchings
To appear in Proceedings of 21st Conference on Web and Internet Economics (WINE) 2025
F. Connor, L. Langevin, N. Ndiaye, A. Totschnig, R. Vasishta and A.Vetta
- A Direct Proof of the Short-Side Advantage in Random Matching Markets
Games and Economic Behavior 154 pp53-61 2025
S. Mauras, P. Pralat and A. Vetta
- k-Leaf Powers cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5
52nd International Colloquium on Automata, Languages, and Programming (ICALP) 72:1-17 2025
M. Dupré la Tour, M. Lafond, N. Ndiaye, and A. Vetta
- Six Candidates Suffice to Win a Voter Majority
57th Symposium on Theory of Computing (STOC) pp1590-1601 2025
M. Charikar, P. Ramakrishnan, A. Lassota, A. Vetta and K. Wang
- Eliminating Majority Illusion is Easy
Proceedings of 39th Conference on Artificial Intelligence (AAAI) pp13763-13770 2025
[Best Poster Award]
J. Dippel, M. Dupré la Tour, A. Niu, S. Roy and A. Vetta
- A Recursive Measure of Voting Power that Satisfies Reasonable Postulates
Games and Economic Behavior 148 pp535-565 2024 [Preliminary version in TARK 2021]
A. Abizadeh and A. Vetta
- FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
Preprint 2024
K. Jansen, A. Lassota, M. Tutas and A. Vetta
- Discrete-Time Immunization Number
Preprint 2024
N. Clarke, K. Collins, M. Messinger, A. Trenk and A. Vetta
- The Condorcet Dimension of Metric Spaces
Preprint 2024
A. Lassota, A. Vetta and B. von Stengel
- Matrix Rationalization via Partial Orders
Proceedings of 16th International Symposium on Algorithmic Game Theory (SAGT) pp461-479 2024
A. Totschnig, R. Vasishta and A. Vetta
- Robot Positioning using Torus Packing for Multisets
Proceedings of 51st International Colloquium on Automata, Languages, and Programming (ICALP) 43:1-18 2024
C. Chen, P. Keevash, S. Kennedy, E. Panafieu and A. Vetta
- Gerrymandering Planar Graphs
Proceedings of 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS) pp463-471 2024
J. Dippel, M. Dupré la Tour, A. Niu, S. Roy and A. Vetta
- One n Remains to Settle the Tree Conjecture
Proceedings of 41st Symposium on Theoretical Aspects of Computer Science (STACS) 28:1-28:16
2024
J. Dippel and A. Vetta
- Penalties and Rewards for Fair Learning in Paired Kidney Exchange Programs
Proceedings of 19th Conference on Web and Internet Economics (WINE) 130-150 2023
M. Carvalho, A. Caulfield, Y. Lin and A.Vetta
- The Price of Anarchy in One-Sided Allocation Problems with Multi-Unit Demand Agents
Proceedings of 19th Conference on Web and Internet Economics (WINE) 420-437 2023
S. Jiang, N. Ndiame, A. Vetta and E. Wu
- Fair Algorithm Design: Fair and Efficacious Machine Scheduling
Proceedings of 15th International Symposium on Algorithmic Game Theory (SAGT) pp239-256 2023
A. Niu, A. Totschnig and A. Vetta
- The Blocker Postulates for Measures of Voting Power
Social Choice and Welfare 60(4) pp595-623 2023
A. Abizadeh and A. Vetta
- The Price of Anarchy of Two-Buyer Sequential Multiunit Auctions
ACM Transaction of Economics and Computation 11(1-2) pp1-26 2023 [Preliminary version in WINE 2020]
M. Ahunbay and A. Vetta
- The Declining Price Anomaly is not Universal
in Multi-Buyer Sequential Auctions (but almost is)
Theory of Computing Systems 66(3) pp546-580 2022 [Preliminary version in SAGT 2019]
[Best Paper Award]
V. Narayan, E. Prebet and A. Vetta
- Risk-Free Bidding in Complement-Free Combinatorial Auctions
Theory of Computing Systems 66(3) pp581-615 2022 [Preliminary version in SAGT 2019]
V. Narayan, G. Rayaprolu and A. Vetta
- An Improved Bound for the Tree Conjecture in Network Creation Games
Proceedings of 15th International Symposium on Algorithmic Game Theory (SAGT) pp241-257 2022
J. Dippel and A. Vetta
- A Case Study in Learning in Metagames: Super Smash Bros. Melee
Proceedings of 17th Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE) pp2-9 2021
J. Codsi and A. Vetta
- The Fair Division of Hereditary Set Systems
ACM Transactions on Economics and Computation 9(2) pp1-19 2021 [Preliminary version in WINE 2018]
Z. Li and A. Vetta
- Improved Two Sample Revenue Guarantees via Mixed-Integer Linear Programming
Proceedings of 14th International Symposium on Algorithmic Game Theory (SAGT) pp3-17 2021
M. Ahunbay and A. Vetta
- The Price of Stability of Envy-Free Equilibria in Multi-Buyer Sequential Auctions
Proceedings of 14th International Symposium on Algorithmic Game Theory (SAGT) pp18-33 2021
M. Ahunbay, B. Lucier and A. Vetta
- Descending the Stable Matching Lattice: How many Strategic Agents
are required to turn Pessimality to Optimality?
Proceedings of 14th International Symposium on Algorithmic Game Theory (SAGT) pp281-298 2021
[Best Paper Award]
N. Ndiaye, S. Norin and A. Vetta
- Two Birds With One Stone: Fairness and Welfare via Transfers
Proceedings of 14th International Symposium on Algorithmic Game Theory (SAGT) pp376-390 2021
V. Narayan, M. Suzuki and A. Vetta
- Pirates in Wonderland: Liquid Democracy has Bicriteria Guarantees
Proceedings of 14th International Symposium on Algorithmic Game Theory (SAGT) pp391-408 2021
J. Noel, M. Suzuki and A. Vetta
- How Many Freemasons Are There? The Consensus Voting Mechanism in Metric Spaces
Proceedings of 13th International Symposium on Algorithmic Game Theory (SAGT) pp322-336 2020
M. Suzuki and A. Vetta
- Two-Buyer Sequential Multiunit Auctions with No Overbidding
Proceedings of 13th International Symposium on Algorithmic Game Theory (SAGT) pp3-16 2020
M. Ahunbay, B. Lucier and A. Vetta
- One Dollar Each Eliminates Envy
Proceedings of 21st ACM Conference on Economics and Computation (EC) pp23-39 2020
J. Brustle, J. Dippel, V. Narayan, M. Suzuki and A. Vetta
- Pricing Policies for Selling Indivisible
Storable Goods to Strategic Consumers
Annals of Operations Research 274(1-2) pp131-154 2019 [Preliminary version in WINE 2015]
G. Berbeglia, G. Rayaprolu and A. Vetta
- The Finite Horizon, Undiscounted, Durable Goods Monopoly Problem with Finitely Many Consumers
Journal of Mathematical Economics 82(C) pp171-183 2019 [Preliminary version in WINE 2014]
G. Berbeglia, P. Sloan and A. Vetta
- Computation in Causal Graphs
Journal of Graph Algorithms and Applications 23(2) pp317-344 2019
J. Atherton, D. Ruths and A. Vetta
-
A Factor 4/3 Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
ACM Transactions on Algorithms 15(4) 55:1-28 2019 [Preliminary version in APPROX 2000]
C. Hunkenschröder, S. Vempala and A. Vetta
- Tight Bounds on the Relative Performances of Pricing Mechanisms in Storable Good Markets
Proceedings of 11th International Symposium on Algorithmic Game Theory (SAGT) pp267-271 2018
G. Berbeglia, S. Boodaghians and A. Vetta
- The Combinatorial Clock Auction: the Effects of Strategic Behaviour
and the Price Increment Rule on Social Welfare
Proceedings of 19th ACM Conference on Economics and Computation (EC) pp91-108 2018
M. Dupré la Tour and A. Vetta
- The Inapproximability of Maximum Single-Sink Unsplittable,
Priority and Confluent Flows
Theory of Computing 13(20) pp1-25 2017
B. Shepherd and A. Vetta
- The Economic Efficiency of the Combinatorial Clock Auction
Proceedings of 27th Symposium on Discrete Algorithms (SODA) pp1407-1423 2016
N. Bousquet, Y. Cai, C. Hunkenschröder and A. Vetta
- Welfare and Rationality Guarantees for the
Simultaneous Multiple-Round Ascending Auction
Proceedings of 11th Conference on Web and Internet Economics (WINE) pp216-229 2015
N. Bousquet, Y. Cai and A. Vetta
- Testing Consumer Rationality using Perfect
Graphs and Oriented Discs
Proceedings of 11th Conference on Web and Internet Economics (WINE) pp187-200 2015
S. Boodaghians and A. Vetta
- Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
Proceedings of the 56th Symposium on the Foundations of Computer Science (FOCS) pp748-758 2015
B. Shepherd, A. Vetta and G. Wilfong
- The Combinatorial World (of Auctions) According to GARP
Proceedings of 8th International Symposium on Algorithmic Game Theory (SAGT) pp125-136 2015
S. Boodaghians and A. Vetta
- Reducing the Rank of a Matroid
Discrete Mathematics & Theoretical Computer Science 17(2) pp143-156 2015
G. Joret and A. Vetta
- Large Supports are Required for Well-Supported Nash Equilibria
Proceedings of 18th Workshop on Approximation Algorithms for Combinatorial
Optimization Problems (APPROX) pp78-84 2015
Y. Anbalagan, H. Huang, S. Lovett, S. Norin, A. Vetta and H. Wu
- Coalition Games on Interaction Graphs: a Horticultural Perspective
Proceedings of 16th ACM Conference on Economics and Computation (EC) pp95-112 2015
N. Bousquet, Z. Li and A. Vetta
- A Near-Optimal Mechanism for Impartial Selection
Proceedings of 10th Conference on Web and Internet Economics (WINE) pp133-146 2014
N. Bousquet, S. Norin and A. Vetta
- To Save or not to Save: the Fisher Game
Proceedings of 10th Conference on Web and Internet Economics (WINE) pp294-307 2014
R. Mehta, N. Thain, L. Vegh and A. Vetta
- Randomized Experimental Design for Causal Graph Discovery
Proceedings of the Neural Information Processing Systems Conference (NIPS) pp2339-2347 2014
H. Hu, Z. Li and A. Vetta
- Routing Regardless of Network Stability
Algorithmica 70(3) pp561-593 2014 [Preliminary version in ESA 2012]
B. Laekhanukit, A. Vetta and G. Wilfong
- Approximating Rooted Steiner Networks
ACM Transactions on Algorithms 11(2) #8 2014 [Preliminary version in SODA 2012]
J. Cheriyan, B. Laekhanukit, G. Naves and A. Vetta
- False-Name Bidding and Economic Efficiency in Combinatorial Auctions
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI) pp2339-2347 2014
C. Alkalay-Houlihan and A. Vetta
- The Complexity of the Simultaneous Cluster Problem
Journal of Graph Algorithms and Applications 18(1) pp1-34 2014
Z. Li, M. Narayanan and A. Vetta
- Polylogarithmic Supports are Required for
Approximate Well-Supported Nash equilibria below 2/3
Proceedings of 9th Conference on Web and Internet Economics (WINE) pp15-23 2013
Y. Anbalagan, S. Norin, R. Savani and A. Vetta
- Non-Redistributive Second Welfare Theorems
Proceedings of 8th Workshop on Internet & Network Economics (WINE) pp247-243 2012
B. Laekhanukit, G. Naves and A. Vetta
- A Theoretical Examination of Practical Game Playing: Lookahead Search
Proceedings of 5th International Symposium on Algorithmic Game Theory (SAGT) pp251-262 2012.
V. Mirrokni, N. Thain and A. Vetta
- Clique Cover on Sparse Networks
Proceedings of 14th Workshop on Algorithm Engineering and Experiments (ALENEX) pp93-102 2012
M. Blanchette, E. Kim and A. Vetta
- A Minmax Theorem for Non-Interfering Flows and Galaxy Cutsets in Planar Graphs
N. Sonnerat and A. Vetta
- Predicting Direct Protein Interactions from Affinity
Purification Mass Spectrometry Data
Algorithms for Molecular Biology 5(34) 2010
M. Blanchette, E. Kim and A. Sabharwal and A. Vetta
- On the Efficiency of Markets with Two-Sided
Proportional Allocation Mechanisms
Proceedings of 3rd International Symposium on Algorithmic Game Theory (SAGT) pp246-261 2010
V. Kuleshov and A. Vetta
- Maximum Flows on Disjoint Paths
Proceedings of 13th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems (APPROX) pp326-337 2010
G. Naves, N. Sonnerat and A. Vetta
- Bounds on the Cleaning Times of Robot Vacuums
Operations Research Letters 38(1) pp69-71 2010
Z. Li and A. Vetta
- Galaxy Cutsets in Graphs
Journal of Combinatorial Optimization 19(3) pp415-427 2010 [Preliminary
version in CO 2008]
N. Sonnerat and A. Vetta
- Simultaneous Clustering of Multiple Gene
Expression and Physical Interaction Datasets (Supplementary Text)
PLoS Computational Biology 6(4) 2010 [Preliminary version in RECOMB-RG 2009]
M. Narayanan, E. Schadt, J. Zhu and A. Vetta
- An Approximation Algorithm for the Maximum Leaf
Spanning Arborescence Problem
ACM Transactions on Algorithms 6(3) 2010
M. Drescher and A. Vetta
- Computational Aspects of Multimarket Price Wars
Proceedings of 5th Workshop on Internet & Network Economics (WINE) pp304-315 2009
N. Thain and A. Vetta
- Defending Planar Graphs against Star-Cutsets
European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2009
N. Sonnerat and A. Vetta
-
On the Odd-Minor Variant of Hadwiger's Conjecture
Journal of Combinatorial Theory Series B 99 pp20-29 2009
J. Geelan, B. Gerards, B. Reed, P. Seymour and A. Vetta
- A Priority-Based Model of Routing
Chicago Journal of Theoretical Computer Science #1 pp1-28 2008
B. Farzad, N. Olver and A. Vetta
-
Planar Graph Bipartization in Linear Time
Discrete Applied Mathematics 156(7) pp1175-1180 2008 [Preliminary version in GRACO 2005]
S. Fiorini, N. Hardy, B. Reed and A. Vetta
- Network Connectivity and Malicious Attacks
N. Sonnerat and A. Vetta
- Degree-Constrained Network Flows
Proceedings of the 37th ACM Symposium on Theory of Computing (STOC) pp681-688 2007
P. Donovan, B. Shepherd, A. Vetta and G. Wilfong
- A Polynomial-Time Algorithm for Finding Nash
Equilibria in Planar Win-Lose Games
Journal of Graph Algorithms and Applications 11(1) pp309-319 2007
L. Addario-Berry, N. Olver and A. Vetta
- An Upper Bound for the Chromatic Number of Line Graphs
European Journal of Combinatorics 28(8) pp2182-2187 2007 [Preliminary version in EuroComb 2005]
A. King, B. Reed and A. Vetta
- Approximate Min-Max Relations for Odd Cycles in Planar Graphs
Mathematical Programming B 110(1) pp71-91 2007 [Preliminary version in IPCO 2005]
S. Fiorini, N. Hardy, B. Reed and A. Vetta
-
Nash Equilibria in Random Games
Random Structures and Algorithms 31(4) pp391-405 2007 [Preliminary version in FOCS 2005]
I. Barany, S. Vempala and A. Vetta
- (Almost) Tight Bounds and Existence Theorems for Single-Commodity Confluent Flows
Journal of the ACM 54(4) #16 32 pages 2007 [Preliminary version in STOC 2004]
J. Chen, R. Kleinberg, L. Lovasz, R. Rajaraman, R. Sundaram and A. Vetta
- The Demand Matching Problem
Mathematics of Operations Research 32 pp563-578 2007 [Preliminary version in IPCO 2002]
B. Shepherd and A. Vetta
-
Network Design via Iterative Rounding of Setpair Relaxations
Combinatorica 26(3) pp255-275 2006
J. Cheriyan, S. Vempala and A. Vetta
- Sink Equilibria and Convergence
Proceedings of the 46th Symposium on the Foundations of Computer Science (FOCS) pp142-154 2005
M. Goemans, V. Mirrokni and A. Vetta
-
Approximation Algorithms for Network Design with Metric Costs
SIAM Journal on Discrete Mathematics 21(3) pp612-636 2007 [Preliminary version in STOC 2005]
J. Cheriyan and A. Vetta
-
Visualizing, Finding and Packing Dijoins
Graph Theory and Combinatorial Optimization (D. Avis, A. Hertz and O. Marcotte eds.) Kluwer pp219-254 2005
B. Shepherd and A. Vetta
-
Convergence Issues in Competitive Games
Proceedings of the 7th International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems (APPROX) pp183-194 2004
V. Mirrokni and A. Vetta
-
Lighting Fibers in a Dark Network
Journal on Selected Areas in Communications 22(9) pp1583-1588 2004
B. Shepherd and A. Vetta
- Finding Odd Cycle Transversals
Operations Research Letters 32 pp299-301 2004
B. Reed, K. Smith and A. Vetta
-
On Clusterings: Good, Bad and Spectral
Journal of the ACM 51(3) pp497-515 2004 [Preliminary version in FOCS 2000]
R. Kannan, S. Vempala and A. Vetta
- Approximation Algorithms for Minimum-Cost k-Vertex Connected Subgraphs
SIAM Journal on Computing 32(4) pp1050-1055 2003 [Preliminary version in STOC 2002]
J. Cheriyan, S. Vempala and A. Vetta
- Nash Equilibria in Competitive Societies with Applications to
Facility Location, Traffic Routing and Auctions
Proceedings of the 43rd Symposium on the Foundations of Computer Science (FOCS) pp416-425 2002
A. Vetta
-
Approximating the Minimum Strongly Connected Subgraph via a Matching Lower Bound
Proceedings of the 12th Symposium on Discrete Algorithms (SODA) pp417-426 2001
A. Vetta
- Misconceptions of Biometrical IQists
Cahiers de Psychologie Cognitive 18(2) pp115-60 1999
C. Capron, M. Duyme, A. Vetta and A. Vetta
- Graph Connectivity: Relaxations and Algorithms
Ph.D. Thesis Massachusetts Institute of Technology 2002 [Advisor: S. Vempala]
A. Vetta