- A Direct Proof of the Short-Side Advantage in Random Matching Markets
Preprint 2024
S. Mauras, P. Pralat and A. Vetta
- Six Candidates Suffice to Win a Voter Majority
Preprint 2024
M. Charikar, P. Ramakrishnan, A. Lassota, A. Vetta and K. Wang
- 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
- k-Leaf Powers cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5
Preprint 2024
M. Dupré la Tour, M. Lafond, N. Ndiaye, and A. Vetta
- Eliminating Majority Illusion is Easy
To appear in Proceedings of 39th Conference on Artificial Intelligence (AAAI) 2025
J. Dippel, M. Dupré la Tour, A. Niu, S. Roy and A. Vetta
- 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
- A General Framework for a Class of Quarrels: The Quarrelling Paradox Revisited
Preprint
A. Abizadeh 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
- A Recursive Measure of Voting Power that Satisfies Reasonable Postulates
Proceedings of 18th Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2021
A. Abizadeh 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