SAGT 2010 accepted papers

http://sagt2010.cti.gr/
  • Elchanan Mossel and Omer Tamuz. Truthful Fair Division  
  • Uriel Feige and Moshe Tennenholtz. Responsive Lotteries 
  • Reshef meir, Yoram Bachrach and Jeffrey Rosenschein. Minimal Subsidies in Expense Sharing Games
  • Vincenzo Auletta , Diodato Ferraioli, Francesco Pasquale and Giuseppe Persiano. Mixing Time and Stationary Expected Social Welfare of Logit Dynamics
  • Felix Brandt, Felix Fischer and Paul Harrenstein. On the Rate of Convergence of Fictitious Play
  • Dimitris Fotakis, George Karakostas and Stavros Kolliopoulos. On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users
  • Chinmay Karande, Gagan Goel and Lei Wang. Single-Parameter Combinatorial Auctions with Partially Public Valuations
  • Bharat Adsul, Sobhan Babu, Jugal Garg, Ruta Mehta and Milind Sohoni. Nash Equilibria in Fisher Market
  • Yonatan Aumann and Yair Dombb. Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games
  • Alexander Skopalik and Martin Hoefer. On the Complexity of Pareto-optimal Nash and Strong Equilibria
  • Noam Hazon and Edith Elkind. Complexity of Safe Strategic Voting
  • Constantinos Daskalakis , Rafael Frongillo, Christos Papadimitriou , George Pierrakos and Gregory Valiant. On Learning Algorithms for Nash Equilibria
  • Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet and Santosh Vempala. On Nash-Equilibria of Approximation-Stable Games
  • Uriel Feige and Inbal Talgam. A Direct Reduction from k-Player to 2-Player Approximate Nash
  • Martin Gairing and Rahul Savani. Computing stable outcomes in hedonic games
  • Uri Nadav and Georgios Piliouras. No Regret Learning in Oligopolies: Cournot vs Bertrand
  • Kristoffer Arnsfelt Hansen , Peter Bro Miltersen and Troels Bjerre Sørensen. The computational complexity of trembling hand perfection and other equilibrium refinements
  • Bharat Adsul , Sobhan Babu , Jugal Garg , Ruta Mehta and Milind Sohoni. A Simplex-like Algorithm for Fisher Markets
  • Matus Mihalak and Jan Christoph Schlegel. It's mostly constant in network creation games
  • Vijay Vazirani. 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
  • Volodymyr Kuleshov and Adrian Vetta. On the Efficiency of Markets with Two-Sided Proportional Allocation Mechanisms
  • Elliot Anshelevich , Bugra Caskurlu and Ameya Hate. Partition Equilibrium Always Exists in Resource Selection Games
  • Martin Macko, Kate Larson and Ľuboš Steskal. Braess's Paradox for Flows Over Time
  • Gagan Goel and Vijay Vazirani. A Perfect Price Discrimination Market Model with Production, and a Convex Program for it
  • Alex Fabrikant, Aaron D. Jaggard and Michael Schapira. On the Structure of Weakly Acyclic Games
  • Vittorio Bilo , Ioannis Caragiannis , Angelo Fanelli and Gianpiero Monaco. Improved lower bounds on the price of stability of undirected network design games
  • Bart de Keijzer , Guido Schaefer and Orestis Telelis. On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games
  • Rajgopal Kannan and Costas Busch. Bottleneck Congestion Games with Logarithmic Price of Anarchy

Comments

Post a Comment

Popular posts from this blog

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Image
Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...
Read more

Proportionally Representative Clustering

Image
H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...
Read more

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 
Read more