AGATE
- Salerno
Research Group
on
Algorithmic Game Theory
and Micro Economics
Our group is working on algorithmic aspects of game theory and micro
economics. In particular, we study computational aspects arising in the
context of so called selfish agents. Selfish agents are used to
model those situation in which the entities involved in the computation
cannot be assumed to act altruistically and to cooperate with the
"system". They rather follow their personal interests, which may result
in a loss of performance.
Our research focuses on the design of efficient algorithmic
solutions for problems involving selfish agents that arise in practical
applications (the Internet being the major source). One of the main
goals is to investigate the interplay of limited computational
resources and the presence of selfishly acting entities, and the loss
of performance due to the combination of these two aspects. This brings
together the two well-established research areas of theory of
computing and micro economics, and poses new questions whose
answer requires (new) sophisticated mathematical tools.
People involved: Pasquale Ambrosio, Vincenzo
Auletta, Roberto De
Prisco, Alessandro
Ferrante, Mimmo
Parente, Paolo Penna,
Pino Persiano, Carmine Ventre.
For more information regarding our work on these topics
see:
-
A power
point presentation of our research within the European project CRESCCO
(also containing some information about the main objective, state of
the
art, and preliminary results obtained by our group) [year 2002, year 2003, year 2004
].
-
A tutorial on
scheduling with selfish machines presented at FUN 04
- A course on Algorithms
for Selfish Agents held at the
University of Salerno (a graduate class)
- A Workshop on
Algorithmic Game Theory (1st
AGATE)
- Some of the most
recent papers from our group:
- V.
Auletta, R. De Prisco, P. Penna, P. Persiano, and C. Ventre. New Constructions of Mechanisms with Verification.
An extended abstract will appear in the Proceedings of ICALP 06.
- P.
Penna, G. Proietti, and P. Widmayer. Polynomial-Time
Truthful Mechanisms in One Shot. Technical
Report N. TRCS
003/2006, Dipartimento di Informatica, Universita' degli Studi di
L'Aquila, 2006.
- P. Penna and C. Ventre. The
Algorithmic Structure of Group Strategyproof Budget-Balanced
Cost-Sharing Mechanisms.
To appear
in Proc. of STACS'06.
- P. Penna and C. Ventre. Some New
Ideas for Critical Resource Sharing Involving Selfish Agents.
An
informal survey paper on some recent results from this group, 2005.
- A.
Ferrante, G. Parlato, F.
Sorrentino and C.
Ventre. Improvements for
Truthful
Mechanisms with Verifiable
One-Parameter Selfish Agents. In Proc. of WAOA'05, LNCS 3879, pag.
147-160, 2005.
- P. Penna and C. Ventre. Free-riders
in Steiner tree cost-sharing games. In Proc.
of SIROCCO'05, LNCS 3499, pag. 231-245,
2005. Full version
available as Technical
Report
of the European project CRESCCO,
2004 [slides
in PPT].
- V.
Auletta, R.
De Prisco, P.
Penna and P. Persiano.On
Designing Truthful Mechanisms for Online Scheduling. In Proc.
of SIROCCO'05, LNCS 3499, pag. 3-17,
2005. Full version
available as Technical
Report
of the European project CRESCCO,
2004 [slides
in PPT]
- P.
Ambrosio and V. Auletta. Deterministic
Monotone Algorithms for Scheduling on Related Machines. In
Proc. of WAOA'04, LNCS
3351, pag. 267-280, 2005.
- P.
Penna and C. Ventre. More
Powerful and Simpler Cost-Sharing Methods. In
Proc. of WAOA'04,
LNCS 3351, pag 97-110, 2005 [slides
in PPT]. Full version
available as Technical
Report
of the European project CRESCCO,
2004 [slides
in PPT].
- G.
Melideo, P. Penna, G. Proietti, R.
Wattenhofer and P. Widmayer. Truthful
mechanisms for generalized utilitarian problems. In Proc. of IFIP-TCS'04, Kluwer Academic
Publisher, pag. 165-180, 2004. Full version available
as Technical Report of the European
project CRESCCO, 2003.
- V. Auletta, R. De Prisco, P.
Penna and P. Persiano. The
Power of Verification for One-Parameter Agents. In Proc.
of ICALP'04, LNCS 3142, pag. 171-182, 2004. Full version also
available
as Technical Report of the European
project CRESCCO, 2003.
- V. Auletta, R. De Prisco, P.
Penna and P. Persiano. How
to route and tax selfish unsplittable traffic. In Proc. of
SPAA'04, ACM Press, pag. 196-205, 2004. Full version available as
Technical Report of the European project CRESCCO,
2003.
- P. Penna and C. Ventre. Sharing
the Cost of Multicast Transmissions in Wireless Networks. In
Proc. of SIROCCO'04, LNCS 3104, pag. 255-266, 2004. Full version available as
Technical Report of the European project CRESCCO,
2003.
- V. Auletta, R. De Prisco, P.
Penna and P. Persiano. Deterministic
Truthful Approximation Mechanisms for Scheduling Related Machines.
In Proc. of STACS'04, LNCS 2996, pag.608-619, 2004. Full
version available
as Technical Report of the European project CRESCCO,
2003 [slides
in PDF].
- C. Ambuehl, A. Clementi, P. Penna, G. Rossi and R. Silvestri.
Energy
Consumption in Radio Networks: Selfish Agents and Rewarding Mechanisms.
In Theoretical Computer Science,
Vol. 343, Issue 1-2, pag. 27-41, 2005. Preliminary
version in Proc. of SIROCCO'03, Carleton Scientific Press, pag.
1-16,
2003. Full version also available as Technical
Report of the European project CRESCCO,
2003 [slides
in PDF].
- Nash Equilibria
- A. Ferrante and M.
Parente. Existence of
Nash
Equilibria
in Selfish Routing Problems. In Proc. of SIROCCO'04,
LNCS 3104, pag. 149-160, 2004.
- P.
Crescenzi, M. Di Ianni, A. Lazzoni, P. Penna, G. Rossi and P. Vocca. Equilibria
for Broadcast Range Assignment Games in Ad-Hoc Networks. In Proc. of AD-HOC-NOW'05, LNCS
3738, pag. 4-17, 2005.